Lesson 5.16

Queue: enqueue, dequeue, first in first out

Part 5: Text, lists, stacks and queuesReading, about 7 min2 exercises in this lesson

Queues: first in, first out

By the end of this you will be able to say how a queue behaves, name its operations, use a list as a queue, and work out what a queue holds after a run of enqueues and dequeues.

Think of a line at a bus stop. A new person joins at the back of the line. The bus takes the person at the front. Whoever has waited longest gets on first, and nobody jumps ahead.

What a queue is

A queue is a collection of values with two ends. Values join at one end, called the back (or rear), and leave from the other end, called the front.

Enqueue adds a new value at the back.
Dequeue takes the value at the front off and gives it back.
Front, also called peek, gives back the value at the front and leaves it where it is.
Is empty tells you whether the queue holds no values at all.

Because values join at the back and leave from the front, the value that comes off is always the one that has been in the queue longest. This is called first in, first out, or FIFO for short.

A stack is the opposite. In a stack, values go on and come off at the same end, the top, so the newest value comes off first. In a queue, the oldest value comes off first.

A list as a queue

A Python list or a Java ArrayList can be a queue. Use the end of the list as the back and index 0 as the front.

queue = []
queue.append(12)
queue.append(15)
queue.append(11)
print(queue)
print(queue[0])
first = queue.pop(0)
print(first)
print(queue)
print(len(queue))

import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<Integer> queue =
        new ArrayList<>();
    queue.add(12);
    queue.add(15);
    queue.add(11);
    System.out.println(queue);
    System.out.println(queue.get(0));
    int first = queue.remove(0);
    System.out.println(first);
    System.out.println(queue);
    System.out.println(queue.size());
}

When it runs:

[12, 15, 11]
12
12
[15, 11]
2

The list prints front first, so the front is the value on the left and the back is the value on the right. The 12 joined first, so it is at the front, and the dequeue takes it. After that, 15 is at the front, and the queue holds 2 values.

When the front value is taken off, every other value moves along one place, so the new front is at index 0 again. You never have to keep track of where the front is.

Here is what each operation does:

Operation	What it does
enqueue	adds a value at the back
dequeue	takes the front value off and gives it back; an error on an empty queue
front	gives back the front value and leaves it on; an error on an empty queue
is empty	true when the queue holds no values

Here is each one in Python, with queue as the list and v as a value:

Operation	Python list
enqueue	`queue.append(v)`
dequeue	`queue.pop(0)`
front	`queue[0]`
is empty	`len(queue) == 0`

And in Java, with queue as an ArrayList:

Operation	Java `ArrayList`
enqueue	`queue.add(v)`
dequeue	`queue.remove(0)`
front	`queue.get(0)`
is empty	`queue.isEmpty()`

In Java, remove(0) takes off the value at index 0, the front. Java also has ready-made classes for queues, such as ArrayDeque, with methods called offer, poll and peek. In Python, the collections module has a deque with a method called popleft. This course uses a list so that you can see the front and the back.

Enqueues and dequeues in order

To work out what a queue holds, write it down after every operation, front first. Here the queue starts empty.

Step	Operation	Queue after, front first	Value given back
1	enqueue 4	[4]	none
2	enqueue 10	[4, 10]	none
3	dequeue	[10]	4
4	enqueue 6	[10, 6]	none
5	enqueue 2	[10, 6, 2]	none
6	dequeue	[6, 2]	10
7	dequeue	[2]	6

The dequeues gave back 4, 10 and 6, the same order those values were enqueued in. Each dequeue takes whichever value is at the front at that moment, which is the oldest value still in the queue. The 2 joined last, and it is still waiting.

If you enqueued some values and then dequeued them all, they would come off in the same order they went on in. A stack would give them back in the opposite order.

Dequeuing an empty queue

An empty queue has no front. In Python, pop(0) on an empty list stops the program with IndexError: pop from empty list. In Java, remove(0) on an empty ArrayList stops the program with an IndexOutOfBoundsException. Looking at the front of an empty queue is an error in the same way.

So check before you dequeue.

queue = []
if len(queue) == 0:
    print("nobody waiting")
else:
    print(queue.pop(0))

import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<Integer> queue =
        new ArrayList<>();
    if (queue.isEmpty()) {
        System.out.println("nobody waiting");
    } else {
        System.out.println(queue.remove(0));
    }
}

This prints nobody waiting, and the program carries on.

Stack or queue

	Stack	Queue
Where values go in	the top	the back
Where values come out	the top	the front
Which value comes out	the newest one still in it	the oldest one still in it
Short name	LIFO	FIFO

Two common mistakes

Taking from the wrong end. pop() in Python, or remove(queue.size() - 1) in Java, takes the value at the back, the one that joined last. That is a stack. A queue always takes from the front.
Dequeuing without checking. If the queue can be empty at that point, check it first, or the program stops with an error.

Now try it yourself on the questions below.

Exercise 5.16.1 · Trace itTrace: queue moves

Complete the trace table for this Python code. queue is used as a queue: its first value is the front and its last value is the back. append adds a value at the back, and pop(0) takes the front value off and gives it back. Write the queue in square brackets, front first, as Python prints it. Then answer the question below the table. [3]

Line 1: queue = []1queue = []
Line 2: queue.append(3)2queue.append(3)
Line 3: queue.append(8)3queue.append(8)
Line 4: x = queue.pop(0)4x = queue.pop(0)
Line 5: queue.append(5)5queue.append(5)
Line 6: queue.append(x + 4)6queue.append(x + 4)
Line 7: total = 07total = 0
Line 8: while len(queue) > 0:8while len(queue) > 0:
Line 9, indented 1 level: front = queue.pop(0)9    front = queue.pop(0)
Line 10, indented 1 level: if front < 6:10    if front < 6:
Line 11, indented 2 levels: queue.append(front + 4)11        queue.append(front + 4)
Line 12, indented 1 level: else:12    else:
Line 13, indented 2 levels: total = total + front13        total = total + front

Fill in one row each time a line changes queue, x or total. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes.

Row	queue	x	total
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Which values did the while loop take off the queue, in the order it took them?

Exercise 5.16.1 · Trace itTrace: queue moves (Java)

Complete the trace table for this Java code. The code runs with ArrayList already imported. queue is an ArrayList used as a queue: its first value is the front and its last value is the back. add adds a value at the back, and remove(0) takes the front value off and gives it back. Write the queue in square brackets, front first, as Java prints an ArrayList. Then answer the question below the table. [3]

Line 1: ArrayList<Integer> queue =1ArrayList<Integer> queue =
Line 2, indented 1 level: new ArrayList<>();2    new ArrayList<>();
Line 3: queue.add(3);3queue.add(3);
Line 4: queue.add(8);4queue.add(8);
Line 5: int x = queue.remove(0);5int x = queue.remove(0);
Line 6: queue.add(5);6queue.add(5);
Line 7: queue.add(x + 4);7queue.add(x + 4);
Line 8: int total = 0;8int total = 0;
Line 9: while (queue.size() > 0) {9while (queue.size() > 0) {
Line 10, indented 1 level: int front = queue.remove(0);10    int front = queue.remove(0);
Line 11, indented 1 level: if (front < 6) {11    if (front < 6) {
Line 12, indented 2 levels: queue.add(front + 4);12        queue.add(front + 4);
Line 13, indented 1 level: } else {13    } else {
Line 14, indented 2 levels: total = total + front;14        total = total + front;
Line 15, indented 1 level: }15    }
Line 16: }16}

Fill in one row each time a line changes queue, x or total. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes.

Row	queue	x	total
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Which values did the while loop take off the queue, in the order it took them?

Exercise 5.16.25.16.2 · Answer itQueue in words

A school printer is shared by every computer in a classroom. Each print job sent to it joins a queue, and the printer always prints the job at the front of the queue next.

(a) Explain what first in, first out means for the order in which the jobs are printed. [2]

(b) Name the four operations of a queue, and state what each one does. [4]

[6]

Your answer