Queues are a abstract data type (ADT) where the elements that are first to be inserted are also the first to be removed (first-in-first-out, FIFO). They have two fundamental operations:

  • enqueue(n): adds an element to the end of the queue.
  • dequeue(): removes the element from the front of the list.
  • peek(): gives us the first element in the queue.

An additional variation on regular queues are deques (or double-ended queues). They support insertion and deletion at both the front and back of the queue (like a mix between a queue and stack). Priority queues store the elements according to a priority value.

In software, queues are commonly implemented with dynamic arrays or linked lists.

In hardware

Hardware components have a type of buffer memory called a First-In First-Out (FIFO) memory, especially for streaming in packets from IO devices. The mechanism behind accessing FIFO registers are simple: the FIFO has a fixed, finite size, when we write it enqueues a packet and when we read it dequeues a packet.

This can be implemented in practice with a circular FIFO, similar to a circular queue. The read and write operations wrap around to the beginning, and we make use of a read and write pointer. See this post.

Language-specific

In C++

Queues are provided as part of the STL as std::queue<T>.

Some useful methods:

  • front() and back() returns the first and last element in the queue.
  • push() inserts an element at the end of the queue.
  • pop() dequeues the first element.

See also

  • Stack, the last-in-first-out equivalent