Data Structures: Queues

What is a queue?

A queue is a data structure that behaves like a black box in which all insertions are performed on TAIL, while retrievals/deletions are performed on HEAD. This kind of access is called First-In-First-Out (FIFO) and structurally makes queue a natural Container implementation.

How can a queue be implemented?

All queues use a List implementation as storage, which can be:

What is a double ended queue?

A double ended queue is something like a dynamic array, only that it's able to offer constant time O(1) access to HEAD by maintaining an extra start index which tracks position of HEAD in memory block. For a normal Dynamic Array, start index is always zero, which means memory block gets filled from position zero onwards. If head element is deleted, all items in block have to be padded one step left so that start index remains zero. In a double ended queue, however, start index can be any value greater or equal than zero, but smaller as CAPACITY: so when HEAD element is deleted, start index merely increments.

Conclusion: even though Doubly Linked List seems like a natural candidate for this kind of operations, double ended queue derivation of Dynamic Array is able to produce much higher performance and thus should be solution of choice!

How does it work?

Let us take its Container implementation as double ended queue to better understand how it works:

Operation Description
clear Frees memory block from RAM, reallocates it for same CAPACITY, resets SIZE to zero.
size Gets SIZE value
isEmpty Checks if SIZE equals zero
push Adds entry at START_INDEX + SIZE position then increments SIZE
If CAPACITY is reached, memory block grows by doubling its size.
peek Gets value at START_INDEX position (HEAD).
pop Gets value at START_INDEX position (TAIL), removes it from queue and increments START_INDEX position.

Share