Practical 16: Queues and Circular Queues

a linear queue of 5 cells
  new            : [. . . . .]  front 0 rear -1 count 0
  five enqueues  : [10 20 30 40 50]  front 0 rear 4 count 5 full? True
  three dequeues : [. . . 40 50]  front 3 rear 4 count 2
  three cells are free, and now:
    enqueue(60): IndexError: the queue is full (the rear is at the end)

  that is the defect: 3 of 5 cells are free and the queue says it is full,
  because the rear can only move forward and has reached the end.

Read the last two lines of that run. The array has five cells. Two hold items. Three are empty. And enqueue(60) fails.

The reason is in is_full:

def is_full(self):
    return self.rear == self.size - 1

The rear has reached the last cell, so there is nowhere for it to go. The three free cells are at the front, behind front, and a rear that only moves forward can never reach them. This is called queue overflow with free space or simply the rightward drift of a linear queue, and it is the defect the exercise exists to fix.

Two bad answers and one good one:

A Python list with pop(0) is the second of those, and it is what most students write first. It is correct and it is O(n) per dequeue, and [Practical 12: Singly Linked Lists] measured what that costs: 20000 of them were about 99 times slower than the cheap operation.

The circular queue

The whole difference is the modulo operator. Instead of rear = rear + 1, which walks off the end:

self.rear = (self.rear + 1) % self.size
self.front = (self.front + 1) % self.size

With five cells, an index runs 0, 1, 2, 3, 4, 0, 1, 2, and so on for ever. The array becomes a ring.

class CircularQueue:
    """The same fixed array, with the indices wrapping round with %.
    A count is kept, so full and empty can be told apart."""

    def __init__(self, size):
        self.size = size
        self.items = [None] * size
        self.front = 0
        self.rear = -1
        self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.size

    def enqueue(self, item):
        if self.is_full():
            raise IndexError("the queue is full (all cells hold an item)")
        self.rear = (self.rear + 1) % self.size        # THE wrap
        self.items[self.rear] = item
        self.count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("the queue is empty")
        item = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.size      # and THE other wrap
        self.count -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("the queue is empty")
        return self.items[self.front]

    def __len__(self):
        return self.count

    def __repr__(self):
        cells = " ".join("." if x is None else str(x) for x in self.items)
        return f"[{cells}]  front {self.front} rear {self.rear} count {self.count}"


q = CircularQueue(5)
print("a circular queue of 5 cells")
print("  new            :", q)

for x in (10, 20, 30, 40, 50):
    q.enqueue(x)
print("  five enqueues  :", q, "full?", q.is_full())

for _ in range(3):
    q.dequeue()
print("  three dequeues :", q)

for x in (60, 70, 80):
    q.enqueue(x)
print("  three more in   :", q)
print("  and the 60 sits at index 0, because (4 + 1) % 5 is 0")

print()
print("  now it really is full:")
try:
    q.enqueue(90)
except IndexError as e:
    print("    enqueue(90): IndexError:", e)

print()
print("  emptying it, in order:")
while not q.is_empty():
    print(f"    dequeue -> {q.dequeue():<3} {q}")
try:
    q.dequeue()
except IndexError as e:
    print("    one dequeue too many: IndexError:", e)

print()
print("the full-against-empty ambiguity, if no count were kept")
r = CircularQueue(3)
print("  empty       : front", r.front, "rear", r.rear,
      "-> (rear + 1) % size is", (r.rear + 1) % r.size, "which equals front?",
      (r.rear + 1) % r.size == r.front)
for x in (1, 2, 3):
    r.enqueue(x)
print("  and now full: front", r.front, "rear", r.rear,
      "-> (rear + 1) % size is", (r.rear + 1) % r.size, "which equals front?",
      (r.rear + 1) % r.size == r.front)
print("  the indices are identical in both cases, which is why a count is kept.")

Following the wrap

The run is worth reading index by index, because this is what an examiner asks to be traced.

Look at the fourth row. The rear is at index 2 and the front is at index 3, so the rear is behind the front in the array and the queue is still in order: the items come out 40, 50, 60, 70, 80, exactly as they went in. The run proves it by emptying the queue and printing each one.

(4 + 1) % 5 is 0, which is why 60 landed at index 0 with 40 and 50 still in cells 3 and 4. That single expression is MU's "wrap-around logic".

Telling full from empty, which is the real subtlety

When front and rear meet, is the queue empty or full? The last part of the run answers it: with three cells, (rear + 1) % size == front is True when the queue is empty and True again when it is full. The indices cannot tell them apart.

Three standard cures, and MU's syllabus allows any of them:

This chapter keeps a count, which is the clearest and is what len() wants anyway. The second cure is the one to recognise in an examination question, because a question that says "a circular queue of size n can hold n - 1 items" is describing it, and the answer to "why" is exactly this ambiguity.

MU's application: task scheduling

MU asks for the queues to simulate task scheduling, and [Practical 8: CPU Scheduling, Round Robin] in Module 1 already built the scheduler. This is the same ready queue from the other side.

from collections import deque


class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.items = [None] * size
        self.front = 0
        self.rear = -1
        self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.size

    def enqueue(self, item):
        if self.is_full():
            raise IndexError("the queue is full")
        self.rear = (self.rear + 1) % self.size
        self.items[self.rear] = item
        self.count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("the queue is empty")
        item = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return item


class Task:
    def __init__(self, name, work):
        self.name = name
        self.left = work

    def __repr__(self):
        return f"{self.name}({self.left})"


def round_robin(tasks, quantum, cells):
    """The ready queue of Practical 8, as a circular queue of fixed size."""
    q = CircularQueue(cells)
    for t in tasks:
        q.enqueue(t)

    clock, order, switches = 0, [], 0
    while not q.is_empty():
        t = q.dequeue()
        ran = min(quantum, t.left)
        clock += ran
        t.left -= ran
        order.append(f"{t.name}:{ran}")
        if t.left > 0:
            q.enqueue(t)                  # back to the rear, in the SAME cells
            switches += 1
        elif not q.is_empty():
            switches += 1
    return clock, order, switches


tasks = [Task("backup", 5), Task("print", 2), Task("index", 4)]
clock, order, switches = round_robin(tasks, 2, cells=3)
print("a task scheduler on a circular queue of 3 cells, quantum 2")
print("  the order of the slices:", " -> ".join(order))
print(f"  finished at time {clock} with {switches} context switches")
print("  the queue never needed more than 3 cells, however many rounds it took")

print()
print("MU's bullet about memory: what the two queues need for the same work")
print(f"  {'':<22}{'cells':>7}{'items ever held':>18}")
print(f"  {'circular queue':<22}{3:>7}{'3 at a time':>18}")
print(f"  {'linear queue':<22}{'grows':>7}{'3 at a time':>18}")
print("  A linear queue in a fixed array of 3 cells could not do this run at")
print("  all: the first time a task went back to the rear, the rear would")
print("  already be at the end and the enqueue would fail.")

print()
print("a deque: both ends, and what Python provides ready-made")
d = deque([20, 30])
d.append(40)          # at the rear
d.appendleft(10)      # at the FRONT, which a queue cannot do
print("  after append and appendleft :", list(d))
print("  popleft (the queue's dequeue):", d.popleft(), "->", list(d))
print("  pop     (the stack's pop)   :", d.pop(), "->", list(d))
d2 = deque([1, 2, 3], maxlen=3)
d2.append(4)
print("  a deque with maxlen=3, after appending a fourth:", list(d2))
print("  the oldest item was dropped, which is a fixed-size ring in one line")

a task scheduler on a circular queue of 3 cells, quantum 2
  the order of the slices: backup:2 -> print:2 -> index:2 -> backup:2 -> index:2 -> backup:1
  finished at time 11 with 5 context switches
  the queue never needed more than 3 cells, however many rounds it took

MU's bullet about memory: what the two queues need for the same work
                          cells   items ever held
  circular queue              3       3 at a time
  linear queue            grows       3 at a time
  A linear queue in a fixed array of 3 cells could not do this run at
  all: the first time a task went back to the rear, the rear would
  already be at the end and the enqueue would fail.

a deque: both ends, and what Python provides ready-made
  after append and appendleft : [10, 20, 30, 40]
  popleft (the queue's dequeue): 10 -> [20, 30, 40]
  pop     (the stack's pop)   : 40 -> [20, 30]
  a deque with maxlen=3, after appending a fourth: [2, 3, 4]
  the oldest item was dropped, which is a fixed-size ring in one line

What the run shows

Three cells were enough for the whole run, although the three tasks went round the queue six times between them. Every time a task was preempted it went back to the rear, into a cell that had just been vacated at the front, and the modulo found it.

A linear queue of three cells could not have done it at all. The first preemption would have found the rear already at the end and the enqueue would have failed, which is the defect of the first program appearing in a real application. That is MU's memory bullet answered:

A circular queue needs as many cells as the most items held at once. A linear queue needs as

many cells as the total number of enqueues ever made, because the rear never goes back.

For this run: three cells against eleven.

The slices and the switches agree with Module 1. Total work is 5 plus 2 plus 4, which is 11, and the clock ends at 11 because the processor is never idle. Five context switches for six slices, which is the "slices minus one" rule from [Practical 8: CPU Scheduling, Round Robin].

The deque, which is both at once

A deque, short for double-ended queue and pronounced "deck", allows adding and removing at both ends. It is therefore a stack and a queue at the same time, and Python provides one.

collections.deque is implemented as a doubly linked list of small blocks, so all four are O(1), and it is the right answer in real Python code for anything queue-shaped. maxlen makes it a fixed-size ring in one argument, dropping the oldest item when a new one arrives, which is exactly what a circular buffer is used for: the last hundred log lines, the last thirty video frames.

And it is not the answer to this exercise, which asks for the structure to be built.

Where circular queues are used

MU's third bullet asks for a discussion, and the honest answer is that this structure is everywhere in systems programming, under the name ring buffer or circular buffer:

• A keyboard buffer. Keys arrive faster than a program reads them; the ring holds them.
• A network card's receive buffer. Packets arrive; the driver takes them out.
• The bounded buffer of [Practical 5: Process Synchronisation and the Bounded Buffer], which

is this structure with two semaphores round it.

• A pipe, which is a fixed-size ring in the kernel, as

[Practical 2: Process Communication with Pipes] measured at 64 kibibytes.

• The ready queue of a round robin scheduler, as above.
• Audio and video playback, where a fixed number of buffers is filled and drained for ever.

The pattern in all six is the same: a fixed amount of memory, one producer, one consumer, and no allocation at all once it is set up. That last property is why the kernel uses it: allocating memory while handling an interrupt is not allowed, so the buffer has to exist already.

The cost of each operation

Procedure

1. Write the linear queue and reproduce the failure: five enqueues, three dequeues, then one more

enqueue.

1. Write the circular queue. Trace the front, the rear and the array after each of the eight

operations, on paper first.

1. Empty it and check that the items come out in the order they went in, even though the rear is

behind the front in the array.

1. Remove the count and implement is_full as (rear + 1) % size == front instead. The queue

now holds four items in five cells, and that is correct: say why in the journal.

1. Write the scheduler. Change the quantum to 1 and to 5 and note how the number of switches

changes, exactly as in Practical 8.

1. Try the scheduler with cells=2 and three tasks, and read the error.
2. Write is_palindrome(word) using a queue and a stack together: push and enqueue every

character, then pop and dequeue and compare. It is the standard question on this pair of structures.

Result

A linear queue in a fixed array of five cells was built and shown to refuse an item while three of its five cells were free, because the rear can only move forward. A circular queue of the same size was built with the two indices advanced modulo the size, and the array was printed after every operation to show the rear wrapping past the front while the items still left in the order they arrived. The full-against-empty ambiguity was demonstrated, with (rear + 1) % size == front true for both an empty and a full queue of three cells, and resolved by keeping a count. The circular queue was then used as the ready queue of a round robin scheduler, completing eleven units of work in three cells where a linear queue would have needed eleven.

Where marks are lost

• rear = rear + 1 without the modulo. The queue then overflows with free space, which is the

whole defect the exercise is about.

• Only one modulo. Both front and rear wrap.
• No way to tell full from empty. Keep a count, or leave one cell empty, and say which you

chose.

• is_full written as rear == size - 1 in the circular version, which is the linear queue's

test and is wrong here.

• Starting rear at 0 instead of -1, which makes the first enqueue write into cell 1 and

leaves cell 0 permanently unused, or makes an empty queue look as if it holds one item.

• Using a Python list with pop(0) and calling it a queue implementation. Correct, O(n), and

not the exercise.

• dequeue on an empty queue returning None instead of raising.
• Not printing the array, so the wrap cannot be seen and the examiner cannot mark the working.
• Saying a circular queue saves memory over a linked queue. It saves memory over a

linear array queue; a linked queue uses exactly what it needs and a link per item.

For the journal

Write the aim, MU's own wording, and the picture of five cells with front and rear marked. Then the linear queue, its run, and the three free cells beside the refusal, because that failure is the motivation for everything after it. Then the circular queue with the table of the array, front, rear and count after each operation, and the (4 + 1) % 5 is 0 beside the row where the wrap happens. Then the ambiguity, with both index comparisons coming out True, and which cure you chose. Then the scheduler and the three-cells-against-eleven comparison. The conclusion: a linear array queue needs a cell for every item it ever holds, a circular queue needs a cell only for the items it holds at once, and the difference is one modulo operator on each of the two indices.

Quick revision

• A queue is FIFO. Enqueue at the rear, dequeue from the front, and nobody is overtaken.
• A linear queue in a fixed array overflows while cells are free, because the rear only moves

forward. That is the defect.

• A circular queue advances both indices modulo the size, so the array becomes a ring. Two lines,

and the problem is gone.

• When front and rear meet, empty and full look the same. Keep a count, or leave one cell

permanently empty so that a queue of size n holds n - 1 items.

• rear starts at -1 and front at 0, so the first enqueue writes to cell 0.
• Memory: a circular queue needs as many cells as the most items held at once; a linear array

queue needs as many as the total enqueues ever made. In the scheduler here, three against eleven.

• A deque allows both ends. collections.deque gives append, appendleft, pop and popleft all

in O(1), and maxlen makes a fixed-size ring in one argument.

• A Python list with pop(0) is a queue and is O(n) per dequeue.
• A circular queue is also called a ring buffer, and it is what a keyboard buffer, a network card,

a pipe and a bounded buffer are made of, because it allocates nothing once it exists.

• The stack and the queue are the two opposite disciplines: LIFO against FIFO, one end against

two.

Questions you should be able to answer

1. What is the defect of a linear queue in a fixed array? The rear index only moves forward, so once it reaches the last cell the queue reports itself full even though the cells behind the front are free. On the page, three of five cells were free and an enqueue failed.

2. What is the one change that makes it a circular queue? Advancing both indices modulo the size: rear = (rear + 1) % size and the same for front. The array is then reused as a ring.

3. In a circular queue of five cells with the rear at index 4, where does the next item go? Index 0, because (4 + 1) % 5 is 0.

4. Can the rear be at a lower index than the front, and is the queue then out of order? Yes it can, and no it is not. In the run on this page the rear was at 2 and the front at 3, and the items still came out in the order they arrived.

5. When front and rear meet, is the queue empty or full, and how is it decided? It cannot be decided from the indices alone: (rear + 1) % size == front is true in both cases. Either keep a count of the items, or leave one cell permanently empty so that a queue of n cells holds n - 1 items.

6. How many cells does a circular queue need, and how many does a linear one? The circular queue needs as many as the greatest number of items held at once. The linear array queue needs as many as the total number of enqueues that will ever be made, because the rear never returns.

7. What is a deque, and what can it do that a queue cannot? A double-ended queue. It can add and remove at both ends, so it is a stack and a queue at once; a queue can only add at the rear and remove at the front.

8. Give three places a circular queue is used in a real system. A keyboard buffer, a network card's receive ring, and the bounded buffer between a producer and a consumer. A pipe in the kernel is one too. The common reason is that it allocates no memory once it exists.

9. Why is a Python list with pop(0) a poor queue? Because removing the first item shifts every other item down one, so each dequeue is O(n). Measured over 20000 operations, that kind of front operation was about ninety-nine times slower than the cheap one.