\(\newcommand{\Front}{\mathit{front}}\) \(\newcommand{\Back}{\mathit{back}}\)

Queues and Deques

Queues usually refer to first-in-first-out (FIFO) queues. The basic operations are

  • ​ enqueue, which puts an element at the end of the queue, and

  • ​ dequeue, which removes the first element in the queue.

_images/queue.png

Queues are easy to implement with mutable linked lists so that both enqueue and dequeue are constant-time operations: for an enqueue operation, one only has to insert a new list entry at the end, while dequeue corresponds to removing the first list entry.

_images/queue-as-list.png

Another implementation technique is to use circular buffers backed by resizable arrays. In them a queue \(v_1,v_2,...,v_n\) is stored in a resizable array of size \(k \ge n\). A \(\Front\) index points to the array element containing \(v_1\) and the queue elements are then in the indices \(\Front\), \(\Front+1\), …, \(\Front+n-1\) modulo \(k\). The \(\Back\) index is \(\Front+n-1 \bmod k\). Enqueueing now corresponds to increasing the \(\Back\) index by one (modulo \(k\) as always) and writing the enqueued element in the new index. If \(n\) would be greater than \(k\), then the array is resized and the queue contents are copied to the new larger array. Dequeueing is done by simply increasing the \(\Front\) index by one (modulo \(k\)). Note that circular buffers also allow constant-time random access to the queue elements.

_images/circular.png

Double-ended queues (abbreviated to deques, pronounced “deck”) extend queues by allowing removing elements at the end and inserting elements in the beginning as well.

_images/deque.png

Similarly to queues, they are easy to implement with mutable doubly-linked lists or with resizable circular buffers.

In some standard libraries:

  • ​ In Scala, the Queue class uses resizable circular buffers, provided in the deque ArrayDeque class, to implement queues. The class ArrayDeque in turn implements deques with circular buffers.

  • ​ In the C++ standard library, queues are implemented either with doubly-linked lists (the list class) or with a two-level indexing structure allowing also constant time access in the queue elements (the deque class).

  • ​ In Java, the deque interface Deque can be implemented in multiple ways, for instance with linked lists (the LinkedList class) or with resizable circular buffers (the ArrayDeque class). The same applies to the queue interface Queue.