The Self-Taught Computer Scientist

12Queues

All students should have the opportunity to learn how to program. Computer science is the basis for modern day creativity and expression. The computer programmers of tomorrow will revolutionize medicine.

Anne Wojcicki

A queue is an abstract data type and a linear data structure where you can add items only to the rear and remove them from the front (Figure 12.1). The queue abstract data type describes a data structure that works like the checkout lines at a grocery store: the first person in the line is the first person to check out, and newcomers join the line's rear.

Figure 12.1 In a queue, you add items to the rear and remove them from the front.

A queue is an example of a first-in, first-out (FIFO) data structure. As the name implies, in a first-in, first-out data structure, the first item to enter the data structure is the first to come out of it. Queues, like stacks, are limited access data structures.

Queues have two primary operations: enqueueing and dequeueing (Figure 12.2). Enqueueing means adding an item to a queue, whereas dequeueing means removing an item. You enqueue elements to the rear of a queue and dequeue them from the front.

Figure 12.2 The primary operations of queues are enqueueing and dequeueing.

There are several different ways to ...