[자료구조] Circular Queue

Circular Queue Data Structure

A circular queue is the extended version of a regular queue where the last element is connected to the first element. Thus forming a circle-like structure.

 

 

 

 

The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit of insertion and deletion, there will be non-usable empty space.

 

 

 

 

 

 

Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This reduces the actual size of the queue.

 

How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.

Here, teh circular increment is performed by modulo division with the queue size.

 

Circular Queue Operations

The circular queue work as follows:

• two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1

1. Enqueue Operation

• check if the queue is full
• for the first element, set value of FRONT to 0
• circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
• add the new element in the position pointed to by REAR

2. Dequeue Operation

• check if the queue is empty
• return the value pointed by FRONT
• circulary increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

• Case 1 : FRONT = 0 && REAR == SIZE-1
• Case 2 : FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

 

Circular Queue Complexity Analysis

 

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).

 

Applications of Circular Queue

• CPU scheduling
• Memory management
• Traffic Management

 

Example Code with TypeScript

class CircularQueue<T> {
    private arr: Array<T>;
    private first: number;
    private rear: number;
    private size: number;

    constructor(size: number){
        this.size = size;
        this.first = -1;
        this.rear = -1;
        this.arr = new Array<T>(size);
    }

    enqueue(item:T) {
        if(this.isFull()){
            console.log('queue is full');
            throw new Error('queue is full');
        }

        if(this.isEmpty()){
            this.first = 0;
        }

        this.rear = (this.rear + 1) % this.size;
        
        this.arr[this.rear] = item;

    }

    dequeue(): T {
        if(this.isEmpty()){
            console.log('queue is empty');
            throw new Error('queue is empty');
        }

        let dequeueResult = this.arr[this.first];

        if(this.first == this.rear){
            this.first = -1;
            this.rear = -1;
        }else{
            this.first = (this.first + 1) % this.size;
        }
        return dequeueResult;
    }

    isEmpty(): boolean {
        return (this.first == -1);
    }

    isFull(): boolean {
        return (this.first == (this.rear+1)%this.size)
    }

    peek(): T | undefined {
        if(this.isEmpty()){
            console.log('queue is empty');
            throw new Error('queue is empty');
        }

        return this.arr[this.first];

        
    }
}

References

URL : https://www.programiz.com/dsa/circular-queue