Data Structures: Queues

├─ What is a QUEUE
└─ How does it implement CONTAINER abstract data type

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. C++ class prototype using Double Ended Queue:

template<typename T>
class Queue {
    ...
    private: 		
        T* contents;
        std::size_t capacity;
        std::size_t size;
        std::size_t position_start;
        std::size_t position_end;
};

How values are added/deleted to/from queue using Double Ended Queue:

For a complete implementation example, check Queue class documentation or its GitHub code.

What is a Double Ended Queue?

A double ended queue (aka deque) is something like a dynamic array, only that it's able to offer constant time O(1) access to HEAD by keeping track of following extra coordinates:

START INDEX: position in NATIVE ARRAY underneath where HEAD is located
END INDEX: position in NATIVE ARRAY underneath where TAIL is located

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 a value greater than zero, but smaller than CAPACITY: so when HEAD element is deleted, START INDEX merely increments.

How can a queue be implemented?

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

Double Ended Queue: a slightly modified dynamic array that grows on TAIL and contracts on HEAD can be used.
Doubly Linked List: a normal doubly linked list that grows on TAIL and contracts on HEAD can be used

Conclusion: even though Doubly Linked List seems like a natural candidate for this kind of operations, Double Ended Queue is able to produce much higher performance and thus should be solution of choice!

How does it implement CONTAINER abstract data type?

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.