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.
All queues use a List implementation as storage, which can be:
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!
Let us take its Container implementation as double ended queue to better understand how it works:
|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.|