The Queue: Two Ends

Get access to whole semester resourcesSemester Pass

Chapter Forty

Syllabus topic Module 1, "Queues: Queue ADT"

Pages 122 to 124 of 411

In one line

A queue adds at one end and removes from the other, so the first thing in is the first thing out, which is what fairness means when things are served in the order they arrived.

First in, first out

Stand in a queue at a bank. You join at the back. You are served from the front. The person who has been waiting longest goes next.

That is a queue, and the rule is FIFO, first in, first out.

The queue	The operation
join at the back	enqueue
serve the person at the front	dequeue
see who is next without serving them	front, or peek
is anyone waiting	is_empty

The vocabulary differs between textbooks: rear, back and tail all mean the end you add to, and front and head mean the end you take from. MU prints "Queue ADT" without fixing the words, so an answer may use any consistent pair, and this book uses front and rear.

Stack against queue

This is the comparison to have ready.

	Stack	Queue
Rule	last in, first out	first in, first out
Add at	the top	the rear
Remove from	the top	the front
Ends used	one	two
Natural for	nesting	waiting
Order out	reversed	preserved
Everyday example	a pile of plates	a queue at a counter

The deepest difference is the last two rows. A stack reverses; a queue preserves. A stack is right when the most recent thing must be dealt with first; a queue is right when the oldest must.

Seen side by side:

from collections import deque

items = ["first", "second", "third", "fourth"]

stack = []
for item in items:
    stack.append(item)
stack_out = []
while stack:
    stack_out.append(stack.pop())

queue = deque()
for item in items:
    queue.append(item)
queue_out = []
while queue:
    queue_out.append(queue.popleft())

print("put in       :", items)
print("stack gives  :", stack_out)
print("queue gives  :", queue_out)
print()
print("the stack reversed the order  :", stack_out == list(reversed(items)))
print("the queue preserved the order :", queue_out == items)

put in       : ['first', 'second', 'third', 'fourth']
stack gives  : ['fourth', 'third', 'second', 'first']
queue gives  : ['first', 'second', 'third', 'fourth']

the stack reversed the order  : True
the queue preserved the order : True

Same four items, same order in, opposite orders out. Nothing else about the two structures matters as much as that.

Why two ends is harder than one

The stack was easy because everything happened at one place. A queue works at both ends, and that causes the one real difficulty of the next three chapters.

On a linked list, adding at the head and removing at the head are both cheap, but a queue needs one operation at each end, and one of those ends is expensive unless a pointer is kept there. Chapter 43 solves it with head and tail.

The Queue: Two Ends

On an array, removing from the front means shifting everything down, which is O(n), or leaving a gap and moving the front marker, which wastes the space in front and eventually reports the queue as full when it is nearly empty. Chapter 42 demonstrates that failure and chapter 44 fixes it.

Neither problem arose for the stack. The second end is what costs.

Where queues are already working

Job scheduling. MU names this application by name, and chapter 48 builds it: processes waiting for the processor, served in arrival order.

Printing. Documents sent to a printer are served in the order they were sent.

Breadth first search. Chapter 94 explores a graph level by level with a queue, exactly as chapter 62 walks a tree with one. The stack goes deep; the queue goes wide.

Buffers. Data arriving faster than it can be handled waits in a queue, and the circular queue of chapter 44 is the standard implementation.

Quick revision

A queue adds at the rear and removes from the front: first in, first out.
Operations: enqueue, dequeue, front, is_empty.
Rear, back and tail mean the adding end; front and head mean the removing end.
A stack reverses the order; a queue preserves it. That is the deepest difference.
A stack works at one end, a queue at two, and the second end is what makes the implementations harder.
On an array, removing from the front shifts everything or wastes the space in front; on links, one end

needs a pointer kept to it.

Used for job scheduling, printing, breadth first search and buffers.

Test yourself

1. What does FIFO mean and how does it differ from LIFO? First in, first out: the item that has waited longest is removed next. LIFO removes the most recently added item.

2. Name the queue operations and the two ends. Enqueue at the rear, dequeue from the front, front or peek to look without removing, and is_empty. Rear, back and tail name the adding end; front and head the removing end.

3. Four items go into a stack and a queue in the same order. How do the outputs differ? The stack gives them back reversed; the queue gives them back in the original order.

4. Why are queue implementations harder than stack implementations? Because a queue works at two ends. On a linked list one end needs a pointer kept to it; on an array, removing from the front either shifts everything or leaves unusable space at the front.

5. Give the two problems the array queue has, and which chapters solve them. Shifting everything down on every dequeue, which is O(n); or moving a front marker, which wastes the space in front and reports full when nearly empty. Chapter 42 demonstrates it and chapter 44 fixes it with wrap-around.

The Queue: Two Ends

6. Name three places a queue is already at work. Job scheduling for the processor, documents waiting at a printer, and breadth first search of a graph or tree. Buffers for data arriving faster than it is handled are a fourth.

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