19. 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 mechanisms we used in the previous chapter with stacks: linked lists or arrays. 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. As we did with stacks, we’ll take a look at more than one implementation.
19.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.
19.2. Implemeting queues with linked lists¶
If you successfully completed all the exercises in Chapter 17 Exercise Set 1: Templates, then just as with Implemeting stacks with linked lists, you have already written an implementation of the queue ADT.
#include "LinkedList.h"
template <class T>
class Queue : public LinkedList<T>
{
public:
// constructors
Queue() = default;
// modifiers
void insert(T item) {
LinkedList<T>::insert_at_end(item);
}
T remove() {
return LinkedList<T>::remove_from_front();
}
bool empty() {
return (LinkedList<T>::length() == 0);
}
};
Just as we did in Implementing stacks by wrapping a list, we could implement our queue by wrapping linked lists. We’ll leave this to you to do as an exercise.
19.3. Array implementation of the Queue ADT¶
Implementing queues with an array presents a new challenge we did not face when implementing stacks. Queues add elements to one end of the linear data structure and remove them from the other. If we add elements to the end of the array, the FIFO discipline requires that we remove them from the beginning (so that the first in becomes the first out.
This has the effect of “moving” the queue through the array, and “wrapping” the end around to the beginning as space becomes available. There are several ways to address this. We could shift all the items over one whenever an item is removed (or added). You be asked to do this in the exercises.
Alternatively, we can us the modulus operator to create a circular buffer, as in the following implementation.
#ifndef QUEUE_H
#define QUEUE_H
#define MAX_SIZE 1024
#include <stdexcept>
template <class T>
class Queue {
int first;
int last;
T items[MAX_SIZE];
public:
Queue() {
first = 0;
last = 0;
}
void insert(const T& value) {
if ((last + 1) % MAX_SIZE == first) {
throw std::overflow_error("No more space in queue");
}
items[last] = value;
last = (last + 1) % MAX_SIZE;
}
T remove() {
if (empty()) {
throw std::underflow_error("Can't remove from empty queue");
}
int oldfirst = first;
first = (first + 1) % MAX_SIZE;
return items[oldfirst];
}
bool empty() const {
return first == last;
}
};
#endif // QUEUE_H
You should trace the execution of this implementation until you convince
yourself you understand how it works. It will be helpful to reduce
MAX_SIZE to something more manageable, say 10, while you do that.
You’ll be asked to do just that as an exercise.
19.4. The priority queue ADT¶
As mentioned, the priority queue ADT has the same application programming
interface (API) as the queue does. What is different is the queueing
discipline. In a priority queue each item is inserted into the queue in
such a way that the items with the highest priority leave the queue before
those with lower priority. This priority can be based on anything as long as
the items are comparable,
meaning the comparision operators (<, >, <=, and >=) can be
used with them. In a sense, a regular queue is a priority queue in which the
priority is time in the queue.
You have all the programming skills you need now to implement priority queues on your own, and you will be asked to do so in the exercises.
19.5. Big-O notation¶
We’ve seen different implementations of both the stack and queue ADTs. In each implementation we have used different algorithms to implement an API supporting the ADT (see Abstract data types and Implementing APIs from last chapter).
An important question we have not considered until now is how these implementations differ in how fast they execute on our computer and how much memory they require. It turns out the differences can be huge, and the study of the relative effeciency of different algorithms is a central part of computer science.
We are interested in this study of efficiency in how time (and space) vary as the size of our data varies. The focus is on what happens as the input data set grows really large. With small input data size, differences in efficiency don’t matter much.
Big-O is a mathematical way to describe algorithmic efficiency and to classify algorithms into categories.
Given functions \(f(n)\) and \(g(n)\), \(f(n)\) is \(O(g(n)\) if there exist constants \(c\) and \(k \in \mathbb{N}\) such that
for all \(n >= k\). We say “\(f\) is big-O of \(g\)”.
The following table lists the most common Big-O categories along with an example from some of the algorithms we’ve used.
Notation |
Name |
Example |
|---|---|---|
\(O(1)\) |
constant |
Accessing an element in an array |
\(O(\log n)\) |
logarithmic |
Finding an element in an ordered array using binary search |
\(O(n)\) |
linear |
Accessing an element in a linked list |
\(O(n \log n)\) |
linearithmic or loglinear |
Mergesort |
\(n^2\) |
quadratic |
bubble sort |
The \(n\) in \(O(n)\) refers to the input data size. The development of electronic computers was motivated in part by the need to handle large data sets too big to be processed effectively by human “computers”. Large inputs are common, so it is important for computer scientists to understand how algorithms behave with them.
To give you a better feel for this, consider an array with 1,099,511,627,776 (that’s one trillion, ninety-nine billion, five hundred eleven million, six hundred twenty-seven thousand, seven hundred seventy-six in case you were interested) elements. Adding an element onto this array or accessing any of its elements can be done in \(O(1)\), or constant time. If the array contains ordered comparable data, finding an element in the array can be done in \(O(log\ n)\), or on the order of about 40 operations.
Note
When we use \(log\ n\) in this context we are refering specifically to the binary logarithm or \(log_2\) (log base 2). Since we are using binary digital computers it is convenient to do this.
Finding an element in an unordered array takes \(O(n)\) or linerar time, on the order of a trillion operations. And sorting the array using the best possible algorthms takes \(O(n\ log\ n)\) or on the order of 44 trillion operations, while using an inefficient bubble or insertion sort takes on the order of \(O(n^2)\) or a bit over a septillion operations.
19.6. 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.
- 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 an array and indices of the first element and the next available space.