Queues and Circular Queues (With Code in C, C++, Java, and Python)
Introduction
A queue is a linear data structure where an item can be inserted from one end and can be removed from another end. We can not insert and remove items from the same end. Figure 1 shows the structure of a queue.
One end of the queue is called a front and the other end is called a rear. Items are inserted in the rear end and are removed from the front end. A queue is called a First In First Out data structure because the item that goes first comes out first.
A real-life example of a queue would be a queue of people in a bank. A cashier can serve only one person at a time. When a person comes while the cashier is serving another person, he/she needs to sit in the queue. If there is more than one person in the queue, the person needs to go to the rear end of the queue and wait for his/her turn.
The queue as an Abstract Data Type (ADT) has following operations.
EnQueue: It is also called a Push or an Insert operation. It inserts an item at the rear end of the queue.
DeQueue: It is also called a Pop or a Remove operation. It removes the item from the front end of the queue.
front: It returns the item at the front of the queue.
isEmpty: It checks whether the queue is empty. If the queue is empty, we cannot do front and dequeue operations.
Details of these operations are described below.
Operations on a queue
EnQueue
The enqueue operation inserts a new item at the rear end of the queue. After the enqueue operation, the value of rear is increased by 1. Figure 2 shows the enqueue operation.
In Figure 2, when an item i4 is inserted, the rear moves one step to the right but the front remains in the same place. The algorithm for the insertion operation using an array is given below.
if (size of queue is > N) {
print "Error: queue is full"
return
}
rear = rear + 1
queue[rear] = item
DeQueue
The dequeue operation removes the item at the front of the queue. When we remove the item at the front, we increase the value of front. Figure 3 shows the dequeue operation.
In Figure 3, when the item i1 is removed from the queue, we increase move the front one step to the right whereas the rear remains in the same place. The algorithm for dequeue operation using an array is given below.
if (rear == -1 and front == -1) {
print "Error: queue is empty"
return
}
item = queue[front]
front = front + 1
return item
front
The front operation returns the item at the front of the queue. This operation does not affect the position of both rear and front.
isEmpty
The isEmpty operation checks whether the queue is empty or note. The queue is empty when the value of both the rear and front is -1 (initially we set both front and rear to -1).
Illustration of enqueue and dequeue
Figure 4 shows the enqueue and dequeue operations and changes in the value of rear and front for some insertions and deletions.
Initially, we set both rear and front to -1. When the first item is inserted we increase the value of both rear and front by 1. After that for every enqueue operation, we increase the value of rear by 1 keeping the front as it is and for every dequeue operation, we increase the value of front by 1 keeping the rear as it is.
In both enqueue and dequeue operations, we increase the value of front and rear. We never decrease the value of both of them. For a limited sized queue (i.e. array implementation) this creates a problem when the rear of the queue reaches the maximum index. Figure 5 illustrates this.
Figure 5 shows a queue that can hold 9 items. Currently, there are only 3 items. Even though the queue can still hold 6 more items, when we try to insert a new item, it says the queue is full. This is because the rear of the queue is already in its maximum index position. This problem can be avoided using the circular array.
Circular Queue
In a linear queue, when a new item is inserted, we increase the value of a rear by 1 and insert the new item in the new position. However, in a circular queue, when a new item is inserted, we update the rear as rear = (rear + 1) % N where N is the capacity of the queue. This makes the queue circular. Let us illustrate this by an example.
Suppose we have a queue whose capacity is 7 i.e. it can hold at most 7 items. Suppose the rear of the queue is at 7th position and the front of the queue is at 3rd position which means the 1st and 2nd position are unused. Let us try to insert a new item. The new position of the rear will be (7 + 1) % 7 = 1. Since the 1st position is unused, the item is inserted there. We do the similar for the front. When an item is deleted, we update the front as front = (front + 1) % N. Figure 6 shows an example of a circular queue.
Since there is no boundary in a circular queue, how do we know when the queue is full? The queue is full when rear and front are adjacent to each other i.e. when (rear + 1) % N == front, the queue is full. The implement of a circular queue is given in the implementation section.
Complexities
All the operations of a queue take a constant time.
Operation
Complexity
enqueue
O(1)
dequeue
O(1)
front (Peek)
O(1)
isEmpty
O(1)
Applications of a queue
In shared resources like a printer, jobs are stored in a queue.
In task CPU scheduling, tasks are stored in a queue.
In many graphs algorithms like Breadth First Search, vertices stored in a queue.
Interrupt handling. Interrupts are stored in a queue.
Many messaging queue systems using the queue to store messages.
#include #define MAX_SIZE 10 int front = -1; int rear = -1;
intqueue[MAX_SIZE];
// insert an item at the rear of the queue voidenqueue(int item){ // Check if the queue is full if ((rear + 1) % MAX_SIZE == front) { printf("%s\n", "ERROR: Queue is full"); return; }
// if there are no items, make front and rear 1 // else increment the rear by 1 if (front == -1 && rear == -1) { front = rear = 0; } else { rear = (rear + 1) % MAX_SIZE; }
// insert the time at rear queue[rear] = item; }
// removes the item from the front of the queue intdequeue(){ int item; // Check if the queue is empty if (rear == -1 && front == -1) { printf("%s\n", "ERROR: Queue is empty"); return-999999; } item = queue[front]; if (front == rear) { front = rear = -1; } else { // increase the front front = (front + 1) % MAX_SIZE; } return item;
}
// returns the item from the front of the queue intgetFront(){ // Check if the queue is empty if (rear == -1 && front == -1) { printf("%s\n", "ERROR: Queue is empty"); return-999999; }
classQueueArray { private: conststaticint MAX_SIZE = 10; intqueue[MAX_SIZE]; int rear; int front; public: QueueArray() { rear = front = -1; }
// insert an item at the rear of the queue voidenqueue(int item){ // Check if the queue is full if ((rear + 1) % MAX_SIZE == front) { cout<<"ERROR: Queue is full"<<endl; return; }
// if there are no items, make front and rear 1 // else increment the rear by 1 if (front == -1 && rear == -1) { front = rear = 0; } else { rear = (rear + 1) % MAX_SIZE; }
// insert the time at rear queue[rear] = item; }
// removes the item from the front of the queue intdequeue(){ int item; // Check if the queue is empty if (rear == -1 && front == -1) { cout<<"ERROR: Queue is empty"<<endl; return-999999; } item = queue[front]; if (front == rear) { front = rear = -1; } else { // increase the front front = (front + 1) % MAX_SIZE; } return item;
}
// returns the item from the front of the queue intgetFront(){ // Check if the queue is empty if (rear == -1 && front == -1) { cout<<"ERROR: Queue is empty"<<endl; return-999999; }
// insert an item at the rear of the queue publicvoidenqueue(int item){ // Check if the queue is full if ((rear + 1) % MAX_SIZE == front) { System.out.println("ERROR: Queue is full"); return; }
// if there are no items, make front and rear 1 // else increment the rear by 1 if (front == -1 && rear == -1) { front = rear = 0; } else { rear = (rear + 1) % MAX_SIZE; }
// insert the time at rear queue[rear] = item; }
// removes the item from the front of the queue publicintdequeue(){ int item; // Check if the queue is empty if (rear == -1 && front == -1) { System.out.println("ERROR: Queue is empty"); return -999999; } item = queue[front]; if (front == rear) { front = rear = -1; } else { // increase the front front = (front + 1) % MAX_SIZE; } return item;
}
// returns the item from the front of the queue publicintgetFront(){ // Check if the queue is empty if (rear == -1 && front == -1) { System.out.println("ERROR: Queue is empty"); return -999999; }
structNode { int data; structNode *next; structNode *prev; };
typedefstructNode *NodePtr;
// define front and rear globally NodePtr front = NULL; NodePtr rear = NULL;
// inserts an item at the rear of the queue voidenqueue(int item){ NodePtr node = malloc(sizeof(NodePtr)); node->data = item; node->next = NULL; node->prev = NULL;
// if the queue is empty, make this node front and rear // else insert it at the end of the queue if (rear == NULL) { rear = node; front = node; } else { rear->next = node; node->prev = rear; rear = node; } }
// remove the item at the front of the queue intdequeue(){ int item; if (front == NULL) { printf("%s\n", "ERROR: Queue is empty"); return-999999; } // destory the front and make the next item new front item = front->data; NodePtr next = front->next;
classQueueArray { private: conststaticint MAX_SIZE = 10; intqueue[MAX_SIZE]; int rear; int front; public: QueueArray() { rear = front = -1; }
// insert an item at the rear of the queue voidenqueue(int item){ // Check if the queue is full if ((rear + 1) % MAX_SIZE == front) { cout<<"ERROR: Queue is full"<<endl; return; }
// if there are no items, make front and rear 1 // else increment the rear by 1 if (front == -1 && rear == -1) { front = rear = 0; } else { rear = (rear + 1) % MAX_SIZE; }
// insert the time at rear queue[rear] = item; }
// removes the item from the front of the queue intdequeue(){ int item; // Check if the queue is empty if (rear == -1 && front == -1) { cout<<"ERROR: Queue is empty"<<endl; return-999999; } item = queue[front]; if (front == rear) { front = rear = -1; } else { // increase the front front = (front + 1) % MAX_SIZE; } return item;
}
// returns the item from the front of the queue intgetFront(){ // Check if the queue is empty if (rear == -1 && front == -1) { cout<<"ERROR: Queue is empty"<<endl; return-999999; }
// insert an item at the rear of the queue publicvoidenqueue(int item){ // Check if the queue is full if ((rear + 1) % MAX_SIZE == front) { System.out.println("ERROR: Queue is full"); return; }
// if there are no items, make front and rear 1 // else increment the rear by 1 if (front == -1 && rear == -1) { front = rear = 0; } else { rear = (rear + 1) % MAX_SIZE; }
// insert the time at rear queue[rear] = item; }
// removes the item from the front of the queue publicintdequeue(){ int item; // Check if the queue is empty if (rear == -1 && front == -1) { System.out.println("ERROR: Queue is empty"); return -999999; } item = queue[front]; if (front == rear) { front = rear = -1; } else { // increase the front front = (front + 1) % MAX_SIZE; } return item;
}
// returns the item from the front of the queue publicintgetFront(){ // Check if the queue is empty if (rear == -1 && front == -1) { System.out.println("ERROR: Queue is empty"); return -999999; }
# inserts an item at the rear of the queue defenqueue(self, item): node = Node(item)
# if the queue is empty, make this node front and rear # else insert it at the end of the queue if self.rear == None: self.rear = node self.front = node else: self.rear.next = node node.prev = self.rear self.rear = node
# remove the item at the front of the queue defdequeue(self): if self.front == None: print"ERROR: Queue is empty" return-999999 # destory the front and make the next item new front item = self.front.data next_node = self.front.next