Queue (First-In-First-Out)

Just like a stack, a queue is simply a list data structure with a constrained set of methods that make it uniquely suited for some programming tasks. These methods are enqueue, which adds an item to the end of the list and dequeue which removes and returns the item in the head position. Think of a queue like a line to get into a night club. New people are added to the end of the queue and people are removed from the front of the queue as they are let in to enjoy a night of dancing. In software parlance, a queue is known as a First-in-First-Out data structure because the first item added to the queue is the first one out (clever, huh?).

Typically, a Linked List is used when implementing a queue. However, an Array is also a viable option. The reader is encouraged to examine the accompanying code to get a better understanding of how queues work.

Applications

  • Job Scheduling: A print driver maintains a queue of print jobs and sends them to the printer as it is available.
  • Buffering: Streaming video and audio applications typically maintain a buffer of content to compensate for erratic connections.
  • CPU Scheduling: A thread can place a job on a queue to be picked by another thread. Caveat: This requires the queue to be synchronized. Multi-threading concepts are covered in other sections.

Asymptotic Complexity

  • Enqueue: $O(1)$
  • Dequeue: $O(1)$

Pseudo Code

enqueue:
    Add item to the end of the list

dequeue:
    Remove item from the head of the list and returns it

peek:
    Return item from the head without removing it from the list

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions