The Queue ADT

Get access to whole semester resourcesSemester Pass

Chapter Forty-One

Syllabus topic Module 1, "Queues: Queue ADT"

Pages 125 to 127 of 411

In one line

The queue ADT is enqueue, dequeue, front, is_empty and size, with underflow on an empty queue and overflow on a full one, and every operation should be O(1).

The ADT

A Queue holds a sequence of items, added at one end called the rear and removed from the other end called the front.

Operation	Needs	Returns	Does	When it cannot
`Queue()`	nothing	an empty queue	creates it	never fails
`enqueue(item)`	an item	nothing	adds at the rear	overflow if full
`dequeue()`	nothing	an item	removes and returns the front	underflow if empty
`front()`	nothing	an item	returns the front, leaves it	error if empty
`is_empty()`	nothing	true or false	is there nothing in it	never fails
`size()`	nothing	a number	how many items	never fails

As with the stack, that table names no array and no linked list, and adding all operations are O(1) is worth a mark.

The names an examiner may use

Textbooks differ, and MU does not fix the words, so know the pairs:

This book	Also written
enqueue	insert, add, push
dequeue	delete, remove, pop, serve
front	head, peek, first
rear	back, tail, last

push and pop for a queue are used by some textbooks and are a genuine source of confusion with stacks. This book does not use them for queues.

Underflow and overflow, again

Exactly as for the stack, and for the same reasons:

Underflow is dequeueing or reading the front of an empty queue. It applies to every implementation, because emptiness belongs to the queue and not to its storage.

Overflow is enqueueing onto a full queue. It applies only where the capacity is fixed, which is the array implementations of chapters 42 and 44. The linked queue of chapter 43 has no maximum.

The ADT obeyed, on Python's own queue

Before building anything, here is the behaviour the next three chapters must reproduce, using a structure the standard library already provides.

from collections import deque


class Queue:
    """The ADT, on top of a deque, so the behaviour can be seen before it is built."""

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from an empty queue: underflow")
        return self._items.popleft()

    def front(self):
        if not self._items:
            raise IndexError("front of an empty queue: underflow")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

    def snapshot(self):
        return list(self._items)


q = Queue()
print("new queue: empty =", q.is_empty(), "| size =", q.size())

for person in ("Asha", "Rohit", "Meera"):
    q.enqueue(person)
    print("enqueue %-6s -> %-28s front is %s"
          % (person, str(q.snapshot()), q.front()))

print()
print("dequeue ->", q.dequeue(), "| now", q.snapshot())
print("dequeue ->", q.dequeue(), "| now", q.snapshot())
print("front   ->", q.front(), "| size is still", q.size())

print()
empty = Queue()
for operation in ("dequeue", "front"):
    try:
        getattr(empty, operation)()
    except IndexError as e:
        print("%-8s on an empty queue ->" % operation, e)

The Queue ADT

new queue: empty = True | size = 0
enqueue Asha   -> ['Asha']                     front is Asha
enqueue Rohit  -> ['Asha', 'Rohit']            front is Asha
enqueue Meera  -> ['Asha', 'Rohit', 'Meera']   front is Asha

dequeue -> Asha | now ['Rohit', 'Meera']
dequeue -> Rohit | now ['Meera']
front   -> Meera | size is still 1

dequeue  on an empty queue -> dequeue from an empty queue: underflow
front    on an empty queue -> front of an empty queue: underflow

Notice the third enqueue line: the front is still Asha, not Meera. Adding at the rear never changes the front, which sounds obvious and is exactly what the array implementation of chapter 42 gets wrong in a subtle way.

The ADT in examination form

Queue: a collection with insertion at the rear and removal at the front.

enqueue(item): add item at the rear. Overflow if full.

dequeue() : remove and return the front item. Underflow if empty.

front() : return the front item without removing it. Error if empty.

is_empty() : true when the queue holds nothing.

size() : the number of items held.

All operations should be O(1).

The word should in the last line is deliberate, and it is what chapters 42 to 44 are about: a naive array implementation does not achieve it, and getting to O(1) is the work.

Quick revision

The queue ADT: enqueue at the rear, dequeue from the front, front, is_empty, size.
It names no implementation, and every operation should be O(1).
Underflow applies to every implementation; overflow only where capacity is fixed.
Know the alternative names: insert and add for enqueue, delete and serve for dequeue, head for front,

back and tail for rear.

Adding at the rear never changes the front.
The naive array implementation does not achieve O(1), which is the point of the next three chapters.

Test yourself

1. Write the queue ADT. A collection with insertion at the rear and removal at the front. enqueue(item) adds at the rear, overflow if full; dequeue() removes and returns the front, underflow if empty; front() returns the front without removing it; is_empty(); size(). All operations should be O(1).

2. Which implementations can overflow, and which can underflow? Any fixed capacity implementation can overflow, which means the array versions. Every implementation can underflow.

3. Give three alternative names for dequeue. Delete, remove, serve. Some textbooks also write pop, which is best avoided because of the stack.

4. Does enqueueing change the front of the queue? No, unless the queue was empty. Adding happens at the rear.

5. Why does the ADT say operations "should" be O(1) rather than "are"? Because it is a target the implementation must achieve. The naive array queue does not: its dequeue shifts every remaining item and is O(n).

The Queue ADT

6. What is the difference between front() and dequeue()? front() returns the front item and leaves the queue unchanged; dequeue() removes it and returns it, reducing the size by one.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue