A queue is a data structure that is first in first out (FIFO). This resembles most closely to an actual queue. A queue will generally contain a pointer to the back of the queue, where elements are added, called the tail. It will also generally have a pointer to the front of the queue where elements are dequeued, called the head.
Implementation
Queues can be implemented using a circular array, or with a linked list.
As long as the singly linked list has a tail/head pointer, it can be implemented efficiently with a singly linked list and enqueue and deque operations will be constant time. The correct implementation for constant time at both ends is to have the front of the queue be at the head of the list.
Queues generally support the following, the first two are mandatory:
- enqueue - insert item at the back of the queue
- dequeue - remove an item from the front of the queue
- peek
- is_empty