Queues are abstract data structures that are meant to emulate the workings of real life queues. They are used extensively in various applications, such resource allocation, scheduling, sorting, and many others. They are typically implemented using a double linked list, although many other implementations exists. A queue usually consists of two operations; an enqueue operation, where items are added to the rear of the queue, and an opposite dequeue operation, where items are removed from the front of the queue. These two operations make the mode of operation of this data structure First In First Out (FIFO).

We can implement an efficient queue using a double linked list. This enables us implement the dequeue operation by removing an item from the head of the linked list. enqueue is simply adding an item to the tail of the linked list. Figure 2.8 shows how the two operations are performed:

To dequeue an item using a double linked list as a base data structure, we just need to move the head to the next item in the list and unlink the old head by pointing the previous pointer to nothing. Enqueuing at the tail is a three-step process. Point the new node's preceding pointer to the current tail, then point the current tail's next pointer to the new node, and finally moving the tail to the new node. The pseudocode for both of these operations is shown in the following code snippet:

dequeue(head)
  if (head != null)
    node = head
    head = head.next
    if (head != null) head.previous = null
    return node.value
  return null
enqueue(tail, item)
  node = new Node(item)
  node.previous = tail
  if (tail != null) tail.next = node
  if (head == null) head = node
  tail = node