Queues: linear, circular and priority

Front and rear pointers, wrapping round with MOD, and priority queues: a command queue for the robot.

A3.3Data structuresA level20 min

A robot that takes commands over the radio cannot always act on them as fast as they arrive. It keeps them in a queue: the first command in is the first one carried out. This lesson builds queues three ways, and uses the most useful of them, the circular queue, as BugBot's command buffer.

The queue

A queue is a first in, first out (FIFO) structure. Items join at the rear and leave from the front, like people waiting at a counter. Its operations:

A stack has one pointer; a queue built on an array needs two, front and rear, because it works at both ends.

A linear queue

The simplest array queue starts with front = 0 and rear = -1. Enqueue adds 1 to rear and stores the item there; dequeue reads the item at front and adds 1 to front.

Here is the problem. Both pointers only ever move up the array. After four enqueues and two dequeues in an array of size 4, the queue holds two items, but rear is at the last index, so the queue reports full. The two free slots at the start can never be used again.

There are two fixes. The first is to shuffle every item down one place after each dequeue, which keeps front at 0 but means moving every item every time: slow for a long queue. The second is to let the pointers wrap round to the start, which is a circular queue.

Python's list used as a queue, with append and pop(0), is a dynamic linear queue that shuffles: pop(0) moves every remaining item down one place.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

commands = []                               # a Python list used as a queue
for side in range(4):
    commands.append(("forward", 20))        # enqueue at the rear
    commands.append(("turn", 90))

while len(commands) > 0:
    kind, amount = commands.pop(0)          # dequeue from the front
    print("doing", kind, amount, "with", len(commands), "still waiting")
    if kind == "forward":
        forward(50, distance=amount)
    else:
        turn_right(30, angle=amount)

Run this in the simulator

The circular queue

In a circular queue the array is treated as a ring: when a pointer passes the last index it goes back to 0. The MOD operator does this in one step:

rear = (rear + 1) MOD size
front = (front + 1) MOD size

When front and rear can wrap, they can end up in the same relative positions for a full queue as for an empty one, so the simplest reliable test is to keep a count of the items as well.

Trace a circular queue of size 4, starting with front = 0, rear = -1, count = 0:

Every slot is reused, and each operation changes only a pointer and the count, however long the queue.

Priority queues

In a priority queue each item has a priority, and dequeue removes the item with the highest priority rather than the oldest. Items of equal priority leave in the order they arrived. A robot's "stop, you have bumped something" should jump ahead of "take a photo".

One way to build it: on enqueue, walk along the queue and insert the new item after every item of the same or more urgent priority. Dequeue is then an ordinary dequeue from the front.

def enqueue(queue, item, priority):
    """Insert so the queue stays in priority order: 1 is most urgent. Equal priorities keep arrival order."""
    i = 0
    while i < len(queue) and queue[i][1] <= priority:
        i = i + 1
    queue.insert(i, (item, priority))

jobs = []
enqueue(jobs, "drive to dock", 3)
enqueue(jobs, "report battery", 2)
enqueue(jobs, "stop: bumped", 1)
enqueue(jobs, "take photo", 3)
enqueue(jobs, "beep", 2)
while jobs:
    item, priority = jobs.pop(0)
    print(priority, item)

Run this in the simulator

The <= matters: with <, a new job would go in front of older jobs of the same priority, and they would no longer leave in arrival order.

Where queues are used

• Buffers: keystrokes waiting for a program, data waiting to be sent to a printer or over a network, commands waiting for a robot.
• Scheduling: processes waiting for the processor (round robin uses a circular queue; module A10), and priority scheduling uses a priority queue.
• Breadth-first search of a graph (module A4), and Dijkstra's shortest path, which uses a priority queue (module A5).
• Simulations of real queues, such as traffic or customers.

Task: the command queue

Build a static circular queue at the top level of the program: an array queue of SIZE elements (here 3), with front starting at 0, rear at -1 and count at 0. Wrap both pointers with %. Do not use the list's own append, pop or insert.

• Write enqueue(item): if the queue is full return -1; otherwise store the item and return the index of the slot it went into.
• Write dequeue(): if the queue is empty return None; otherwise remove the item at the front and return it.

Each function changes pointers, so give it a global line naming the ones it changes. Then go through EVENTS in order:

• "add <command>": enqueue the command (the text after add). Print added <command> at <slot>, for example added forward 20 at 0, or full, dropped <command> if it did not fit.
• "run": dequeue a command, print ran <command>, and carry it out with do(command).

A dropped command must never be carried out.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def do(command):
    """command is a string such as "forward 20": a direction and a whole number of cm."""
    move, cm = command.split()
    cm = int(cm)
    if move == "forward":
        forward(50, distance=cm)
    elif move == "backward":
        backward(50, distance=cm)
    elif move == "left":
        left(50, distance=cm)
    elif move == "right":
        right(50, distance=cm)

SIZE = 3
queue = [None] * SIZE
front = 0
rear = -1
count = 0

def enqueue(item):
    return -1

def dequeue():
    return None

EVENTS = ["add forward 20", "add right 20", "run", "add forward 15", "add left 10",
          "add backward 50", "run", "run", "run"]

Challenges

1. Write the circular queue without count, using only front and rear. You will need to leave one slot always empty: explain why.
2. Add a peek() that returns the front item without removing it.
3. Change the priority queue so the most urgent job is found when dequeuing rather than when enqueuing. Which operation is now slow?