21. Queues and priority queues¶
This chapter presents two ADTs: Queues and Priority Queues. In real life a queue is a line of customers waiting for service of some kind. In most cases, the first customer in line is the next customer to be served. There are exceptions, though. For example, at airports customers whose flight is leaving imminently are sometimes taken from the middle of the queue. Also, at supermarkets a polite customer might let someone with only a few items go first.
The rule that determines who goes next is called a queueing discipline. The simplest queueing discipline is called FIFO, for “first-in-first-out.” The most general queueing discipline is priority queueing, in which each customer is assigned a priority, and the customer with the highest priority goes first, regardless of the order of arrival. The reason this is the most general discipline is that the priority can be based on anything: what time a flight leaves, how many groceries the customer has, or the percieved importance or power of the customer. Of course, not all queueing disciplines are “fair,” but fairness is in the eye of the beholder.
The Queue ADT and the Priority Queue ADT have the same set of operations and their interfaces are the same. The difference is in the semantics of the operations: a Queue uses the FIFO policy, and a Priority Queue (as its name suggests) uses the priority queueing policy.
As with most ADTs, there are a number of ways to implement queues. Since a queue is a collection of items, we can use either of the basic mechanisms we have been using for storing collections: vectors or linked lists. Choosing between them should be based in part on their performance – how long it takes to perform the operations we want to perform – and partly on ease of implementation.
21.1. The queue ADT¶
The queue ADT is defined by the following operations:
- new
Create a new, empty queue.
- insert
Add a new item to the queue.
- remove
Remove and return an item from the queue.
- empty
Check whether the queue is empty.
21.2. Glossary¶
- queue¶
An ordered set of objects waiting for a service of some kind.
- queueing discipline¶
The rules that determine which member of a queue is removed next.
- FIFO¶
“first in, first out”, a queueing discipline in which the first member to arrive is the first to be removed.
- priority queue¶
A queueing discipline in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed.
- Priority Queue¶
An ADT that defines the operations that can be performed on a priority queue.
- veneer¶
A class definition that implements an ADT with function definitions that are invocations of other functions, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.
- performance hazard¶
A danger associated with a veneer that some of the functions might be implemented inefficiently in a way that is not apparent to the client.
- constant time¶
A operation whose run time does not depend on the size of the input data.
- linear time¶
An operation whose run time is a linear function of the size of the input data.
- linked queue¶
An implementation of a queue using a linked list and pointers to the first and last nodes.
- circular buffer¶
An implementation of a queue using a vector and indices of the first element and the next available space.