This is a beta course, so its structure, chapters, and examples may continue to change.

Queues

A queue is the other restricted linear list that stands alongside the stack, and it follows the first in, first out (FIFO) principle. From queuing to buy milk tea to task scheduling in an operating system, from the breadth-first search of a graph to the level-order traversal of a binary tree, the queue is everywhere. This chapter revolves around the two storage implementations of a queue (the sequential one and the linked one), the false overflow problem of a circular queue, and the variants such as the deque and the priority queue. After reading this section you will be able to understand the definition, the characteristics and the basic operations of a queue, master the storage structure of a circular queue together with its conditions for testing emptiness and fullness and its enqueue and dequeue implementations, understand the false overflow problem of an ordinary sequential queue and the way the circular queue solves it, master the implementation of a linked queue and the precautions for its dequeue operation, learn the characteristics and the applicable scenarios of the deque and of the priority queue, and master the application of a queue in scenarios such as BFS and the level-order traversal.

Questions This Chapter Answers

How can first come, first served be guaranteed? An ordinary sequential queue suffers from the space waste of the false overflow, while a circular queue joins the head and the tail of the array with a modulo operation; a linked queue gets rid of the space limit completely. In addition, how a deque combines the advantages of a stack and of a queue, and how a priority queue cuts in line, are the questions that this chapter has to sort out.

Basic route: basic concepts → sequential queue → linked queue; master the two storage implementations first.

Advanced route: deque and priority queue → classic applications → summary; understand the variants of a queue and their practical value.

The conditions for testing emptiness and fullness of a circular queue are the core examination point of this chapter (front == rear means empty, (rear+1)%MaxSize == front means full), so be sure to work through the convention of “sacrificing one storage unit” together with the code. When a linked queue dequeues its last element, the rear pointer has to be updated as well, which is another common point of confusion.

Basic Concepts

A queue (Queue) is a first in, first out (First In First Out, abbreviated FIFO) linear list in which insertion is allowed only at one end of the list (called the rear) and deletion only at the other end (called the front).

The insertion operation is called enqueue
The deletion operation is called dequeue
A queue that contains no elements is called an empty queue

Characteristics

First in, first out (FIFO): the element that was enqueued first is dequeued first
Restricted operations: insertion only at the rear, deletion only at the front
The front and the rear move dynamically: the two pointers move with the dequeue and the enqueue operations respectively

Basic Operations

Operation	Description
`InitQueue(&Q)`	Initializes an empty queue
`DestroyQueue(&Q)`	Destroys the queue and releases the memory
`EnQueue(&Q, x)`	Enqueues the element $x$
`DeQueue(&Q, &x)`	Dequeues the front element and returns it in $x$
`GetHead(Q, &x)`	Reads the front element and returns it in $x$ (without dequeuing it)
`QueueEmpty(Q)`	Tests whether the queue is empty
`QueueLength(Q)`	Returns the number of elements in the queue

Exercises

Exercise 1

The characteristic of a queue is ( )

A. First in, first out B. Last in, first out C. Random in, random out D. In and out by priority

Reference Answer

queuefirst in first outlinear list

Approach:

This question tests the basic characteristic of a queue. When deciding it, focus on the division of labour between the two ends of a queue, insertion at the rear and deletion at the front; the dequeue order therefore has to be first in, first out, and the options that describe other structures can be ruled out.

Steps:

A queue is a restricted linear list in which insertion (enqueue) and deletion (dequeue) are allowed only at the rear and at the front respectively.
Because the element that was enqueued first stands at the front, the element that was enqueued first has to be dequeued first, so the ordering characteristic of a queue is first in, first out (First In First Out, FIFO), and option A is correct.
Option B, “last in, first out”, is the characteristic of a stack; option C, “random in, random out”, violates the operational restriction of a queue; option D, “in and out by priority”, is not a basic characteristic of a queue.

Answer:

Exercise 2

Suppose a stack S and a queue Q are both initially empty, and the elements a, b, c, d, e, f enter the stack S in this order. If every element enters the queue Q as soon as it leaves the stack, and the dequeue order of the 6 elements is b, d, c, f, e, a, then the capacity of the stack S is at least ( )

A. 2 B. 3 C. 4 D. 5

Reference Answer

queuestackpop sequencecapacity analysis

Approach:

This question asks for the minimum capacity of the stack, derived backwards from the dequeue order. The key is to use the first in, first out property of the queue in reverse: an element enters the queue right after it leaves the stack, so the dequeue order of the queue is exactly the pop order of the stack. Simulate every push and pop on that basis and find the maximum number of elements that the stack holds at the same time.

Steps:

Because every element enters the queue as soon as it leaves the stack, and the queue is first in, first out, the dequeue order b, d, c, f, e, a of the 6 elements is the pop order of the stack.
a is pushed (stack: [a]); b is pushed (stack: [a,b]) and then b is popped (stack: [a]).
c is pushed (stack: [a,c]); d is pushed (stack: [a,c,d]) and then d is popped (stack: [a,c]) and c is popped (stack: [a]).
e is pushed (stack: [a,e]); f is pushed (stack: [a,e,f]) and then f is popped (stack: [a,e]), e is popped (stack: [a]) and a is popped.
During the whole process the stack holds at most 3 elements at the same time (a, c, d or a, e, f), so the capacity of the stack is at least 3.

Answer:

B (3).

Exercise 3

Briefly describe the definition and the main characteristics of a queue. What is the difference between a queue and a stack?

Reference Answer

queuefirst in first outqueue and stack comparisonrestricted operations

Approach:

This question asks for the definition and the characteristics of a queue first, and then for a comparison with a stack. In the answer, explain the division of labour between the two ends and the first in, first out ordering first, and then compare the two structures point by point from three angles: the ordering characteristic, the end at which the operations are allowed, and the typical scenario.

Steps:

The definition of a queue: a queue is a first in, first out (FIFO) linear list in which insertion is allowed only at one end of the list (the rear) and deletion only at the other end (the front).
The main characteristics: first in, first out (FIFO), the element that was enqueued first is dequeued first; restricted operations, insertion only at the rear (enqueue) and deletion only at the front (dequeue); the front and the rear move dynamically, the two pointers moving with the dequeue and the enqueue operations respectively.
The first difference from a stack: a stack is last in, first out (LIFO), while a queue is first in, first out (FIFO).
The second difference from a stack: a stack allows both the insertion and the deletion at one end (the top), while a queue allows the insertion at one end (the rear) and the deletion at the other end (the front).
The third difference from a stack: a stack suits the scenarios in which the last arrival is processed first (such as function calls and expression evaluation), while a queue suits the scenarios in which the first arrival is served first (such as task scheduling and buffer management).

Answer:

A queue is a first in, first out (FIFO) linear list in which insertion is allowed only at the rear and deletion only at the front. Its difference from a stack is that a stack is last in, first out and operates at a single end, while a queue is first in, first out and divides the work between the two ends; a stack suits function calls and expression evaluation, and a queue suits task scheduling and buffer management.

Sequential Storage

A sequential queue stores the elements of the queue in a set of storage units with contiguous addresses, and it is equipped with two pointers: front (the front pointer) and rear (the rear pointer).

The Problem with an Ordinary Sequential Queue

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int front;  // front pointer
    int rear;   // rear pointer
} SqQueue;

Initialization: front = rear = 0

Enqueue: data[rear++] = x

Dequeue: x = data[front++]

An ordinary sequential queue suffers from the false overflow problem: as the enqueue and the dequeue operations go on, both the front and the rear pointer keep moving forwards, and once the rear reaches the end of the array no further element can be enqueued even though there is still free space at the front of the array. This is the “false overflow”. The solution is to use a circular queue.

Circular Queue

A circular queue joins the head and the tail of the array so that they form a ring. When a pointer reaches the end of the array, the next position goes back to the beginning of the array. This reuses the array space and avoids the false overflow.

Storage Structure

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int front;  // front pointer, pointing at the front element
    int rear;   // rear pointer, pointing at the position just after the rear element
} CirQueue;

The convention of this chapter is the following: front points at the front element and rear points at the position just after the rear element. The queue is empty when front == rear. Under this convention the queue can hold at most MaxSize-1 elements, because one storage unit is sacrificed in order to tell emptiness and fullness apart.

Initialization

void InitQueue(CirQueue &Q) {
    Q.front = Q.rear = 0;
}

Testing for Emptiness

bool QueueEmpty(CirQueue Q) {
    return Q.front == Q.rear;
}

Testing for Fullness

bool QueueFull(CirQueue Q) {
    return (Q.rear + 1) % MaxSize == Q.front;
}

The condition for a full circular queue is (rear + 1) % MaxSize == front, and not rear == front! Because rear == front is also the condition for an empty queue. In order to tell emptiness and fullness apart, the circular queue sacrifices one storage unit: the queue is regarded as full when the position just after the rear pointer is the front.

Enqueue

bool EnQueue(CirQueue &Q, int x) {
    if (QueueFull(Q)) return false;  // the queue is full
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;  // move the rear forwards, the modulo makes it circular
    return true;
}

Dequeue

bool DeQueue(CirQueue &Q, int &x) {
    if (QueueEmpty(Q)) return false;  // the queue is empty
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;  // move the front forwards, the modulo makes it circular
    return true;
}

Queue Length

int QueueLength(CirQueue Q) {
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

Time complexity: all the operations are $O(1)$ .

Three ways of telling an empty circular queue from a full one:

Sacrifice one storage unit (the one used in this chapter): the queue is full when (rear+1)%MaxSize == front
Add a size member: record the number of elements in the queue, and the queue is full when size == MaxSize
Add a tag member: tag=0 means the latest operation was a deletion and tag=1 means the latest operation was an insertion. The queue is empty when front==rear and tag==0, and it is full when front==rear and tag==1

Exercises

Exercise 1

A circular queue stores its elements in the array A[0..m-1], and its front pointer front and its rear pointer rear are known (rear points at the position just after the rear element), then the number of elements in the queue is ( )

A. (rear - front + m) % m B. rear - front + 1 C. rear - front D. (rear - front) % m

Reference Answer

circular queuenumber of elementsmodulo operationfront and rear pointers

Approach:

This question tests the computation of the number of elements in a circular queue. The key is to notice that the rear may become smaller than the front after the pointers wrap around, so subtracting them directly gives a negative number; the length of the array m has to be added first and the result taken modulo m, so that it falls into the legal range.

Steps:

In a circular queue the rear may be smaller than the front because the pointer wraps around, so rear - front cannot be used directly as the answer.
The correct formula is the number of elements = (rear - front + m) % m, that is, add the length of the array m first in order to keep the result non-negative, and then take the result modulo m in order to restrict it to the range from 0 to m-1.
When rear is greater than or equal to front the result is rear - front; when rear is smaller than front the pointer has gone around once, and the result is rear - front + m.

Answer:

Exercise 2

Suppose the storage space of a circular queue is Q[1..35] and the initial state is front=rear=35. After a series of enqueue and dequeue operations front=15 and rear=15, then the number of elements in the circular queue is ( )

A. 15 B. 16 C. 20 D. 0 or 35

Reference Answer

circular queueemptiness testfullness testsacrificed storage unit

Approach:

This question tests the state judgement when front is equal to rear. The idea is to recall that in a circular queue the condition front == rear expresses both emptiness and fullness at the same time, so this condition alone cannot tell the two states apart.

Steps:

In a circular queue, when front == rear, the queue may be empty (0 elements) or it may be full.
Under the convention of sacrificing one storage unit in order to tell emptiness and fullness apart, the queue holds at most 35 elements, so when it is full front and rear are equal as well.
The condition front == rear alone cannot decide whether the queue is empty or full, so the number of elements may be 0, or it may be 35.

Answer:

D (0 or 35).

Exercise 3

What is a circular queue? Why is a circular queue used? How can the empty state and the full state of a circular queue be told apart?

Reference Answer

circular queuefalse overflowemptiness and fullnessmodulo operation

Approach:

This question asks for the definition, the motivation and the implementation details of a circular queue. In the answer, first explain that a circular queue is the ring formed by joining the head and the tail of a sequential queue, then point out that it exists in order to solve the false overflow problem of an ordinary sequential queue, and finally list the three common ways of telling emptiness and fullness apart.

Steps:

What a circular queue is: the array of a sequential queue is joined head to tail so that it forms a ring, and when the front or the rear pointer reaches the end of the array the next position goes back to the beginning of the array, the circular movement of the pointers being realized with the modulo operator (%).
Why it is used: an ordinary sequential queue suffers from the false overflow problem, the front and the rear keep moving forwards and once the rear reaches the end of the array no further element can be enqueued even though there is still free space at the front of the array; the circular queue joins the head and the tail of the array and reuses the free space at the front, which solves the false overflow and improves the space utilization.
The first way of telling them apart (the one most commonly used): sacrifice one storage unit and agree that the queue is full when the position just after the rear pointer is the front, the empty condition being front == rear and the full condition being (rear + 1) % MaxSize == front, so that the queue holds at most MaxSize-1 elements.
The second way: add a size member that records the number of elements in the queue, the empty condition being size == 0 and the full condition being size == MaxSize.
The third way: add a tag member that records the type of the latest operation, tag=0 meaning the latest operation was a deletion and tag=1 meaning the latest operation was an insertion, the empty condition being front == rear && tag == 0 and the full condition being front == rear && tag == 1.

Answer:

A circular queue is the ring formed by joining the head and the tail of the array of a sequential queue, the circular movement of the pointers being realized with the modulo operator (%), and it is used to solve the false overflow problem of an ordinary sequential queue and to improve the space utilization. There are three common ways of telling emptiness from fullness: sacrificing one storage unit (empty when front == rear, full when (rear + 1) % MaxSize == front), adding a size member, or adding a tag member that records the type of the latest operation.

Linked Storage

A linked queue is a queue implemented with a linked list, and it has to maintain both a front pointer and a rear pointer. For the sake of convenience, a dummy head node is usually attached.

Storage Structure

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front;  // front pointer
    LinkNode *rear;   // rear pointer
} LinkQueue;

Basic Operations

Initialization

void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));  // dummy head node
    Q.front->next = NULL;
}

Testing for Emptiness

bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

Enqueue (insert at the tail)

bool EnQueue(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;  // insert the new node at the rear
    Q.rear = s;         // update the rear pointer
    return true;
}

Dequeue

bool DeQueue(LinkQueue &Q, int &x) {
    if (QueueEmpty(Q)) return false;
    LinkNode *p = Q.front->next;  // p points at the node of the front element
    x = p->data;
    Q.front->next = p->next;      // the head node points at the new front
    if (Q.rear == p) {             // if the last element is the one deleted
        Q.rear = Q.front;          // update the rear pointer to point at the head node
    }
    free(p);
    return true;
}

When a linked queue dequeues an element, pay special attention to the case in which the last element is deleted! The rear pointer has to be updated as well so that it points at the head node, otherwise rear becomes a dangling pointer.

Time complexity: all the operations are $O(1)$ .

Exercises

Exercise 1

The linked list that is most suitable as a linked queue is ( )

A. A circular singly linked list with a front pointer and a rear pointer B. A non-circular singly linked list with a front pointer and a rear pointer C. A circular singly linked list with only a front pointer D. A non-circular singly linked list with only a front pointer

Reference Answer

linked queuefront pointerrear pointercircular linked list

Approach:

This question tests the choice of the underlying linked list structure of a linked queue. The idea is to list the two operations of a queue separately, to point out which pointer each of them needs in order to run in constant time, and then to judge whether a circular structure is necessary.

Steps:

A queue needs to insert at the rear (enqueue) and to delete at the front (dequeue), and the two operations act on the two ends of the linked list.
Only a front pointer allows the dequeue to be performed in $O(1)$ time, and only a rear pointer allows the enqueue to be performed in $O(1)$ time.
A non-circular singly linked list already satisfies the needs of the operations at the two ends and there is no need to maintain a circular link; a list with only one pointer cannot make the operation at the other end $O(1)$ as well.
Therefore the most suitable choice is the non-circular singly linked list with a front pointer and a rear pointer.

Answer:

Exercise 2

Briefly describe what has to be watched out for in the dequeue operation of a linked queue. Why?

Reference Answer

linked queuedequeue operationrear pointerdangling pointer

Approach:

This question tests the boundary handling of the dequeue operation of a linked queue. The idea is to distinguish the case in which the queue still holds several elements from the case in which only the last element is left, to explain that only the latter requires the rear pointer to be modified at the same time, and to describe the consequence of not modifying it.

Steps:

A linked queue usually has a dummy head node, with front pointing at the head node and rear pointing at the node of the rear element; the point to watch out for in the dequeue operation is that the rear has to be updated to point at the head node when the last element is deleted.
When the queue holds several elements, the dequeue only has to modify the next pointer of the head node, and the rear pointer is not affected.
When the queue holds only one element, it is both the front and the rear: after the deletion the next of the head node becomes NULL and the queue is empty, but rear still points at the node that has just been deleted and becomes a dangling pointer.
If rear is not updated, the next enqueue inserts the new node through rear->next, while the memory that rear points at has already been released, which causes a memory error.
Therefore the dequeue has to judge whether the node being deleted is the one that rear points at, and if it is, rear has to be updated to point at the head node (the same as front), so that when the queue is empty both front and rear point at the head node.

Answer:

When the dequeue deletes the last element of the queue, the rear pointer has to be updated at the same time so that it points at the head node; otherwise rear becomes a dangling pointer to memory that has already been released and the next enqueue causes a memory error.

Deques and Priority Queues

Double-Ended Queue (Deque)

A double-ended queue (Double-Ended Queue, abbreviated Deque) is a queue in which both the insertion and the deletion are allowed at both ends.

Classification of Deques

Input-restricted deque: insertion is allowed only at one end, and deletion at both ends
Output-restricted deque: deletion is allowed only at one end, and insertion at both ends
General deque: both the insertion and the deletion are allowed at both ends

The Relationship Between a Deque, a Stack and a Queue

If a deque is restricted to the insertion and the deletion at one end only, it degenerates into a stack
If a deque is restricted to the insertion at one end and the deletion at the other, it degenerates into an ordinary queue

A deque combines the advantages of a stack and of a queue and is therefore very flexible. In practice std::deque in the C++ STL is the implementation of a double-ended queue, and it supports the efficient insertion and deletion of elements at both ends.

Priority Queues

A priority queue (Priority Queue) is a special queue in which every element carries a priority, and the element with the highest priority is always the first to leave the queue instead of the element that was enqueued first.

A priority queue is usually implemented with a heap, and the enqueue and the dequeue operations have a time complexity of $O(\log n)$ .

Typical applications of a priority queue:

Process scheduling in an operating system (scheduling the processes by priority)
The Dijkstra shortest path algorithm (choosing the vertex with the smallest distance)
Huffman coding (choosing the two nodes with the smallest weight)
Event-driven simulators (processing the events in chronological order)

Applications

Breadth-First Search (BFS)

The breadth-first search of a graph uses a queue to hold the vertices that are still waiting to be visited, so that the vertices are visited layer by layer in the order of their distance from the starting vertex.

void BFS(Graph G, int v) {
    InitQueue(Q);
    visited[v] = true;
    EnQueue(Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v);
        visit(v);  // visit the vertex v
        for (each adjacent vertex w of v) {
            if (!visited[w]) {
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
}

Other Applications

Buffer management: such as the keyboard input buffer and the printer job queue
Task scheduling in an operating system: the ready queue and the waiting queue
Network packet transmission: the packets are queued up in a router
Level-order traversal: the level-order traversal of a binary tree
Sliding window: the sliding window maximum problem is implemented with a deque

Fun Facts

The everyday analogy of a queue: the most vivid example of a queue is queuing to buy milk tea. The person who arrives first stands at the front, gets the milk tea first and leaves (first in, first out); the person who arrives later stands at the rear and has to wait until everyone ahead of them has been served. If somebody cuts in line, the first in, first out principle of the queue is broken, and in the language of data structures that is exactly the use of a priority queue, where the person who cuts in line has the higher priority.

The number-ticket system of a bank: the number-ticket system of a bank is a typical application of a queue. A customer takes a number and enters the waiting queue, and the numbers are called in the order in which they were taken (first in, first out). But the VIP customers of a bank are served first, and this introduces the notion of a priority queue, in which the VIP customers have the higher priority and are allowed to cut in ahead of the ordinary customers.

Summary

A queue is a first in, first out linear list, all of whose operations are $O(1)$ ; what really takes thought is the management of the space, the false overflow of an ordinary sequential queue and the way a circular queue joins the head and the tail of the array with the modulo operator. The terminology table aligns the terms enqueue, dequeue, circular queue and priority queue with their English names, and the key takeaways list the complexity and the solution of the false overflow that have to be remembered.

Terminology Reference

Term	Abbreviation	Explanation
Queue	-	A first in, first out linear list
Front	-	The end at which the deletion is allowed
Rear	-	The end at which the insertion is allowed
Enqueue	-	Inserting an element at the rear
Dequeue	-	Deleting the front element
Circular queue	-	A queue whose array is joined head to tail
Linked queue	-	A queue implemented with a linked list
Deque	-	A queue that allows the insertion and the deletion at both ends
Priority queue	-	A queue that dequeues by priority
First in, first out	FIFO	First In First Out
False overflow	-	The space waste of an ordinary sequential queue

Key Takeaways

All the operations of a queue (enqueue, dequeue and reading the front) have a time complexity of $O(1)$
The circular queue solves the false overflow problem of the ordinary sequential queue
The full condition of a circular queue: (rear + 1) % MaxSize == front (one unit of space is sacrificed)
The number of elements of a circular queue: (rear - front + MaxSize) % MaxSize
When a linked queue dequeues its last element, the rear pointer has to be updated
A deque combines the characteristics of a stack and of a queue and is therefore very flexible
A priority queue is usually implemented with a heap, and the time complexity is $O(\log n)$

Stack

Arrays and Special Matrices

Found an issue with this content?

Tell us what could be improved.

Your membership covers this course — no need to buy it again.

Login Required to Purchase

Payment Failed

Payment Successful!

Queues

Questions This Chapter Answers

Basic Concepts

Characteristics

Basic Operations

Exercises

Exercise 1

Exercise 2

Exercise 3

Sequential Storage

The Problem with an Ordinary Sequential Queue

Circular Queue

Storage Structure

Initialization

Testing for Emptiness

Testing for Fullness

Enqueue

Dequeue

Queue Length

Exercises

Exercise 1

Exercise 2

Exercise 3

Linked Storage

Storage Structure

Basic Operations

Initialization

Testing for Emptiness

Enqueue (insert at the tail)

Dequeue

Exercises

Exercise 1

Exercise 2

Deques and Priority Queues

Double-Ended Queue (Deque)

Classification of Deques

The Relationship Between a Deque, a Stack and a Queue

Priority Queues

Applications

Breadth-First Search (BFS)

Other Applications

Fun Facts

Summary

Terminology Reference

Key Takeaways