Beginning Algorithms

Chapter 4. Queues

Queues are an essential part of algorithms that manage the allocation and scheduling of work, events, or messages to be processed. They are often used as a way of enabling different processes—either on the same or different machines—to communicate with one another.

In this chapter, you will learn the following:

• How queues differ from lists

• Characteristics and implementation of a first-in-first-out (FIFO) queue

• How to create a thread-safe queue

• How to create a bounded queue—one with a maximum size limit

• How to combine all of these queue types to build a multi-threaded simulation of a call center to see just how queues can be put to use

Understanding Queues

Customers line up in a bank waiting to be served by a teller and in supermarkets waiting to check out. No doubt you've been stuck waiting in a line to speak to a customer service representative at a call center. In computing terms, however, a queue is a list of data items stored in such a way that they can be retrieved in a definable order. The main distinguishing feature between a queue and a list is that whereas all items in a list are accessible—by their position within the list—the only item you can ever retrieve from a queue is the one at the head. Which item is at the head depends on the specific queue implementation.

More often than not, the order of retrieval is indeed the same as the order of insertion (also known as first-in-first-out, or FIFO), but there are other possibilities as well. Some of the more common ...