Understanding Queue
Queue is a FIFO (First In First Out) data structure. Imagine a queue of people standing to buy a ticket for a movie. The person standing in front of the queue was the first person to enter and queue. He/she also gets the ticket earlier than anyone else and leaves the queue. So the first person to enter the queue (First In) was the first person to leave the queue (First Out).
Given a fixed size, queues can be easily implemented through an array where we push a new element at the end of the array and pop an element from the front of the array. We can simulate these push and pop operations by keeping two pointers front and rear which keep track of the front and rear ends of the queue respectively. A queue of size 5 having three elements will look like this:
[ 1, 2, 3, x, x]
^ ^
front rear
Where x denotes a value we don't know or care about.
We can implement a circular queue on the same lines by wrapping through the array. Consider this:
Queue size: 5. Front denoted by * and rear denoted by #.
push(1) -> [1*#,x,x,x,x]
push(2) -> [1*,2#,x,x,x]
push(3) -> [1*,2,3#,x,x]
pop() -> [x,2*,3#,x,x]
push(4) -> [x,2*,3,4#,x]
push(5) -> [x,2*,3,4,5#]
push(6) -> [1#,2*,3,4,5]
Notice how in the last step we used up the empty space in the beginning of the array. Instead of simply doing rear = rear+1, we do rear = (rear+1)%size
Solution
Few points to keep in mind while reading the code:
- We start with front = rear = -1
- Whenever front = -1 it means the queue is empty
- When front != -1 but front = rear that means queue has only 1 element. Now, if we were to pop that element, the queue becomes empty so it is a good idea to reset front=rear=-1 which enables us to fill the queue next time from index 0 instead of filling the queue from that index.
capacitystores the remaining number of elements which can be pushed to the queue. If capacity == 0 that means queue is full. If capacity == size that means queue is empty.
class MyCircularQueue {
public:
vector<int> q;
int front, rear, capacity, size;
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
q = vector<int>(k);
front = rear = -1;
capacity = size = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if (isFull())
return false;
if (front == -1)
front = rear = 0;
else
rear = (rear+1)%size;
q[rear] = value;
capacity--;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty())
return false;
if (rear == front)
rear = front = -1;
else
front = (front+1)%size;
capacity++;
return true;
}
/** Get the front item from the queue. */
int Front() {
if (isEmpty())
return -1;
return q[front];
}
/** Get the last item from the queue. */
int Rear() {
if (isEmpty())
return -1;
return q[rear];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return front == -1;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return capacity == 0;
}
};