Queue
Internal
Overview
Overview
A queue is a dynamic set in which the the DELETE operation, which does not have any argument, removes the oldest element in the queue. The queue implements the first-in-first-out, or FIFO, policy. The queue has a head and a tail. The INSERT operation for a queue is called ENQUEUE and places the new element at the tail. The DELETE operation is called DEQUEUE, and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue underflows. If we attempt to enqueue an element on a full queue, it is said that the queue overflows.
Implementation
The following implementation uses an array, which dictates the queue length. The queue grows circularly and wraps around the edge of the array as the data is enqueued and dequeued. We use to pointers, "head" and "tail", containing the indexes of the corresponding head and tail elements. The "head" pointer indicates the head element - the one that will be dequeued next, while "tail" points to the position where the next enqueued element will be placed.
An empty queue is indicated by the fact that the "head" and the "tail" pointers have the same value.
We have two choices when it comes to model a full queue. If we want to use all the n elements in the array for queue element storage, then we model the "full" position with an external boolean, because otherwise there would be no way to distinguish the "empty queue" head and tail overlap and "full queue" head and tail overlap. Another possibility is to use only n - 1 elements of the array for queue element storage, and use one array element as a "marker" that always separates the head from the tail. This way, the "head" and "tail" pointers never overlap for a full queue, just for an empty queue.
The equivalent implementations are presented below:
n element Queue
We model "full" and "empty" by allowing the "head" and "tail" markers to overlap, and we maintain an extra bit of data that tells those states apart.