Lesson 5.17

A problem a queue solves

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

Java answers can't run on Spine yet. You can still read Java, trace it, and put an answer's lines in order.

Uses of a queue: problems a queue solves

By the end of this you will be able to spot a problem that a queue solves well, and explain why a queue fits it.

A ticket office has one window. People join a line, and the person at the front is served next. Here is that as a flowchart. Follow it with three people in the line.

Each time round, the person who has waited longest is at the front, so they are the one served. Nobody is skipped, and nobody jumps ahead.

The sign of a queue problem

A queue fits a problem when the thing you need next is always the oldest thing still waiting. Ask yourself: when I take something, do I want the one that arrived first? If the answer is always yes, a queue fits.

Problems like this often have one of these shapes:

Serving in order of arrival. Customers at a ticket office, or callers waiting on a phone line, are served in the order they came.
Keeping things in the order they happened. Keys pressed while a computer is busy are stored, then handled in the order they were typed.
Taking turns. Each one gets a short go, then waits again behind everyone else, so a slow job cannot hold up the rest.

Serving a line

Here is the ticket office from the flowchart in code. The list is the queue, with index 0 as the front.

queue = ["Lena", "Omar", "Priya"]
while len(queue) > 0:
    name = queue.pop(0)
    print("Serving " + name)
print("Window closed")

import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<String> queue =
        new ArrayList<>();
    queue.add("Lena");
    queue.add("Omar");
    queue.add("Priya");
    while (queue.size() > 0) {
        String name = queue.remove(0);
        System.out.println("Serving " + name);
    }
    System.out.println("Window closed");
}

When it runs:

Serving Lena
Serving Omar
Serving Priya
Window closed

Here is the queue, front first, each time the loop reaches its check:

Check	Queue, front first	What happens
1	[Lena, Omar, Priya]	not empty, so serve Lena
2	[Omar, Priya]	not empty, so serve Omar
3	[Priya]	not empty, so serve Priya
4	[]	empty, so the loop ends

The loop asks the same question as the diamond in the flowchart. It stops only when nobody is waiting, so it never dequeues from an empty queue.

When a queue is the wrong tool

A queue only gives you the oldest value. Some problems want something else.

Undo wants the newest change first. That is a stack, from the lesson before last.
A hospital sees the most urgent patient first, not the one who arrived first. Neither a plain queue nor a stack fits, because the next one is chosen by how urgent it is, not by when it arrived.
If you need to read any value at any time, use a plain list.

Explaining why a queue fits

When a question asks you to explain why a queue suits a problem, make two points.

Say what the problem needs next: the item that arrived first, which has waited longest.
Link it to the queue: a queue is first in, first out, so that item is always at the front, and a dequeue gives it straight away.

Here is an explanation for the ticket office. The person to serve next is the one who has waited longest. A queue is first in, first out, so that person is always at the front, and a dequeue gives them without searching the line.

Saying only "a queue is first in, first out" is not enough. You have to show why that order is the one the problem needs.

Now try it yourself on the questions below.

Exercise 5.17.15.17.1 · Write itTake turns on the console

A games club has one console, and the players share it fairly by taking turns. Write a function that works out the order of the turns.

The players are numbered 0, 1, 2 and so on. turns holds how many turns each player wants: player 0 wants turns[0] turns, player 1 wants turns[1], and so on. There are 1 to 10 players, and each wants a whole number of turns from 1 to 5.
At the start, the players stand in a queue in number order, so player 0 is at the front.
Again and again, the player at the front leaves the queue and plays one turn. If that player still wants more turns, they join the back of the queue. If not, they are done.
When the queue is empty, every turn has been played.
Return a list of the player numbers in the order the turns were played, one number for each turn.

For example, if turns holds 2, 1 and 3, the turns go to players 0, 1, 2, 0, 2, 2.

Only the value your function returns is checked.

def round_robin_turns(turns: list[int]) -> list[int]

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

round_robin_turns([2, 1, 3]) should return [0, 1, 2, 0, 2, 2]: the example in the question (rules 3 and 5)
round_robin_turns([1, 1, 1]) should return [0, 1, 2]: one turn each, so each player is done after one go (rule 3)
round_robin_turns([3, 1]) should return [0, 1, 0, 0]: player 0 is left alone in the queue and plays on (rules 3 and 4)
round_robin_turns([1]) should return [0]: one player who wants one turn (rule 4)

public static ArrayList<Integer> roundRobinTurns(int[] turns)

Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

roundRobinTurns(new int[]{2, 1, 3}) should return [0, 1, 2, 0, 2, 2]: the example in the question (rules 3 and 5)
roundRobinTurns(new int[]{1, 1, 1}) should return [0, 1, 2]: one turn each, so each player is done after one go (rule 3)
roundRobinTurns(new int[]{3, 1}) should return [0, 1, 0, 0]: player 0 is left alone in the queue and plays on (rules 3 and 4)
roundRobinTurns(new int[]{1}) should return [0]: one player who wants one turn (rule 4)

solution.pySolution.java

def round_robin_turns(turns: list[int]) -> list[int]:
    # your code here
    pass

Exercise 5.17.25.17.2 · Answer itMessages sent offline

Ravi's phone has no signal on a train. Each message Ravi sends meanwhile waits in an outbox. When the signal comes back, the outbox sends the waiting messages one at a time. The outbox is a queue: a new message joins at the back.

On the train, Ravi sends three messages to a friend, in this order:

"The train has stopped in a tunnel"
"It could be an hour"
"So start dinner without me"

(a) State the messages in the outbox, front first, just before the signal comes back. [1]

(b) The signal comes back. State which message is sent first, and name the queue operation that takes it out of the outbox. [2]

(c) Suppose the outbox were a stack instead. State the order in which the friend would get the three messages, and explain, using what the messages say, why that order is a problem. [2]

[5]

Your answer