Chapter 5. Queues: FIFO Collections

A queue is an abstract data structure that serves as a linear collection of objects that are inserted and removed based on the first-in first-out (FIFO) principle. The two most notable operations of a queue are enqueue, which adds objects to the tail or back of the collection, and dequeue, which removes objects from the head or front of the collection. The following figure demonstrates the queue data structure as well as these two basic operations. Other common operations include peek, empty, and full, all of which will be examined later in this chapter:

Queues are very similar to stacks and they share some of the same functionality. Even two of their primary operations are very similar, just implemented on opposite principles. Like a stack, a queue can be either array-based or linked list-based, and the linked list based version is more efficient in most cases. However, unlike a stack, which can be sorted or unsorted, a queue is not intended...