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()andback()returns the first and last element in the queue.push()inserts an element at the end of the queue.pop()dequeues the first element.
In C
On BSD, Unix, and Linux systems, queue structs and functions are provided in the queue.h header. STAILQ refers to a singly-linked tail queue, and TAILQ refers to a doubly-linked tail queue. Both are in practice implemented with the SLIST and LIST utilities defined in the same header file.
See also
- Stack, the last-in-first-out equivalent