Data Structures and Algorithms with C · Lecture Notes
Chapter 7: Queues
A stack inserts and removes at the same end, so the last item in is the first one out. Most lines in everyday life work the opposite way: at a bank counter, in a cafeteria, or at a printer, whoever arrives first is served first. A data structure that obeys this rule is called a queue. A new item enters at the rear, and the next item to be processed leaves from the front. These notes first define the queue as an abstract data type. They then build the simplest array implementation and use a code trace to expose its "false full" problem. The cure is the circular queue: the end of the array is treated as if it were joined to its beginning, and indices wrap around with the remainder operator. The remaining topics are three ways to tell a full circular queue from an empty one and the queue built on a linked list. The last section covers the double-ended queue, round-robin scheduling as used by operating systems, and how to build a queue from two stacks.
Learning outcomes
- The first-in-first-out rule
- Define a queue as Q = {a0, …, an−1}, identify its front and rear ends, and list the operations of the queue abstract data type together with their error conditions.
- The problem with the linear queue
- Explain why cells vacated at the front of an array-based linear queue cannot be reused, and compute the cost of the shifting remedy.
- Circular queue
- Wrap indices with
% MAX, compute the item count and a step backward correctly, and distinguish a full queue from an empty one in three ways. - Linked queue
- Enqueue and dequeue in O(1) time with
frontandrearpointers, handling the first insertion into an empty queue and the removal of the last item without memory errors. - Deque and applications
- Implement a double-ended queue in a circular array, use a queue for time-sliced job scheduling, and build a queue from two stacks and justify its amortized cost.
7.1What is a queue?
Stacks and queues are the two basic structures that deliberately restrict access to a collection of items. In both, only the item at one particular end can be reached; the items in the middle stay out of sight. This restriction is not a shortcoming. The narrower the access rule, the simpler and faster the structure is to implement, and the easier it is to predict how a program behaves. The only thing that separates the two structures is which item gets removed. In a stack it is the item inserted last. In a queue it is the item that has waited longest, that is, the one inserted first.
7.1.1First in, first out
A line at a bus stop is the simplest example of a queue. A newcomer steps to the end of the line. When the bus arrives, the passenger at the head of the line boards. Cutting into the middle of the line or pulling someone out of it breaks the rule. Passengers board in exactly the order in which they joined the line, and the queue data structure reproduces this behavior faithfully.
A queue is an ordered list in which insertion takes place at one end and deletion at the other. In a queue Q = {a0, a1, …, an−1}, the element a0 is at the front and an−1 is at the rear. For every i, ai was inserted before ai+1. A new element is inserted at the rear, and removal always takes place at the front. This rule is called first in, first out (FIFO).
The last sentence of the definition determines the entire behavior of a queue. If elements enter the queue in the order a0, a1, a2, they leave in the same order. A stack given the same insertion order would produce the reverse removal order, a2, a1, a0, which is why the stack rule is called last in, first out (LIFO). In short, a stack reverses the order and a queue preserves it.
Figure 7.1 shows the items A, B, C, and D being added to an empty queue in that order, followed by one removal. In an empty queue, front and rear are at the same place and there are no items between them. Each insertion moves the rear one cell forward. The removal returns A, which stands at the front because it entered first. Once A has left, the front cell is vacated and B becomes the new front. One detail in the figure deserves attention: removal does not move the remaining items. The front end advances one cell to the right while the items stay where they are. This detail is the source of every problem, and every solution, of the array-based queue.
7.1.2The queue abstract data type
Before implementing a data structure, we must decide which operations will be performed on it and what each operation means. This specification is independent of the internal layout of the structure. A program that uses a queue need not know whether the items sit in an array or in a linked list; it only needs to know that insertion and removal obey the first-in-first-out rule. Giving the operations in this way, separately from any implementation, is called an abstract data type (ADT). Table 7.1 lists the six operations of the queue ADT.
| Operation | Meaning | Error condition |
|---|---|---|
queue_create(max) | Creates an empty queue that can hold at most max items. | — |
queue_full(Q) | Returns true if no room is left in the queue. | — |
enqueue(Q, x) | Adds x at the rear of the queue. | Overflow if the queue is full. |
queue_empty(Q) | Returns true if the queue holds no items. | — |
dequeue(Q) | Removes the front item from the queue and returns it. | Underflow if the queue is empty. |
queue_front(Q) | Reads the front item without removing it. | Error if the queue is empty. |
The names of the two error conditions in the table are familiar from the stack. Trying to insert into a full structure causes an overflow, and trying to take an item from an empty one causes an underflow. The notion of "full" is meaningful only for fixed-size implementations: a queue built on a linked list does not fill up until memory runs out. Even so, the abstract data type includes the queue_full operation, so that the same interface covers both the array and the linked-list implementation.
The difference between a stack and a queue fits into one word in the table: end. A stack has a single active end, and both insertion and removal take place at the top. A queue has two ends, and each operation uses its own: insertion at the rear, removal at the front. The difference shows up in the implementation as well. A single index (top) suffices to manage a stack, whereas a queue needs two indices, one tracking the front and the other the rear. The position of these two indices relative to each other is the real subject of the rest of these notes.
7.1.3Where queues are used
Queues appear wherever the principle "whoever's turn it is gets served" applies. Some of the uses are computer counterparts of real-life lines, and others sit inside the workings of algorithms.
- Operating systems. Processes that are ready to run wait in a queue for the processor, documents sent to a printer wait for the printer, and disk requests wait for the disk. It would be unfair if a later request could overtake the ones ahead of it; a queue provides this fairness automatically.
- Buffers. Keystrokes from the keyboard, packets from the network, and samples headed for the sound card wait in a buffer. A buffer is a queue that sits between the party that produces data and the party that consumes it. The two sides may run at different speeds: a keyboard can send several keys at once, and the program reads them a moment later. Such buffers are almost always fixed-size circular queues.
- Breadth-first search. Breadth-first search (BFS), which visits the nodes of a graph or tree in order of their distance from the start, rests on a queue. The neighbors or children of the node being processed are added at the rear of the queue, and the next node is taken from the front. In a tree the same method yields the nodes level by level, from left to right; this traversal is called level-order traversal.
- Simulation. When a bank counter, a traffic light, or a production line is simulated on a computer, every arriving customer or vehicle joins a queue. A simulation answers questions such as the average waiting time without building the real system.
- Message queues. In large software systems, servers pass jobs to one another through a message queue. Jobs are processed in the order in which they were sent, and they are not lost even if the receiver is busy at that moment.
One often confused structure must be added to this list. The name of the priority queue contains the word "queue", but it does not obey the first-in-first-out rule. In a priority queue every item has a priority, and each removal takes the item with the highest priority. The line in an emergency room is a good example: a seriously ill patient goes ahead of mildly ill patients who arrived earlier. A priority queue is implemented efficiently with a tree structure called a heap. In these notes the word "queue", unless stated otherwise, means the ordinary queue that obeys the first-in-first-out rule.
The slides also contain an interactive queue. There the "add" button puts a new item at the rear of the queue and the "remove" button takes out the front item. After a few trials the same observation is confirmed over and over: the items come out in the same order in which they went in. For a stack, this order was exactly the reverse.
7.2Linear queue in an array
The shortest way to build a queue in C is to use a fixed-size array and two integer indices. This section first gives that simplest implementation. It then uses a code trace to expose an important flaw, and examines the first, expensive way of removing the flaw.
7.2.1Representation and C code
A single top index was enough for the stack. A queue has two ends, so two indices are kept: front and rear. The items lie side by side in the array, from the cell after front up to the cell that rear points to. The code below is the implementation in the book by Horowitz, Sahni, and Anderson-Freed:
#define MAX_QUEUE_SIZE 100
element queue[MAX_QUEUE_SIZE];
int front = -1; /* one before the first item */
int rear = -1; /* last item */
void enqueue(int *rear, element item) {
if (*rear >= MAX_QUEUE_SIZE - 1) /* any room? */
queue_full(); /* warn and exit */
queue[++*rear] = item; /* bump, then store */
}
element dequeue(int *front, int rear) {
if (*front == rear)
queue_empty(); /* warn and exit if empty */
return queue[++*front]; /* bump, return the front */
}The first lines set up the memory of the queue. MAX_QUEUE_SIZE is the number of cells in the array. element is the type of the items stored in the queue. As in the stack implementation, this type is defined as a struct to suit the program; for example, it may carry a single int value field. The queue array and the two indices are global variables. Both indices start at −1.
The meaning of the two indices must be read carefully, because all of the code depends on it. rear points to the cell that holds the last item. front, however, points not to the first item but to the cell one before the first item. At first sight this choice looks odd, but it gives both operations the same shape: each first advances its own index and then uses that cell. The items of the queue therefore lie in cells queue[front+1], …, queue[rear], and the item count is rear − front. If the two indices are equal, the range is empty: the condition for an empty queue is front == rear. The initial values −1 and −1 satisfy this condition as well.
enqueue first checks whether there is room. If rear has reached the last cell of the array (MAX_QUEUE_SIZE − 1), no cell is left behind it and queue_full is called. If there is room, ++*rear first increments rear, and the value of the expression is the incremented index; the item is written into that cell. dequeue first checks for emptiness. If the queue is not empty, ++*front advances the front index to the cell of the item to be removed, and the item in that cell is returned.
The parameter types are chosen deliberately. Because enqueue changes rear, it takes it by address, as int *rear; the call has the form enqueue(&rear, x). dequeue, on the other hand, changes front and only reads rear, so it takes front by address and rear by value. The parameter names are the same as the names of the global variables. This is legal in C: inside the function, the parameter name shadows the global variable. When reading the code, remember that *rear stands for the global rear, while a bare rear stands for the parameter's copy.
On an error, the code calls the functions queue_full and queue_empty. Like their counterparts in the stack implementation, these print a warning and terminate the program:
void queue_full(void) {
printf("Queue is full!!!\n"); exit(-1);
}
void queue_empty(void) {
printf("Queue is empty!!!\n"); exit(-2);
}Terminating the program is crude error handling, but it keeps the code short and puts the main idea in the foreground at the first stage of learning. Once the queue is full or empty, the operation does not continue; therefore enqueue and dequeue need no separate branch for what happens after the error. Safe versions return false on error and leave the decision to the caller. That version is treated in the section on the circular queue.
Each operation performs one comparison, one increment, and one array access. Since a constant amount of work is done regardless of how many items the queue holds, the time cost of both operations is O(1). The queue uses a fixed-size array; the memory cost is MAX_QUEUE_SIZE items and does not depend on the item count.
Writing queue[*rear++] instead of queue[++*rear]. Because the postfix ++ operator has higher precedence, the expression *rear++ reads as *(rear++). This advances the pointer itself rather than the integer that rear points to. The global rear does not change, and the item is written into the wrong cell. The prefix form ++*rear first reaches *rear and then increments it. Wherever the precedence is in doubt, writing ++(*rear) is the safest course.
7.2.2Code trace: false full
The flaw of the linear queue becomes visible after a few steps of the code. In the trace the array is kept small: MAX_QUEUE_SIZE = 4. Initially front = rear = −1. The sequence of operations is as follows: A, B, and C are added; two items are removed; then D and E are added. Because the items are single letters, element can be thought of as char in the trace.
| Operation | Check | front | rear | Array [0..3] | Result |
|---|---|---|---|---|---|
| Start | — | −1 | −1 | . . . . | Empty |
enqueue(&rear, 'A') | −1 ≥ 3? No | −1 | 0 | A . . . | queue[0] = A |
enqueue(&rear, 'B') | 0 ≥ 3? No | −1 | 1 | A B . . | queue[1] = B |
enqueue(&rear, 'C') | 1 ≥ 3? No | −1 | 2 | A B C . | queue[2] = C |
dequeue(&front, rear) | −1 == 2? No | 0 | 2 | . B C . | returns A |
dequeue(&front, rear) | 0 == 2? No | 1 | 2 | . . C . | returns B |
enqueue(&rear, 'D') | 2 ≥ 3? No | 1 | 3 | . . C D | queue[3] = D |
enqueue(&rear, 'E') | 3 ≥ 3? Yes | 1 | 3 | . . C D | "Queue is full!!!", the program ends |
The first three insertions go smoothly. In each, the check says there is room, rear grows by one, and the letter is written into the new cell. In the two removals front advances first to 0 and then to 1, and A and B are returned in turn. What matters here is that removal does not change the array. A and B are still written in cells 0 and 1, but they are no longer part of the queue: the queue starts at front+1. These two cells are in effect empty.
When D is added, rear reaches 3, the last cell of the array. The queue holds only two items (C and D); the item count is rear − front = 3 − 1 = 2. Nevertheless, when E is to be added, the check gives 3 ≥ 3 and the code regards the queue as full. The program prints "Queue is full!!!" and ends, although two of the four cells are empty. This situation is called false full. Its cause is that both indices only move forward. As front advances, the cells it leaves behind are never used again. A linear queue can perform a total of MAX_QUEUE_SIZE insertions over its lifetime, no matter how many items it holds at any one time. For example, if 60 items are added to a 100-cell queue and all 60 are removed, the queue is empty. Even so, at most 40 more insertions fit; the 41st insertion raises a "full" error.
rear = 2. After two removals, front = 1; A and B are drawn faded because they no longer belong to the queue. When D is added, rear = 3, and the next insertion counts as full even though cells 0 and 1 are empty.Mistaking the condition rear == MAX_QUEUE_SIZE − 1 in a linear queue for true fullness. This condition only means "no room is left at the rear". The number of items actually in the queue is found with rear − front, and it may be very small. The queue is truly full only if rear has reached the end while front == −1.
7.2.3Shifting: the expensive fix
The first fix that comes to mind for false full is to shift the items to the beginning of the array. When rear reaches the end and there are empty cells at the front, all items are moved to the left, front is pulled back to −1, and rear to one less than the item count. Figure 7.3 starts from the final state of the trace: front = 1, rear = 3, items C and D. After shifting, C moves to cell 0 and D to cell 1; front = −1, rear = 1, and two cells open up at the rear.
front = 1, rear = 3 looks "full", although there are two empty cells at the front. Middle: every item is moved once toward the start. Bottom: front = −1, rear = 1, and room has opened up at the rear.Adding shifting to the queue code is easy. The two functions below operate on the global queue, front, and rear of the previous section:
void shift_left(void) { /* move items to the start */
int n = rear - front; /* item count */
for (int i = 0; i < n; i++)
queue[i] = queue[front + 1 + i];
front = -1;
rear = n - 1;
}
void enqueue_shift(element item) {
if (rear == MAX_QUEUE_SIZE - 1) {
if (front == -1) queue_full(); /* truly full */
shift_left(); /* room at front: O(n) */
}
queue[++rear] = item;
}shift_left first computes the item count (n = rear − front). The loop moves the i-th item, the one in cell queue[front+1+i], to queue[i]. The moves go from left to right; because the destination cell is always to the left of the source cell, no item that has not yet been read is overwritten. The last two assignments pull the indices to the new position. enqueue_shift comes into play only when rear has reached the end. If front is also −1 at that moment, there is no empty cell at the front and the queue is truly full. Otherwise it shifts first and then inserts the item as usual. Testing this version, the state in the trace (C, D; front = 1, rear = 3) becomes front = −1, rear = 1 after shifting. E and F then fit, while G is rejected because the queue is truly full.
The solution is correct, but its price is high. Shifting moves each of the n items in the queue once, so its cost is Θ(n). Shifting is not performed at every insertion, only when rear has reached the end. However, if the queue runs almost full all the time (the normal situation for a buffer), nearly every insertion triggers a shift. Suppose the queue holds M − 1 items and one insertion and one removal are performed in succession. Each removal opens a single cell at the front. At the next insertion rear again hits the end, and M − 1 items are moved. Thus insertion goes from O(1) to O(n).
This estimate was also confirmed by measurement. With the queue holding M − 1 items at all times, 200,000 insertion–removal pairs were performed. For M = 1000 the total number of moves is 199,799,001, and for M = 2000 it is 399,798,001; that is, about M items were moved per insertion. The times are given in Table 7.15: the running time of the shifting queue grows in proportion to M, while that of the circular queue stays constant. In the slides this is put in the words of the instructor: shifting is the name of high cost in computer science. The way to escape shifting is to leave the items where they are and let the indices go around. This structure is called the circular queue.
7.3Circular queue
The problem of the linear queue is that the indices stop when they reach the end of the array. The circular queue removes this limit: after the last cell, the index goes back to the first cell. The cells vacated at the front are thus used for items added at the rear, and no item is ever moved from its place. This section takes up, in turn, the idea, the remainder operation that makes it possible, the code, and the problem of telling a full circular queue from an empty one.
7.3.1Joining the end of the array to its beginning
Imagine an array of six cells as a ring instead of a flat strip. The cells, numbered 0 to 5, are the slices of the ring, and cell 5 is followed directly by cell 0 again. Nothing changes in memory; the array is still a flat block. Only the rule by which the indices advance changes. Figure 7.4 shows this ring: the queue holds A, B, and C, front points to 0, and rear points to 3.
front = 0 and rear = 3; the queue holds A, B, and C in cells 1, 2, and 3. After cell 5 comes 0.A circular queue is a queue implementation in an array of MAX cells in which the indices return to 0 after MAX − 1. The indices advance with rear = (rear + 1) % MAX and front = (front + 1) % MAX. As in the linear queue, front points to the cell one before the first item and rear points to the last item; initially front = rear = 0. The queue is empty when front == rear and full when (rear + 1) % MAX == front.
The full condition in the definition says: if advancing rear by one would land on front, there is no room. One consequence of this condition is that one of the MAX cells always stays empty. The queue holds at most MAX − 1 items. Why this is so, that is, why the last cell is not filled, is the subject of the problem of telling full from empty. For now it is enough to note this: if the last cell were filled as well, rear would be equal to front. That is the same as the condition for an empty queue, and the code would mistake a full queue for an empty one.
7.3.2Modular arithmetic and wrap-around
The tool that lets an index go around the ring is C's remainder operator %. The expression a % m gives the remainder of dividing a by m. For non-negative a, the result always lies between 0 and m − 1. Computing with numbers by their remainders modulo some m is called modular arithmetic. A clock is the most familiar example: three hours after 11 o'clock is not 14 but (11 + 3) mod 12 = 2.
In a circular queue the next value of rear is computed as (rear + 1) % MAX. If rear is not in the last cell, this expression is the same as the ordinary rear + 1. If rear is in the last cell, then rear + 1 = MAX and the remainder is 0: the index returns to the start. This event is called wrap-around. Table 7.3 gives four consecutive steps for MAX = 6.
rear | rear + 1 | (rear + 1) % 6 | Meaning |
|---|---|---|---|
| 3 | 4 | 4 | normal advance |
| 4 | 5 | 5 | last cell |
| 5 | 6 | 0 | wrap-around: back to the start |
| 0 | 1 | 1 | normal advance again |
There is a C-specific trap with the remainder operator. The C standard (since C99) truncates integer division toward zero. As a result, the remainder of a negative number is also negative: the value of -1 % 6 is −1, not 5, and -2 % 6 is −2. The mathematical mod operation always gives a non-negative result; C's % operator does not. This difference matters when an index has to be taken one step backward. The expression (i − 1) % MAX gives −1 for i = 0, and queue[-1], outside the array, would be accessed. The correct form is (i − 1 + MAX) % MAX. Adding MAX keeps the value from being negative, and the remainder operation brings the result back into the range 0 to MAX − 1: (0 − 1 + 6) % 6 = 5. In a queue an index only moves forward; a step backward is needed in the double-ended queue, which works from both ends.
The second use of modular arithmetic is finding the item count. In the linear queue the item count was rear − front. In a circular queue rear can wrap around and fall behind front; then the difference is negative. The same correction works here:
Let MAX = 6, front = 4, and rear = 1. The item count is (rear − front + MAX) % MAX = (1 − 4 + 6) % 6 = 3 % 6 = 3. The items are counted from the cell after front up to rear, taking the wrap-around into account: cells 5, 0, and 1. The difference rear − front would give −3, which would be wrong. If front and rear are equal, the formula gives 0, which agrees with the condition for an empty queue.
7.3.3Wrap-around with A…F
To see step by step how wrap-around works in a queue, consider a circular queue of six cells. Initially front = rear = 0. A, B, C, D, and E are added in turn. In each insertion, rear advances first and then the item is written into the new cell. This is why A goes into cell 1, not cell 0. After E is added, rear = 5 and cell 0 is empty.
If one more insertion were attempted at this point, the value (5 + 1) % 6 = 0 would equal front and the queue would count as full. Six cells hold five items; one cell is left empty on purpose. Next, A is removed: front = (0 + 1) % 6 = 1 and A is returned. Now cells 0 and 1 are both empty. Then F is added. rear = (5 + 1) % 6 = 0, and F is written into cell 0, which was vacated at the front. The cell that the linear queue could not use is used here as if it lay at the rear. The queue is full again: (0 + 1) % 6 = 1 = front. The queue holds B, C, D, E, and F, and their order is preserved. The next removal returns B, because front advances from 1 to 2.
front = rear = 0); A…E added (rear = 5); A removed (front = 1); F written into cell rear = (5 + 1) % 6 = 0. In the final state the queue is full: five items in six cells.7.3.4C code and a subtle point
The code of the circular queue differs from that of the linear queue in only two places: the indices advance with % MAX_QUEUE_SIZE, and the full condition changes. The version below again follows the implementation in the book by Horowitz, Sahni, and Anderson-Freed:
void enqueue(int front, int *rear, element item) {
*rear = (*rear + 1) % MAX_QUEUE_SIZE; /* advance */
if (front == *rear) queue_full(); /* full? */
queue[*rear] = item; /* store */
}
element dequeue(int *front, int rear) {
if (*front == rear) queue_empty(); /* empty? */
*front = (*front + 1) % MAX_QUEUE_SIZE; /* advance */
return queue[*front]; /* return */
}enqueue now takes front as a parameter as well, because the full condition depends on front. The function first advances *rear by one with wrap-around. If the advanced rear equals front, the queue is full and queue_full is called. Otherwise the item is written into the new cell. As in the linear version, dequeue first checks for emptiness, then advances *front with wrap-around and returns the item in that cell. Both functions perform a constant number of operations and move no item; the cost of each is O(1).
The subtle point in this code is that enqueue advances *rear first and checks for fullness afterward. If the queue is full, *rear has already been set equal to front. In the version in the slides this does no harm, because queue_full terminates the program and the corrupted value is never used again. The problem appears when one writes a version that does not terminate on error but only prints a warning and returns. After an attempted insertion into a full queue, front == rear holds and the queue looks empty. All the items in it have vanished at once. This behavior was confirmed with a small experiment: after A…E were added to a six-cell queue (front = 0, rear = 5), an insertion of F was attempted. After the warning was printed and the function returned, rear = 0 and front == rear; the queue looked empty.
The implementation in the book therefore restores rear to its old value when the queue is full. A cleaner way is to compute the new position first in a temporary variable and change rear only once it is certain that there is room. This approach is an instance of a general principle: an operation that can fail must not modify the data structure when it fails.
In the slides this slide appears next to a saying of the instructor. The saying says that studying at a good university is not a guarantee but a responsibility: a student should work knowing that failure means being expelled. The same attitude applies when writing code. It is not enough for code to "usually work"; edge cases such as insertion into a full queue must also be thought through deliberately.
7.3.5The safe version and a code trace
The version below does not terminate the program. It returns false on error and true on success and leaves the decision to the caller. dequeue delivers the removed item not through its return value but through an output parameter (element *x), because the return value is reserved for the success flag. <stdbool.h> must be included for the bool type.
bool enqueue(int front, int *rear, element x) {
int next = (*rear + 1) % MAX_QUEUE_SIZE;
if (next == front) return false; /* full */
*rear = next; queue[next] = x;
return true;
}
bool dequeue(int *front, int rear, element *x) {
if (*front == rear) return false; /* empty */
*front = (*front + 1) % MAX_QUEUE_SIZE;
*x = queue[*front]; return true;
}enqueue computes the new position in a local variable called next. If next == front, the queue is full and the function returns false without touching rear. If there is room, *rear = next is executed first and then the item is written. dequeue returns false on an empty queue. Otherwise it advances front, hands the item to the caller through *x, and returns true. The caller can catch the error with a check such as if (!enqueue(front, &rear, x)).
Let MAX_QUEUE_SIZE = 5 and initially front = rear = 0. A, B, C, D, and E are to be added in turn; two items are removed; then E, F, and G are to be added. Table 7.4 gives the check and the result of each call.
| Call | Check | front | rear | Array [0..4] | Returns |
|---|---|---|---|---|---|
| Start | — | 0 | 0 | . . . . . | — |
| enqueue A | next = 1 ≠ 0 | 0 | 1 | . A . . . | true |
| enqueue B | next = 2 ≠ 0 | 0 | 2 | . A B . . | true |
| enqueue C | next = 3 ≠ 0 | 0 | 3 | . A B C . | true |
| enqueue D | next = 4 ≠ 0 | 0 | 4 | . A B C D | true |
| enqueue E | next = (4 + 1) % 5 = 0 = front | 0 | 4 | . A B C D | false (full) |
| dequeue | 0 == 4? No | 1 | 4 | . . B C D | true, *x = A |
| dequeue | 1 == 4? No | 2 | 4 | . . . C D | true, *x = B |
| enqueue E | next = (4 + 1) % 5 = 0 ≠ 2 | 2 | 0 | E . . C D | true (wrap-around) |
| enqueue F | next = 1 ≠ 2 | 2 | 1 | E F . C D | true |
| enqueue G | next = 2 = front | 2 | 1 | E F . C D | false (full) |
Two rows of the table are especially important. At the first attempt to add E, the queue holds four items and one of the five cells (cell 0) is empty. Even so, next is 0 and equals front; the queue counts as full. The safe version leaves rear at 4 here. The queue is not corrupted, and the two removals return A and B in the correct order. At the second attempt to add E, rear wraps from 4 to 0, and E is written into cell 0, which a linear queue could never use. At the attempt to add G there are again four items (C, D, E, F), and the cell left empty, cell 2, is the cell that front points to. The removals that empty the queue from this state return C, D, E, F, which is consistent with the first-in-first-out rule.
next = 0 = front, full); front = 2 after two removals; E written into cell 0 by wrap-around; full again at the attempt to add G (next = 2 = front). In each frame the "item count" line applies the formula (rear − front + 5) % 5.Forgetting % MAX_QUEUE_SIZE in one place in a circular queue, for example writing *front = *front + 1 in dequeue. The program works correctly until the first wrap-around. When front takes the value MAX_QUEUE_SIZE after the last cell, an address outside the array is read. This is undefined behavior, and the bug often shows its symptoms only after a long run, in some unrelated place. Every line that advances an index must contain the remainder operation.
7.3.6Full or empty? Three methods
In the previous two traces the queue was counted as full while one cell was still empty. This is not carelessness but a necessity. With front and rear alone, a full and an empty queue cannot be told apart. Counting is enough to express the state exactly.
If the state of a circular queue of MAX cells is represented only by the indices front and rear, it is impossible to distinguish all MAX + 1 states in which the queue holds 0, 1, …, MAX items. At least two different item counts map to the same index relationship.
Proof. The number of items in the queue depends only on the difference of the two indices: the items begin at the cell after front and extend up to rear. The difference is measured as (rear − front + MAX) % MAX, and this expression can take only the values 0, 1, …, MAX − 1; that is, there are MAX different values. The item count, however, can take MAX + 1 different values, from 0 to MAX. We must distribute MAX + 1 states into MAX boxes. By the pigeonhole principle, at least one box receives two states. Concretely, the empty queue and the full queue with MAX items give the same difference (0): in both, front == rear. ∎
The theorem leaves two ways out. Either one of the indistinguishable states is not used, or extra information is kept next to the indices. Table 7.5 compares three implementations of these two ways.
| Method | Empty | Full | Capacity | Cost |
|---|---|---|---|---|
| 1. Leave one cell empty | front == rear | (rear+1)%MAX == front | MAX − 1 | One cell is wasted. |
| 2. Keep a counter | count == 0 | count == MAX | MAX | The counter is updated in every operation. |
| 3. Keep a flag | front == rear and the last operation was a dequeue | front == rear and the last operation was an enqueue | MAX | The flag is updated in every operation. |
The first method is the one used by all the code so far. The state with MAX items is given up, so that front == rear describes only the empty queue. The cost is a single cell. If the items are large structures, this cell means a noticeable amount of memory, but in most applications it is negligible. The simplicity of the code makes up for the cost.
The second method keeps the item count in a separate variable, count. Empty and full are read directly from this counter, and all MAX cells are used. The counter has a further benefit: the item count is available at any moment and is read in O(1). Moreover, with a counter there is no need to keep rear. The position of the last item is computed as (front + count − 1) % CAP and the next free cell as (front + count) % CAP.
The third method adds just one bit of information: whether the last operation was an insertion or a removal. The condition front == rear arises in only two ways. Either a removal has taken out the last item of the queue, or an insertion has filled the last empty cell. The flag tells these two possibilities apart. The code of the flag method is given in the exercises section.
7.3.7Circular queue with a counter
The counter version gathers the whole state of the queue in a struct. Several queues can then be used in the same program, and no global variable is needed. The structure is defined as typedef struct { int data[CAP]; int front, count; } Queue;. In this version front points not to the cell before the first item but to the first item itself; an empty queue starts with front = 0, count = 0. The operations are as follows:
bool enqueue(Queue *q, int x) {
if (q->count == CAP) return false; /* full */
q->data[(q->front + q->count) % CAP] = x;
q->count++;
return true;
}
bool dequeue(Queue *q, int *x) {
if (q->count == 0) return false; /* empty */
*x = q->data[q->front];
q->front = (q->front + 1) % CAP;
q->count--;
return true;
}enqueue first checks for fullness: if count == CAP, there is no room. If there is room, the new item is written just after the last item, that is, into cell (front + count) % CAP, and the counter grows by one. dequeue returns false on an empty queue. Otherwise it copies the front item into *x, advances front by one with wrap-around, and decreases the counter by one. Both operations do constant work; their cost is O(1). The functions take the queue through a Queue *q pointer. If the structure were passed by value, the function would work on a copy of it and the caller's queue would not change. The notation q->count is shorthand for (*q).count.
Let CAP = 3, front = 0, and count = 0. The values 1, 2, 3, and 4 are to be added in turn; one item is removed; 4 is added; one more item is removed. Table 7.6 gives every step.
| Call | Computation | front | count | data[0..2] | Returns |
|---|---|---|---|---|---|
| Start | — | 0 | 0 | . . . | — |
enqueue(&q, 1) | pos = (0 + 0) % 3 = 0 | 0 | 1 | 1 . . | true |
enqueue(&q, 2) | pos = (0 + 1) % 3 = 1 | 0 | 2 | 1 2 . | true |
enqueue(&q, 3) | pos = (0 + 2) % 3 = 2 | 0 | 3 | 1 2 3 | true |
enqueue(&q, 4) | count == CAP | 0 | 3 | 1 2 3 | false (full) |
dequeue(&q, &x) | *x = data[0] | 1 | 2 | . 2 3 | true, x = 1 |
enqueue(&q, 4) | pos = (1 + 2) % 3 = 0 | 1 | 3 | 4 2 3 | true (wrap-around) |
dequeue(&q, &x) | *x = data[1] | 2 | 2 | 4 . 3 | true, x = 2 |
This time all three cells fill up and no cell is wasted. The fourth insertion is rejected only because the counter has reached CAP. After one removal, the 4 that is added is written into cell 0 by wrap-around. In the final state the logical order of the queue, starting from front, is 3, 4: 3 is in the second cell and 4 is in the zeroth cell. The physical order in the array (4, ·, 3) differs from the order of the queue. In a circular queue the order is never read off the flat array; it is always read starting at front and wrapping around.
CAP = 3). Top: all three cells are full and the fourth insertion is rejected. Middle: 1 has been removed, and 4 has been written into cell 0 by wrap-around. Bottom: 2 has been removed as well: front = 2, count = 2.Mixing up the two representations. In the array-based code of the slides, front points to the cell before the first item, and the operations work in the order "advance first, then use". In the counter version, front is the first item itself, and dequeue works in the order "use first, then advance". If the code of one representation is used together with the initial values of the other, the queue skips the first item or returns an item that does not exist. In every implementation, what the indices point to should be written in a comment at the top of the code.
7.4Linked queue
Every array-based queue has a capacity. The capacity is chosen when the program is written and does not change afterward. If it is not known in advance how many items will enter the queue, two bad options remain: reserve a large array and waste memory, or reserve a small array and risk an overflow. A linked list removes this dilemma. Each item lives in its own node; a node is allocated with malloc when needed and returned with free when it is done.
7.4.1A queue on a linked list
Each node of a linked list carries a value and the address of the next node (the link). In these notes the node type is defined as typedef struct node { int data; struct node *link; } node;. The structure contains a pointer to its own type; this is why the name struct node is used before the typedef is complete. The link of the last node is NULL.
In a singly linked list, inserting at the head and deleting from the head are easy, because the first node is kept at hand. To insert at the end, one must reach the last node. If only the address of the first node is kept, the last node can be found only by walking the whole list from the beginning, which takes O(n) time. In a queue, insertion is made at one end and removal at the other, so both ends must be at hand. A linked queue is therefore represented by two pointers: front points to the first node and rear to the last. In an empty queue both are NULL.
*front points to the first node (10) and *rear to the last node (30). The link of the last node is NULL. The starred names remind us that the pointers are passed to the function by address.Which end is the front and which is the rear is not chosen at random. Insertion is made at the end of the list: rear->link = new_node; rear = new_node; and the job is done. Removal is made at the head of the list: front = front->link; skips the first node. Both operations perform a constant number of assignments and are O(1). If the opposite had been chosen, inserting at the head and deleting at the tail, insertion would still be easy but deletion would become hard. To delete the last node, the link of the node before it has to be set to NULL. In a singly linked list one cannot go back from a node to its predecessor; the second-to-last node can be found only by walking from the head, in O(n) time. The rule in short: in a singly linked queue, insert at the tail and delete from the head.
This section relies on knowledge of pointers. In the slides, an anecdote of the instructor captures well the feeling students have about this topic. The instructor devoted two lectures to pointers. A student says that he knows pointers well but still does not understand what was explained. The instructor admits that this can happen. The safest way to grasp pointer code is to draw the boxes and arrows on paper after every assignment. The two traces below do this drawing step by step.
7.4.2Code trace: enqueue
The insertion function may change both pointers of the queue. In the first insertion into an empty queue, both front and rear must point to the new node. For this reason both pointers are passed by address, that is, as pointers to pointers (node **). The call has the form enqueue(&front, &rear, 10).
bool enqueue(node **front, node **rear, int x) {
node *new_node = malloc(sizeof *new_node);
if (new_node == NULL) return false;
new_node->data = x; new_node->link = NULL;
if (*rear == NULL) *front = new_node; /* empty queue */
else (*rear)->link = new_node; /* link at end */
*rear = new_node;
return true;
}The first line allocates memory for the new node. sizeof *new_node is the size of the type that new_node points to, that is, of node. Not repeating the type name keeps the code up to date if the type changes later. If malloc finds no memory, it returns NULL. In that case the function returns false without touching the queue. Then the fields of the node are filled in. Because the new node will be the last node of the queue, its link is set to NULL.
The next if separates two cases. If *rear == NULL, the queue is empty; the new node is also the first node, and *front = new_node is executed. If the queue is not empty, the new node is linked behind the old last node: (*rear)->link = new_node. The parentheses here are necessary. The -> operator binds before *; had we written *rear->link, it would read as *(rear->link) and would not compile, because rear points to a pointer, not to a structure. In both cases the last line, *rear = new_node, moves the rear to the new node.
| Call | Step | *front | *rear | Queue |
|---|---|---|---|---|
| Start | — | NULL | NULL | (empty) |
enqueue(…, 10) | malloc; data = 10, link = NULL | NULL | NULL | (empty) |
*rear == NULL → *front = new_node | node(10) | NULL | 10 | |
*rear = new_node | node(10) | node(10) | 10 | |
enqueue(…, 20) | malloc; data = 20, link = NULL | node(10) | node(10) | 10 |
(*rear)->link = new_node: 10 now points to 20 | node(10) | node(10) | 10 → 20 | |
*rear = new_node | node(10) | node(20) | 10 → 20 | |
enqueue(…, 30) | (*rear)->link = new_node: 20 now points to 30 | node(10) | node(20) | 10 → 20 → 30 |
*rear = new_node | node(10) | node(30) | 10 → 20 → 30 |
The trace shows that front changes only at the first insertion. In later insertions front always points to 10; what changes is the link of the old last node and rear. Each insertion performs one malloc, a few assignments, and one comparison. The length of the queue affects no step; insertion is O(1). Had the rear pointer not been kept, the last node would have to be found by walking from the head at every insertion, and the total cost of n insertions would be 1 + 2 + … + n = Θ(n2).
enqueue. From top to bottom: after 10 is added, *front and *rear point to the same node; when 20 is added, the link of 10 is first turned to the new node (red arrow); then *rear moves to 20; the final state after 30 has been added as well.Forgetting to update front at the first insertion into an empty queue, that is, skipping the if branch and writing (*rear)->link = new_node in every case. When the queue is empty, *rear is NULL, and writing to NULL->link crashes the program. If only the NULL check is added and *front is skipped, the program does not crash, but front stays NULL. The queue looks empty and the inserted items can never be removed; all of them leak.
7.4.3Code trace: dequeue
The removal operation detaches the front node from the list, hands its value to the caller, and returns the node's memory:
bool dequeue(node **front, node **rear, int *x) {
node *old = *front;
if (old == NULL) return false; /* empty */
*x = old->data;
*front = old->link;
if (*front == NULL) *rear = NULL; /* last one gone */
free(old);
return true;
}The function first saves the address of the front node in a local variable called old. This saving is mandatory. Once *front has advanced to the next node, there is no other way to reach the old node; if one advances without saving its address, the node cannot be freed and leaks. If old is NULL, the queue is empty and the function returns false. Otherwise the value is copied into *x and *front = old->link moves the front to the second node.
The next line is the easiest detail of the linked queue to forget. If the last item of the queue has been removed, *front is now NULL. At this moment *rear still points to the node that is about to be freed. Unless *rear = NULL is executed, rear becomes a dangling pointer, that is, a pointer to a memory region that is no longer valid. The next call to enqueue does not see *rear as NULL, does not regard the queue as empty, and writes into the link field of the freed node. This is undefined behavior. Moreover, because front stays NULL, the new item is not visible in the queue either. Finally, free(old) returns the node. free must be called after the value has been read and the link followed; reading the fields of a freed node is also undefined behavior.
| Call | Step | old | *front | *rear | Result |
|---|---|---|---|---|---|
1. dequeue | old = *front | node(10) | node(10) | node(20) | — |
*x = 10; *front = old->link | node(10) | node(20) | node(20) | *front ≠ NULL: rear unchanged | |
free(old) | — | node(20) | node(20) | true, 10 | |
2. dequeue | old = *front | node(20) | node(20) | node(20) | — |
*x = 20; *front = old->link | node(20) | NULL | node(20) | *front == NULL | |
*rear = NULL; free(old) | — | NULL | NULL | true, 20 | |
3. dequeue | old = *front = NULL | NULL | NULL | NULL | false (empty) |
dequeue. Top: after the first call *front has moved to 20; the node of 10 is held by old. Middle: in the second call *front has become NULL, but *rear still points to the node that is about to be freed. Bottom: *rear = NULL has been executed; the node can now safely be freed.The two functions were tested together. When 10, 20, and 30 were added to an empty queue and all were removed, the values came out in the order 10, 20, 30, and after the last removal both front and rear were NULL. A new insertion (99) into the emptied queue correctly pointed both pointers to the new node. A test with 100,000 items also confirmed that the items came out in insertion order. The malloc and free calls in the program were counted: every one of the 100,006 allocations was matched by a release, so there is no leak. On this compiler and platform a node is 16 bytes: a 4-byte int, 4 bytes of alignment padding, and an 8-byte pointer.
Not setting rear = NULL when the last item is removed from a linked queue. The bug does not show at once; it appears at the first insertion after the queue has emptied. The program sometimes seems to work and sometimes crashes in some unrelated place. The invariant of the two pointers in a linked queue is this: either both are NULL, or both point to a valid node.
7.4.4Array or linked list?
The three implementations of the queue offer the same abstract operations, but their costs and constraints differ. Table 7.9 puts them side by side.
| Criterion | Linear array | Circular array | Linked list |
|---|---|---|---|
| Enqueue / dequeue | O(1), but "false full" | O(1) | O(1) (with malloc/free) |
| Is shifting needed? | Yes: O(n) | No | No |
| Capacity | MAX (total insertions over its lifetime) | MAX − 1 (MAX with a counter) | As much as memory allows |
| Extra memory | None | None | One pointer per item |
| Special case | rear hits the end | Wrap-around and full/empty distinction | rear = NULL when emptied |
The linear queue serves teaching purposes only; it is not used in real programs. The choice between the circular array and the linked list depends on the application. The circular array uses memory as a single block. Because the items sit side by side in memory, it makes good use of the processor cache and does not call malloc in every operation. A linked queue needs no upper bound, but it carries a pointer for every item and every insertion is a memory allocation call. In a queue of int this means 16 bytes per item, where an array needs 4.
In practice two structures are used most: the circular array for fixed-capacity buffers, and the growing circular array for queues whose upper bound is unknown. In the growing version, when the array becomes full, a new array of twice the size is allocated and the items are moved there. The move cannot be done with realloc. realloc copies the old block as it is; if the queue has wrapped around, some of the items are at the end of the array and some at the beginning, and in the enlarged array empty cells would remain between them. The items are therefore copied one by one in logical order, starting at front.
typedef struct {
int *data;
int cap, front, count;
} DQueue;
bool grow(DQueue *q) {
int new_cap = 2 * q->cap;
int *bigger = malloc(new_cap * sizeof *bigger);
if (bigger == NULL) return false;
for (int i = 0; i < q->count; i++) /* copy in queue order */
bigger[i] = q->data[(q->front + i) % q->cap];
free(q->data);
q->data = bigger; q->cap = new_cap; q->front = 0;
return true;
}
bool dq_enqueue(DQueue *q, int x) {
if (q->count == q->cap && !grow(q)) return false;
q->data[(q->front + q->count) % q->cap] = x;
q->count++;
return true;
}grow allocates the new array, takes the i-th item from cell data[(front + i) % cap] and writes it into the i-th cell of the new array, releases the old array, and pulls front back to 0. dq_enqueue grows the queue only when it is full; if growing fails, it returns false without touching the queue. For example, suppose 1…4 are added to a four-cell queue, two items are removed, and then 5 and 6 are added. The array physically contains 5, 6, 3, 4, and front = 2. When 7 is added, the array grows to eight cells and the items are laid out from the start in the order 3, 4, 5, 6; 7 goes into the fifth cell. A copy that disturbed the order would make the queue return some order other than 3, 4, 5, 6, 7.
Growing by itself takes Θ(n) time, but it is done rarely. Because the capacity doubles each time, the total number of items copied over n insertions is 1 + 2 + 4 + … < 2n. The average cost per insertion therefore stays constant; insertion is amortized O(1). In the experiment, one million items were added to a queue whose capacity started at 1: 20 growth steps were made, a total of 1,048,575 items were copied, and this number stayed below 2n. All items came out in insertion order; all 23 malloc calls were matched by free.
A linked queue is the natural choice if the items already live as nodes. For example, an operating system strings its process descriptor structures into a queue using their own link fields. In this case the queue allocates no separate memory; it merely arranges the links that already exist.
7.5Deques and applications
Queues and stacks restrict access to one or two ends. This section first introduces the general structure in which both ends are open for both insertion and removal, the double-ended queue. It then moves on to three applications of the queue: keeping several queues in a single array, time-sliced scheduling in operating systems, and building a queue from two stacks alone.
7.5.1The double-ended queue
A double-ended queue, or deque for short (pronounced "deck"), is an ordered list in which insertion and deletion can take place at both ends. It has four basic operations: insert at the front, insert at the rear, remove from the front, and remove from the rear. In a suitable implementation all four take O(1) time.
The deque is a general structure that covers both the stack and the queue. If only one end is used, for example always inserting at the rear and always removing from the rear, the deque behaves like a stack: after 1, 2, 3 are inserted, 3, 2, 1 come out. If items are inserted at one end and removed from the other, it becomes a queue: the same insertion order gives the removal order 1, 2, 3. Both behaviors were checked by testing the implementation below. There are also two restricted kinds. In an input-restricted deque, insertion is allowed at one end only, while deletion is allowed at both. In an output-restricted deque, insertion is allowed at both ends and deletion at one end only.
The deque is useful in many algorithms. In the sliding window problem, a window of fixed width is slid along an array and the largest value in the window is wanted at every position. A deque holds the indices of the candidate values. The index that leaves the window is dropped from the front, and candidates smaller than the newcomer are dropped from the back. The whole array is thus processed in O(n) time. In work stealing, a method used in multicore schedulers, each core keeps its own jobs in a deque. The core takes its own jobs from one end, while an idle core "steals" a job from the other end. The undo history of a text editor can also be kept in a deque. New operations are added at the rear and undo is done from the rear. When the history exceeds a certain length, the oldest record is dropped from the front.
7.5.2A deque in a circular array
A deque is built from the circular queue with a counter by adding a little. The structure is the same: typedef struct { int data[CAP]; int front, count; } Deque;. front points to the first item, and count is the item count. Insertion at the rear and removal from the front are the same as the enqueue and dequeue functions of the queue with a counter. The two new operations are insertion at the front and removal from the rear:
bool push_front(Deque *d, int x) {
if (d->count == CAP) return false;
d->front = (d->front - 1 + CAP) % CAP; /* one back */
d->data[d->front] = x; d->count++;
return true;
}
bool pop_back(Deque *d, int *x) {
if (d->count == 0) return false;
*x = d->data[(d->front + d->count - 1) % CAP];
d->count--; return true;
}push_front puts the new item one cell behind the current first item. To do so, front is moved back by one. To avoid the negative-remainder trap of modular arithmetic, the step backward is computed as (front − 1 + CAP) % CAP. For front = 0 this expression gives CAP − 1: the cell behind 0 is the last cell of the array. pop_back finds the position of the last item with (front + count − 1) % CAP, reads the value in that cell, and only decreases the counter. When the last item is removed, front does not change, because the first item stays where it is. For completeness, the other two operations are given below:
bool push_back(Deque *d, int x) {
if (d->count == CAP) return false;
d->data[(d->front + d->count) % CAP] = x; /* just after the last item */
d->count++;
return true;
}
bool pop_front(Deque *d, int *x) {
if (d->count == 0) return false;
*x = d->data[d->front];
d->front = (d->front + 1) % CAP; /* one forward */
d->count--;
return true;
}None of the four functions contains a loop; each performs a few arithmetic operations and one array access. All of them cost O(1). The memory cost is CAP items.
Let CAP = 5. The values 10 and 20 have been inserted with push_back; front = 0, count = 2. The calls push_front(&d, 5), push_front(&d, 3), and two calls of pop_back are made in turn. Table 7.10 gives every step.
| Call | Computation | front | count | data[0..4] | Order |
|---|---|---|---|---|---|
| Start | — | 0 | 2 | 10 20 . . . | 10 20 |
push_front(&d, 5) | front = (0 − 1 + 5) % 5 = 4 | 4 | 3 | 10 20 . . 5 | 5 10 20 |
push_front(&d, 3) | front = (4 − 1 + 5) % 5 = 3 | 3 | 4 | 10 20 . 3 5 | 3 5 10 20 |
pop_back | pos = (3 + 4 − 1) % 5 = 1; *x = 20 | 3 | 3 | 10 . . 3 5 | 3 5 10 |
pop_back | pos = (3 + 3 − 1) % 5 = 0; *x = 10 | 3 | 2 | . . . 3 5 | 3 5 |
The first push_front shows that wrap-around works in the backward direction as well. front goes from 0 to 4 and 5 is written into the last cell of the array. In the logical order, however, 5 is in front of 10. Read flat, the array shows 10, 20, ·, ·, 5; the order of the deque is read starting at front and wrapping around: 5, 10, 20. The two calls of pop_back return not the most recently inserted items but the items at the end of the deque: first 20, then 10. If a pop_front were called at this point, it would return 3 and front would advance to 4.
front wrapping from 0 to the end of the array (4); 3 pushed at the front as well (front = 3); after two pop_back calls only 3 and 5 remain. The bottom line of each frame computes the position of the last item.Writing the step backward as (front − 1) % CAP. In C the value of (0 − 1) % 5 is −1, not 4 as in mathematics. The code writes to data[-1]. This address falls on the memory just before the array, often another field of the structure or another variable. The compiler does not catch it. In backward steps, + CAP must always be added.
7.5.3Several queues in one array
Some programs use many queues at the same time. For example, an operating system may keep a separate ready-process queue for each priority level. Reserving a separate large array for each queue wastes memory, because not all the queues fill up at once. A method used for stacks can be tried here too: a one-dimensional array memory[] is divided into n segments and each queue is given one segment. For the i-th queue three values are kept: front[i], rear[i], and boundary[i], which marks where the segment ends.
Two stacks fit into one array very efficiently: one grows from the beginning of the array to the right, the other from the end to the left, and they meet only when the whole array is full. This trick of growing from the ends does not work for queues. The bottom end of a stack is fixed, but both ends of a queue move. A queue keeps drifting within its segment as items are inserted and removed. If each segment is managed as a circular queue, no shifting is needed. But when a segment fills up, even if other segments have free space, one of the queues must be moved to make room. This takes O(m) time, where m is the length of the array. Because of this complexity, nowadays each queue usually gets its own growing array or linked list when several queues are needed.
7.5.4Round-robin job scheduling
On a computer with a single processor, many processes want to run at the same time. The operating system shares the processor among the processes. The best-known sharing method is time-sliced scheduling, also called round robin. Ready processes wait in a queue. The scheduler takes the process at the front and runs it for at most Q units, one time slice. If the process finishes its work in this time, it leaves the system. If it cannot finish, it returns to the end of the queue with its remaining work. Thus no process can monopolize the processor, and every process gets its turn at regular intervals.
In the simulation the processes are represented by the numbers 0, 1, 2, and the amounts of remaining work by the array left[]. The queue is the circular queue with a counter; the function names are enqueue and dequeue again:
#define CAP 16
typedef struct { int data[CAP]; int front, count; } Queue;
bool enqueue(Queue *q, int x) {
if (q->count == CAP) return false;
q->data[(q->front + q->count) % CAP] = x;
q->count++;
return true;
}
bool dequeue(Queue *q, int *x) {
if (q->count == 0) return false;
*x = q->data[q->front];
q->front = (q->front + 1) % CAP;
q->count--;
return true;
}Initially all three processes are in the queue. P0 has 5 units of work, P1 has 2, and P2 has 4, and the time slice is Q = 2:
int left[] = {5, 2, 4}; /* work left for P0, P1, P2 */
int Q = 2, time = 0, p;
Queue q = { {0}, 0, 0 }; /* empty queue with counter */
for (int i = 0; i < 3; i++)
enqueue(&q, i); /* all start in the queue */The scheduler itself is a single loop:
/* q: queue of process ids; Q: time slice */
while (dequeue(&q, &p)) {
int run = left[p] < Q ? left[p] : Q;
time += run;
left[p] -= run;
if (left[p] > 0)
enqueue(&q, p); /* back of line */
else
printf("P%d done: t=%d\n", p, time);
}The loop runs until the queue is empty; because dequeue returns false on an empty queue, the condition is also the termination check. In each round the process at the front is taken into p. The time the process will run in this round is the smaller of its remaining work and the time slice; the conditional expression (? :) computes this in one line. The clock (time) advances by that much, and the process's remaining work decreases by the same amount. If work remains, the process is added at the end of the queue; otherwise its finishing time is printed.
| Round | Dequeued | run | Running interval | left (P0, P1, P2) | Result | Queue (front to rear) |
|---|---|---|---|---|---|---|
| — | — | — | — | 5, 2, 4 | — | P0 P1 P2 |
| 1 | P0 | 2 | 0–2 | 3, 2, 4 | goes back to the rear | P1 P2 P0 |
| 2 | P1 | 2 | 2–4 | 3, 0, 4 | P1 done: t=4 | P2 P0 |
| 3 | P2 | 2 | 4–6 | 3, 0, 2 | goes back to the rear | P0 P2 |
| 4 | P0 | 2 | 6–8 | 1, 0, 2 | goes back to the rear | P2 P0 |
| 5 | P2 | 2 | 8–10 | 1, 0, 0 | P2 done: t=10 | P0 |
| 6 | P0 | 1 | 10–11 | 0, 0, 0 | P0 done: t=11 | (empty) |
The program prints P1 done: t=4, P2 done: t=10, and P0 done: t=11 in this order. In the last round P0 has only 1 unit of work left, so the slice is 1, not 2. The total time equals the sum of the jobs (5 + 2 + 4 = 11), because the processor is never idle. The result of scheduling is the finishing order. The shortest job (P1) finishes first and the longest (P0) last. Had the processes instead been run without interruption under a first-come-first-served rule, the finishing times would have been 5 for P0, 7 for P1, and 11 for P2. A short job would have had to wait behind a long one.
In terms of cost, each round performs one dequeue and at most one enqueue; both are O(1). If the total work of a process is w units, the process is taken from the queue ⌈w/Q⌉ times. The total cost of the simulation is proportional to the sum of these numbers. In the example this sum is 3 + 1 + 2 = 6 rounds. As the time slice gets smaller, processes get their turn more often, but the number of rounds increases. With Q = 1 the same example takes 11 rounds. In real systems every round carries the cost of a context switch, so the slice is not chosen very small.
7.5.5A queue from two stacks
If a queue is needed in an environment that offers only stack operations, two stacks suffice. The idea rests on the fact that a stack reverses order. If a sequence of items is put onto one stack and transferred from there to another stack, it is reversed twice and thus returns to its original order. The queue consists of two stacks: in and out. The stack type Stack is defined by a data array and a top index that is −1 when the stack is empty. push, pop, and stack_empty are the familiar stack operations; pop returns false if the stack is empty. The queue type has the form typedef struct { Stack in, out; } Queue2;.
void enqueue(Queue2 *q, int x) {
push(&q->in, x);
}
bool dequeue(Queue2 *q, int *x) {
int t;
if (stack_empty(&q->out)) /* out is empty */
while (pop(&q->in, &t)) /* move them all */
push(&q->out, t);
return pop(&q->out, x);
}enqueue always puts the item on the in-stack; its cost is a single push. If the out-stack is empty, dequeue first transfers all the items of the in-stack to the out-stack one by one. The transfer reverses the order: the item at the very bottom of the in-stack, that is, the oldest item, ends up on top of the out-stack. Then one pop is made from the out-stack. If the out-stack is not empty, no transfer is made, because every item in the out-stack is older than every item in the in-stack. If the transfer were made before the out-stack was empty, the new items would land on top of the old ones and the order would break. If both stacks are empty, the last pop returns false and dequeue returns false too. enqueue ignores the return value of push. If the in-stack becomes full, the item is silently lost; a safe version must pass this value on to the caller.
| Operation | What happens? | in | out | Returned |
|---|---|---|---|---|
| enqueue 1, 2, 3 | three push calls | 1 2 3 | — | — |
| dequeue | out is empty: 3, 2, 1 are transferred; then pop | — | 3 2 | 1 |
| enqueue 4 | push | 4 | 3 2 | — |
| dequeue | out is not empty: only pop | 4 | 3 | 2 |
| dequeue | out is not empty: only pop | 4 | — | 3 |
| dequeue | out is empty: 4 is transferred; then pop | — | — | 4 |
The removal order is 1, 2, 3, 4, the same as the insertion order. Although 4 was added after 2 and 3, it does not come out before them. When 4 is added, 2 and 3 are already in the out-stack, and 4 is transferred only after the out-stack has emptied.
A single call of dequeue can be expensive: if the out-stack is empty and the in-stack holds n items, n transfers are made and the call takes Θ(n) time. But such expensive calls are rare. Over a whole sequence of operations, the cost per operation is constant.
Every sequence of m calls to enqueue or dequeue, starting from an empty queue, performs at most 4m stack operations (push or pop). Hence the amortized cost of both operations is O(1).
Proof. Follow the life of a single item in the queue. The item is pushed onto the in-stack once by enqueue (one push). During a transfer it leaves the in-stack once and is put onto the out-stack once (one pop, one push). It never goes back from the out-stack to the in-stack, so it is never transferred a second time. Finally it leaves the out-stack once by dequeue (one pop). Each item thus takes part in at most four stack operations. In addition to these, each dequeue call performs at most one pop that fails when the stacks are empty and one stack_empty check. Since at most m items can be inserted in the sequence, the operations belonging to items number at most 4m; the failing operations are also bounded by a constant factor. The total work is O(m) and the average work per operation is O(1). ∎
The method in this proof is the simplest form of amortized analysis. The cost of an expensive operation is distributed over the cheap operations that make it possible. Here every enqueue "pays in advance" for the cost of later transferring its item. The theorem was also tested by an experiment. In a randomly chosen sequence of 60 operations, 37 insertions were made and all the inserted items were eventually removed. A total of 74 push and 74 pop calls were counted; this means exactly two push and two pop calls per item. All items came out in insertion order. One point deserves attention here: amortized O(1) does not say that every call is fast. If an application requires that no operation exceed a certain time (for example, a real-time audio buffer), the circular queue is more suitable.
7.5.6Stack or queue?
To decide whether a problem needs a stack or a queue, ask a single question: of the items waiting to be processed, which should be handled first, the newest or the oldest? If the newest, a stack is appropriate; if the oldest, a queue. If neither the newest nor the oldest but the item that is most important by some other criterion is to be taken first, a priority queue is needed. Table 7.13 classifies the examples in the slides according to this question.
| Problem | Structure | Reason |
|---|---|---|
| Documents sent to a printer | Queue | Documents are printed in the order they were sent. |
| Ctrl+Z in a text editor | Stack | The most recent operation is undone first. |
| Printing a tree level by level | Queue | Level-order traversal (BFS): the node discovered first is processed first. |
| Checking nested parentheses | Stack | A closing parenthesis matches the most recently opened one. |
| Function calls | Stack | The call stack: the most recently called function returns first. |
| Most seriously ill patient first in an emergency room | Priority queue | The turn depends on priority, not on arrival; it is not FIFO. |
The last row can be misclassified by looking at the word "queue" in its name. The instructor's note in the slides also points out this confusion. In the queue of everyday language, items are added at the end and taken from the front. A priority queue does not obey this rule; the word in its name carries only the meaning "a place to wait".
7.6Complexity summary and measurements
Table 7.14 brings together the operation costs of the four implementations examined in these notes. The justification of each value in the table is given in the relevant section. Here only the common points are summarized.
| Operation | Linear array | Circular array | Linked | Deque (circular) |
|---|---|---|---|---|
| Enqueue | O(1)* | O(1) | O(1) | O(1), at both ends |
| Dequeue | O(1) | O(1) | O(1) | O(1), at both ends |
| Front / empty / full | O(1) | O(1) | O(1) | O(1) |
| Item count | rear − front | (rear−front+MAX)%MAX | O(n) or a counter | count |
| Memory | MAX | MAX | n · (item + pointer) | CAP |
The starred value carries a caveat. In a linear queue, insertion by itself is O(1), but if false full is cured by shifting, insertion rises to O(n). In a linked queue, if no separate counter is kept, the item count can be found only by walking the list from beginning to end. Adding a counter variable brings this operation down to O(1) as well. Because insertion and removal take constant time in all the implementations, the cost of an algorithm that uses a queue is determined by the number of queue operations it performs. The round-robin simulation and level-order traversal perform O(n) queue operations for n items.
The difference between the linear queue with shifting and the circular queue was also shown by measurement. Both queues used an array of M cells. The shifting queue held M − 1 items at all times, and the circular queue held M − 2 items, since one cell stays empty there. One insertion and one removal were then performed 200,000 times. The program was compiled with -O2 and the times were measured with timespec_get. The results are given in Table 7.15. Absolute times vary from machine to machine; what matters is how the columns change with M.
| M | Shifting: items moved | Shifting: time | Circular: time |
|---|---|---|---|
| 1000 | 199.799.001 | 7–8 ms | ≈ 1 ms |
| 2000 | 399.798.001 | 13–15 ms | ≈ 1 ms |
| 4000 | 799.796.001 | 31–33 ms | ≈ 1 ms |
| 8000 | 1.599.792.001 | 63–76 ms | ≈ 1 ms |
The number of items moved doubles when M doubles; each insertion moves about M − 1 items. The times grow at the same rate. The time of the circular queue, on the other hand, is independent of M. The times of the shifting version are surprisingly short relative to the number of items moved. The reason is that the compiler turns the shifting loop into a fast operation that copies blocks of memory in bulk. Even so, the growth is linear, and the gap widens as the queue gets larger.
7.7Common mistakes
The six most common mistakes in queue code are collected below. Each was treated in detail in the earlier sections; here the symptom and the remedy are given together.
- Mistaking
rear == MAX − 1for true fullness in a linear queue. The condition says only that no room is left at the rear; the item count isrear − frontand may be very small. The remedy is the circular queue. - Forgetting
% MAXin a circular queue. At the first wrap-around the index goes outside the array. The program may run correctly for a long time and then break in an unexpected place. The remainder operation must be looked for on every line that changes an index. - Advancing
rearfirst and not restoring it if the queue is full. In a version that returns an error, an attempted insertion into a full queue makesrearequal tofrontand the queue looks empty. The new position must be tried first in a temporary variable. - Writing
(i − 1) % MAXfor a step backward. In C the remainder of a negative number is negative; fori = 0the result is −1. The correct form is(i − 1 + MAX) % MAX. - Not setting
rear = NULLwhen the last item is removed from a linked queue.rearpoints to the freed node; the next insertion writes into that memory and the new item is not visible in the queue. - Forgetting to update
frontat the first insertion into an empty linked queue. Either the write goes through aNULLpointer and the program crashes, orfrontstaysNULLand the inserted items can never be removed.
The common root of these mistakes is edge cases: the empty queue, the full queue, the one-item queue, and the last cell of the array. When a queue implementation is tested, at least the following scenarios should be tried: removing from an empty queue, filling the queue completely and trying one more insertion, at least one wrap-around, and emptying the queue entirely and reusing it.
7.8Exercises and solutions
This section gives the five exercises in the slides with detailed solutions. The solutions that contain code have been compiled and tested.
7.8.1Item count and positions
Question. How many items does a circular queue with MAX = 6, front = 4, and rear = 1 hold, and at which indices are they?
Solution. The item count is (rear − front + MAX) % MAX = (1 − 4 + 6) % 6 = 3. Because front points to the cell before the first item, the items begin at the cell after front: (4 + 1) % 6 = 5. Then, with wrap-around, come 0 and 1. The items are in cells 5, 0, and 1, and the front item is in cell 5. Cells 2, 3, and 4 are empty; cell 4 is the cell that the first method leaves empty.
7.8.2Circular queue with a flag
Question. Write the insertion and removal routines of a circular queue that tells full from empty with a flag.
Solution. A boolean variable called last_was_enqueue records whether the last operation was an insertion. When front == rear, the queue is full if this variable is true and empty if it is false. Initially the queue is empty, so its value is false.
#define MAX 4
int queue[MAX];
int front = 0, rear = 0;
bool last_was_enqueue = false; /* was the last op an enqueue? */
bool enqueue(int x) {
if (front == rear && last_was_enqueue) return false; /* full */
rear = (rear + 1) % MAX;
queue[rear] = x;
last_was_enqueue = true;
return true;
}
bool dequeue(int *x) {
if (front == rear && !last_was_enqueue) return false; /* empty */
front = (front + 1) % MAX;
*x = queue[front];
last_was_enqueue = false;
return true;
}After the full check, insertion works in the same way as the code in the slides, but at the end it raises the flag. Removal lowers the flag. The flag is read only when front == rear. While the queue holds between 1 and MAX − 1 items, the two indices differ anyway and the value of the flag does not matter. When this version was tested, four insertions fit into the empty four-cell queue (front = rear = 0, flag true) and the fifth was rejected. After one removal (10) and one insertion (99), the queue was full again and the items came out in the order 11, 12, 13, 99. No cell is wasted; the cost is one assignment in every operation and one boolean comparison in the full or empty check.
7.8.3Cost of a queue made of two stacks
Question. Write a queue using two stacks. What is the amortized cost of dequeue?
Solution. The code consists of the enqueue and dequeue functions in the slides: insertion does a push onto the in-stack; removal transfers the whole in-stack if the out-stack is empty and then does a pop from the out-stack. As shown in the proof of Theorem 7.2, each item is pushed onto a stack at most twice and popped from a stack twice. The total cost of a sequence of m operations is O(m). The amortized cost of dequeue is therefore O(1). A single call in the worst case, however, takes Θ(n). For example, add 1, 2, 3, 4, remove one item, add 5, and remove four more. The output is 1, 2, 3, 4, 5. The first removal transfers four items and the last removal transfers only 5; the total number of push calls is 10, made up of 5 insertions and 5 transfers.
7.8.4Circular linked queue with only a rear pointer
Question. Write a queue using a circular linked list in which only the rear pointer is kept.
Solution. In a circular linked list the link of the last node is not NULL but the first node. A separate front pointer is therefore unnecessary: the front node is always rear->link. In a one-node queue the node points to itself. In an empty queue rear is NULL.
bool enqueue(node **rear, int x) {
node *new_node = malloc(sizeof *new_node);
if (new_node == NULL) return false;
new_node->data = x;
if (*rear == NULL) new_node->link = new_node; /* lone node points to itself */
else {
new_node->link = (*rear)->link; /* new node points to front */
(*rear)->link = new_node; /* old rear points to new */
}
*rear = new_node;
return true;
}
bool dequeue(node **rear, int *x) {
if (*rear == NULL) return false; /* empty */
node *front = (*rear)->link; /* front follows rear */
*x = front->data;
if (front == *rear) *rear = NULL; /* last node gone */
else (*rear)->link = front->link;
free(front);
return true;
}Insertion places the new node between the last node and the front node. First the new node points to the front node (new_node->link = rear->link), then the old last node points to the new node, and finally rear moves to the new node. The order of these links matters: if the second assignment were made first, the address of the front node would be lost. Removal takes out the front node (rear->link). If the queue has a single node, front and rear are the same node and the queue becomes empty. Otherwise the link of the last node is turned to the second node. Both operations are O(1) and only one pointer is kept. In testing, when 10, 20, and 30 were added and removed, the order was preserved; all 1003 malloc calls were matched by free.
7.8.5Round robin, Q = 3
Question. Run the round-robin example (P0 = 5, P1 = 2, P2 = 4) with Q = 3. When do the processes finish?
Solution. P0 runs from 0 to 3 and has 2 units left; it returns to the rear. P1 runs from 3 to 5 and finishes at t = 5. P2 runs from 5 to 8 and has 1 unit left; it returns to the rear. P0 runs its remaining 2 units from 8 to 10 and finishes at t = 10. P2 runs its last unit from 10 to 11 and finishes at t = 11. The program prints P1 done: t=5, P0 done: t=10, P2 done: t=11. The finishing order has changed relative to Q = 2: P0 now finishes before P2. The number of rounds also falls from 6 to 5. As the slice grows, scheduling approaches first-come-first-served; for Q ≥ 5 the finishing times are 5, 7, and 11.
7.9Summary
- A queue is an ordered list in which insertion takes place at the rear and removal at the front; its rule is first in, first out (FIFO). A stack reverses order and a queue preserves it. The basic operations are
enqueue(overflow),dequeue(underflow),queue_front,queue_empty, andqueue_full. - The linear queue uses two indices:
frontpoints to the cell before the first item andrearto the last item; the empty condition isfront == rear. Because the indices only move forward, cells vacated at the front cannot be used (false full). Shifting solves this problem but makes insertion O(n). - The circular queue wraps the indices with
% MAX. Empty:front == rear; full:(rear + 1) % MAX == front. The item count is(rear − front + MAX) % MAXand a step backward is(i − 1 + MAX) % MAX; in C the remainder of a negative number is negative. - Two indices cannot distinguish
MAX + 1occupancy states. The remedy is either to leave one cell empty (capacityMAX − 1) or to keep a counter or a flag. The counter version gives the item count in O(1) and computesrear. - An operation that can fail must not modify the structure when it fails: the new position is first tried in a temporary variable.
- The linked queue inserts at the tail and deletes from the head with
frontandrearpointers; both operations are O(1). At the first insertion into an empty queuefrontis updated, and when the last item is removedrear = NULL; otherwise a leak or a dangling pointer results. - In practice, a circular array is used for fixed-capacity buffers and a circular array that doubles in size (amortized O(1)) for queues with an unknown upper bound; when growing, the items are copied in order starting at
front. - The deque inserts and removes at both ends; in a circular array all four operations are O(1). It covers both the stack and the queue.
- In round-robin scheduling, processes wait in a queue, run for at most one time slice, and return to the rear if work remains. In a queue made of two stacks, each item is transferred at most once; the operations are amortized O(1).
7.10Key terms
- queue
- FIFO (first in, first out)
- LIFO (last in, first out)
- front
- rear
- enqueue
- dequeue
- abstract data type
- overflow
- underflow
- circular queue
- modular arithmetic
- buffer
- breadth-first search (BFS)
- level-order
- priority queue
- dangling pointer
- memory leak
- deque (double-ended queue)
- amortized analysis
- doubling
- stack
7.11Test Yourself
In a safe circular queue,
MAX_QUEUE_SIZE = 4and initiallyfront = rear = 0. The values 1, 2, 3, 4 are to be added in turn, one item is removed, and 4 is added again. Which insertion is rejected? At the end, what arefront,rear, and the item count? Which value does the nextdequeuereturn?Answer
1, 2, 3 go into cells 1, 2, 3 respectively. For 4,
next = (3 + 1) % 4 = 0 = front, and the insertion is rejected. The removal advancesfrontto 1 and returns 1. The re-added 4 is written into cellrear = 0. At the endfront = 1,rear = 0, and the item count is(0 − 1 + 4) % 4 = 3. The next removal returns 2.Three items are added to a linear queue with
MAX_QUEUE_SIZE = 5and all three are removed. Although the queue is empty, how many more insertions can be made at most? Why?Answer
After three insertions and three removals,
front = rear = 2. Insertion is possible untilrearreaches 4: two insertions. At the third attemptrear ≥ 4holds and the queue counts as full. The cause is false full: cells 0, 1, and 2 are empty, but because the indices only move forward they are never used again.A programmer has written the step backward in a deque as
d->front = (d->front - 1) % CAP;. What happens ifpush_frontis called whenCAP = 8andfront = 0?Answer
In C the value of
(0 − 1) % 8is −1.frontbecomes −1 and the item is written intodata[-1], that is, outside the array. This is undefined behavior; another field of the structure or a neighboring variable may be corrupted. The correct expression is(front − 1 + CAP) % CAP, which gives 7.The line
if (*front == NULL) *rear = NULL;has been deleted from thedequeuefunction of the linked queue. 5 and 7 are added to an empty queue, two items are removed, and then 9 is added. What happens?Answer
After the second removal
frontisNULL, butrearstill points to the freed node of 7. When 9 is added,*rear != NULL, so the code does not regard the queue as empty and writes into freed memory with(*rear)->link = new_node; this is undefined behavior. Becausefrontis not updated, it staysNULL. The nextdequeuefinds the queue empty; 9 can never be removed and its node leaks.In a circular queue with a counter,
CAP = 4,front = 3, andcount = 3. In which cells are the items? Into which cell will the nextenqueuewrite its item?Answer
Starting at
front, the items are in cells 3, 0, and 1. The position of the last item is(3 + 3 − 1) % 4 = 1. The next insertion writes into cell(3 + 3) % 4 = 2and the counter becomes 4; the queue is full.To an empty deque with
CAP = 6(front = 0,count = 0),push_front 1,push_front 2, andpush_back 3are applied in turn. Which value is in which cell? What doespop_frontreturn?Answer
The first
push_frontmovesfrontto(0 − 1 + 6) % 6 = 5and writes 1 into cell 5. The second movesfrontto 4 and writes 2 into cell 4.push_back 3writes into cell(4 + 2) % 6 = 0. The order of the deque is 2, 1, 3;pop_frontreturns 2.In a round-robin simulation each of three processes has 3 units of work and Q = 2. When do the processes finish?
Answer
In the first round P0 runs from 0 to 2, P1 from 2 to 4, and P2 from 4 to 6; each has 1 unit left and returns to the rear. In the second round P0 runs from 6 to 7, P1 from 7 to 8, and P2 from 8 to 9. The finishing times are 7 for P0, 8 for P1, and 9 for P2.
1, 2, 3, 4 are added to a queue made of two stacks; one item is removed; 5 is added; four more items are removed. What is the removal order? How many
pushcalls are made in total?Answer
At the first removal the out-stack is empty; 4, 3, 2, 1 are transferred and 1 is removed. 5 is pushed onto the in-stack. The next three removals return 2, 3, 4 from the out-stack. At the last removal the out-stack is empty; 5 is transferred and removed. The removal order is 1, 2, 3, 4, 5. The number of
pushcalls is 10, made up of 5 insertions and 5 transfers.In the first method (leaving one cell empty), why does a queue of
MAXcells hold at mostMAX − 1items? What would happen if the queue were allowed to holdMAXitems?Answer
If the
MAX-th item were added,rearwould advance and become equal tofront. Butfront == rearis the condition for an empty queue. The code would mistake a full queue for an empty one:dequeuewould report underflow, whileenqueuewould overwrite items. The difference of the two indices takes onlyMAXvalues, whereas the item count can takeMAX + 1values; one state has to be given up.
7.12Further reading
- E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Sections 3.3 and 4.3: the source of the array-based and linked queue implementations followed in these notes, of the circular queue, and of several queues in one array.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Section 10.1: gives the queue in pseudocode on a circular array, briefly and precisely; the deque and the queue from two stacks appear as exercises.
- R. Sedgewick, Algorithms in C, Parts 1–4, Chapter 4: treats abstract data types, the stack and queue interfaces, and their array and linked-list implementations comparatively.
7.13References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Sections 3.3 and 4.3.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Section 10.1 (queues, deque exercises).
- R. Sedgewick, Algorithms in C, Parts 1–4, Chapter 4.
Related pages: Chapter 7 slides · © Sercan Külcü. All rights reserved.