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
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.
- 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.
- Enqueue: $O(1)$
- Dequeue: $O(1)$
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
Click here for build and run instructions