Queues

A queue is FIFO

• A queue is First In, First Out (FIFO).
• The first item you add is the first one to leave.
• Think of a line of people: the person at the front is served first.

enqueue and dequeue with a list

• We can build a queue from a Python list.
• enqueue = queue.append(x) — add to the back.
• dequeue = queue.pop(0) — remove and return the front.

queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)

front and empty

• Look at the front without removing it: queue[0].
• A queue is empty when len(queue) == 0.
• Check it is not empty before you dequeue.

queue = [10, 20, 30]
print(queue[0])         # the front
print(len(queue) == 0)  # is it empty?

A note on speed

• pop(0) has to shift every other item forward by one place.
• For a big queue that is slow, so it uses more time.
• Real systems use a circular buffer with front and rear pointers instead.

In Cambridge pseudocode

• The exam builds a queue from an array with a front and a rear pointer.

DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0           // empty

// enqueue value
rear ← rear + 1
queue[rear] ← value

// dequeue into value
value ← queue[front]
front ← front + 1

Common mistakes

• A queue is first-in, first-out: join the back, leave from the front.
• Check it is not empty before you dequeue.

Now you try

• Use a list as your queue (append to enqueue, pop(0) to dequeue).
• Press Check answer to test your code.