In the last article, we looked at Stack, which was a LIFO (Last In First Out) structure. What this means is that the element which goes in last (is on the top), comes out first (when popped). We will now have a look at data structure called Queue, and its variants.
Recollect how a Stack had a ‘top’. Queue is a data structure with two points, a ‘front’ and a ‘rear’. Elements are added to the rear and removed from the front. Thus, the elements are removed in the order of their respective insertion into the queue. Hence, it can be said that the Queue is a FIFO (First In First Out) data structure.
Thus, there are two basic operations in a queue:
i) Enqueue: To insert an element at the rear of the queue. The complexity of this operation is expected to be O(1).
ii) Dequeue: To remove an element from the front of the queue. The complexity of this operation is expected to be O(1).
A queue and its operations.
As with a stack, a queue can also be represented using either an array or a linked list of elements.
Thus, we can see that the implementation should be fairly simple to understand if you have grasped the concept of linked lists. The array implementation of the queue has two pointers, front and rear which point to indices within the array, which act as the front and the rear. In the dequeue operation, the front pointer is incremented by one, and in the enqueue operation, the rear is incremented by one. However, once rear reaches the fixed boundary of the array, it can no longer be incremented, (even though there may be some free space in the array) until certain special adjustments are made.
To use the array without any problems, we implement a slightly different way of manipulating the front and rear pointers. This concept is known as a Circular Queue or in general, a Circular Buffer.
The array is considered to be a ‘circular’ one, joined end-to-end. So, once the rear reaches the boundary, it simply goes to the next position which is the beginning of the array (provided front does not lie there), and this process can go on until rear meets front.
A Circular Queue
Similarly after repeated deletions, the front may approach the boundary too, and can similarly wrap around too.
Double-Ended queue allows queuing and dequeuing to happen both at front and rear. It is also known as deque (pronounced as deck). Complexity of both the operations remains O(1).
Priority queue demands elements to be added with a ‘priority’. When, an element is to be removed from the front, the element with the greatest priority is removed first, regardless of when it arrived. A simple-implementation is O(N) for Enqueue and O(1) for Dequeue if a list of elements sorted by priority is maintained, where N is the number of elements in the queue. An O(1) for Enqueue and O(N) for Dequeue is also common when a sorted list is not maintained, and the element with the highest-priority is looked up in the list at the time of dequeuing.
However, common implementations use a special data structure called Heap, which gives O(log N) insertion and removal complexities.
Queue is implemented in C++ STL (Standard Template Library) using the queue template. Functions for pushing (queuing) and popping (dequeuing) at both front and back are, push_front, push_back, pop_front, and pop_back. There are implementations of Queue in most modern languages, however, one is expected to be comfortable with implementing them without external help.
- Implement the Circular Queue
- Implement Double-Ended Queue.