Data Structures and Algorithms (DSA27) · Week 7

Queues (Lecture 07)

These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.

Quizzes Previous week Next week Midterm exam simulator Timed test on this lecture

W7-M01 Recall

"FIFO" means:
W7-M02 Apply

enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4), dequeue(). What does the next dequeue() return?
W7-M03 Explain

In SlowQueue, dequeue is pop(0) on a DynamicArray. Its cost on a queue of n items is:
W7-M04 Explain

An array-based queue that enqueues with insert_at(0, x) and dequeues with pop() at the end has costs:
W7-M05 Apply

A CircularQueue with capacity 8 has head = 6 and size = 3. The next enqueue writes to slot:
W7-M06 Apply

A CircularQueue with capacity 5 has head = 4 and size = 2. After one dequeue, head is:
W7-M07 Recall

A ring buffer that stores only head and tail (no size) finds head == tail. The queue is:
W7-M08 Explain

CircularQueue keeps a _size field because:
W7-M09 Apply

A full ring of capacity 4 holds [E, F, C, D] with head = 2. It grows to capacity 8 by copying new[i] = old[i] and keeping head = 2. Read front to back, the queue is now:
W7-M10 Recall

A queue on a singly linked list with head and tail references should put the front of the queue at:
W7-M11 Explain

Why not dequeue at the tail of a singly linked list?
W7-M12 Apply

A queue built from two stacks (inbox and outbox, pouring only when outbox is empty): enqueue(1), enqueue(2), enqueue(3), dequeue(). How many items are now in outbox?
W7-M13 Explain

The cost of dequeue on that two-stack queue is:
W7-M14 Recall

Which of these needs a queue?
W7-M15 Apply

n enqueues followed by n dequeues on a SlowQueue cost in total:
W7-M16 Apply

In Python, (0 - 1) % 8 is:
W7-M17 Recall

A deque is a structure that:
W7-M18 Explain

Measured, a ring-buffer dequeue and a linked-queue dequeue are both flat lines as n grows, but the ring is about five times slower. The reason:
W7-M19 Apply

Five people A, B, C, D, E stand in a circle; counting from A, every second person leaves. Who is left last?
W7-M20 Apply

An array queue with a head index but no wrap-around, 8 slots: 8 enqueues, then 5 dequeues. How many more enqueues fit without growing the block?
W7-M21 Explain

A CircularQueue that doubles its capacity when full has an enqueue cost of:
W7-M22 Recall

A priority queue (Week 12) differs from a queue because it dequeues:
W7-M23 Apply

A CircularQueue(4), starting empty: enqueue(1), enqueue(2), enqueue(3), enqueue(4), dequeue(), dequeue(), enqueue(5). Which describes the ring now?
W7-M24 Apply

A CircularQueue(5), starting empty: enqueue A, B, C, D, E; dequeue three times; enqueue F, then G. What is in the block, from slot 0 to slot 4?
W7-M25 Apply

A full CircularQueue of capacity 4 holds C D E F (front to back), with head = 2. enqueue(G) makes the correct _grow double the block first. Afterwards, head is ___ and G is in slot ___:
W7-M26 Explain

A student's _grow copies in queue order into an Array(8) and sets head = 0, but forgets to set self._capacity = 8. On the full ring of W7-M25, enqueue(G) then:
W7-M27 Explain

A dequeue updates the head with self._head += 1 instead of self._head = (self._head + 1) % self._capacity. On a CircularQueue(4): enqueue A, B, C, D; dequeue four times; enqueue E; dequeue. What happens?
W7-M28 Explain

A linked queue's enqueue tests if self._tail is None: to decide that the queue is empty, and its dequeue moves head on but never resets tail. After enqueue(1), dequeue(), enqueue(2), the next dequeue():
W7-M29 Apply

A queue from two stacks (pour only when outbox is empty). Count every push and pop on the two stacks, including the pours: enqueue 1, 2, 3; dequeue; enqueue 4, 5; dequeue three times. How many stack operations is that in total?
W7-M30 Recall

A ring buffer that leaves one slot unused to tell full from empty has a block of 8 slots. It holds at most:
W7-M31 Apply

A ring with 8 slots stores only head and tail and leaves one slot unused. Now head = 3 and tail = 2. How many items does it hold, and is it full?
W7-M32 Explain

CircularQueue.dequeue sets the slot it read back to None. Why?
W7-M33 Recall

Which of these is a typical use of a ring buffer?
W7-M34 Apply
What does this print?
```
q = CircularQueue()
q.enqueue("1")
for _ in range(6):
    s = q.dequeue()
    print(s, end=" ")
    q.enqueue(s + "0")
    q.enqueue(s + "1")
```
The queue gives breadth-first order: the children of 1 (10, 11) are dequeued before the children of 10 (100, 101), and those before the children of 11 (110, 111). That is the binary numbers 1 to 6, in order. (b) follows one branch only (depth-first); (d) swaps 100 and 101; (c) enqueues s + "1" first.
W7-M35 Apply

Six people, 1 to 6, are put in a queue. Until one is left: move two people from the front to the back, then dequeue the third, who leaves. In what order do they leave, and who is left?
W7-M36 Recall

A graph search dequeues a node, then enqueues its unvisited neighbours, and repeats. If the queue is replaced by a stack (pop instead of dequeue, push instead of enqueue), the same loop:
W7-M37 Recall

With Python's collections.deque, the O(1) way to remove the front item of a queue d is:
W7-M38 Explain

A moving average of the last k readings keeps a CircularQueue(k) and a running total beside it. The running total is there because:
W7-M39 Apply

A CircularQueue with capacity 6 has head = 4 and size = 5. Front to back, the queue's items are in slots:
W7-M40 Explain

A naive _grow copies new[i] = old[i] and keeps head. It passes a test that fills a fresh CircularQueue(4) with A, B, C, D and then enqueues E. Why does the test not catch the bug?

32 marks

Written questions

9 written questions (32 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.

Written total: 0 / 32

W7-E1 Explain 4 marks

State the Queue ADT with the cost of each operation. Explain why an array-based queue that shifts is O(n) per dequeue, and why swapping which end is the front does not help. How does a ring buffer fix it?
Your answer (saved on this device only)
Model answer and marking points
- ADT: enqueue(x) at the back, dequeue() from the front (FIFO), is_empty, len — all O(1); dequeue raises IndexError when empty.
- Shifting: on a plain array the front is a fixed position, index 0; removing it moves the n − 1 others: O(n).
- Swapping ends does not help: the back at index 0 makes enqueue shift everything instead. A queue uses both ends, and an array is cheap at only one.
- Ring buffer: do not move data, move the indices. head marks the front; the back is (head + size) % capacity; both wrap round with %, so slots freed at the front are reused. Every operation O(1).
W7-E2 Apply 4 marks

In a ring buffer, head == tail can mean two different things. Explain which two, with an example of each, and describe two ways of telling them apart. Which one does dsa/queue.py use?
Your answer (saved on this device only)
Model answer and marking points
- Empty: nothing in the ring, e.g. a new queue: head = tail = 0.
- Full: the tail has caught up with the head, e.g. capacity 4, head 2, four items: tail = (2 + 4) % 4 = 2.
- Fixes: (1) keep a count size — empty is size == 0, full is size == capacity; (2) leave one slot always unused — full is (tail + 1) % capacity == head, so head == tail means only empty; (3) a flag set when an enqueue makes head equal tail.
- dsa/queue.py keeps _size (and computes the tail from it).
W7-E3 Explain 4 marks

A full CircularQueue must grow. Explain, with an example, why copying the block slot by slot gives a wrong queue once the data has wrapped, give the correct copy, and explain why doubling keeps enqueue amortised O(1).
Your answer (saved on this device only)
Model answer and marking points
- Example: capacity 4, head 2, block [E, F, C, D], queue C D E F. A slot-by-slot copy into 8 slots keeps C, D in slots 2, 3 and E, F in slots 0, 1; with head 2 the queue now reads C, D, then empty slots — E and F are lost behind the front.
- Correct copy: in queue order: new[i] = old[(head + i) % old_capacity] for i in 0..size − 1, then head = 0 (and the capacity updated).
- Amortised O(1): a copy happens only when the ring is full, and doubling means the copies after n enqueues total 1 + 2 + 4 + … < 2n: O(n) over n operations, O(1) each on average.
- It only goes wrong once the data has wrapped, which is why it survives tests that never dequeue before growing.
W7-E4 Explain 3 marks

Describe a queue built from two stacks. Show that it is amortised O(1) per operation, and explain why pouring must happen only when the outbox is empty.
Your answer (saved on this device only)
Model answer and marking points
- inbox takes every enqueue; dequeue pops outbox, and when outbox is empty it first pours all of inbox into it — which reverses them, so the oldest is on top.
- Amortised: each item is pushed on inbox once, moved to outbox once and popped once — three O(1) steps in its life, so n operations cost O(n).
- Pour only when empty: pouring into a non-empty outbox would put newer items on top of older ones and break FIFO; pouring back and forth on every dequeue keeps FIFO but costs O(n) per dequeue (W7-K3).
W7-E5 Explain 3 marks

Compare the ring buffer and the linked queue (with head and tail): cost per operation, memory, and when you would choose each. Where does Python's collections.deque fit?
Your answer (saved on this device only)
Model answer and marking points
- Ring buffer: O(1) (amortised if it grows); one contiguous block, no allocation per item, good locality. Choose it when the maximum size is known or bounded — hardware and OS buffers — or for speed in general.
- Linked queue: O(1) worst case, never copies; but a node per item (more memory, scattered). Choose it when a worst-case guarantee matters more than memory.
- collections.deque combines them: a doubly linked list of fixed blocks — O(1) at both ends, few allocations. It is what to use in real Python code.
W7-E6 Explain 4 marks

Three ring-buffer bugs: the tail computed as head + size with no %; the head moved with head += 1 with no %; and a _grow that never updates _capacity. For each, say what goes wrong and the shortest operation sequence that shows it. Why do all three pass a test that never wraps the ring?
Your answer (saved on this device only)
Model answer and marking points
- No % on the tail: once the back reaches the end of the block, the write goes to slot capacity and the Array raises IndexError, although there are free slots at the front. Shortest: CircularQueue(2): enqueue, enqueue, dequeue, enqueue (tail = 1 + 1 = 2).
- No % on the head: dequeues work until head reaches capacity; the next dequeue reads slot capacity and raises. Shortest: CircularQueue(1): enqueue, dequeue (head = 1), enqueue (written to (1 + 0) % 1 = 0), dequeue.
- _capacity not updated in _grow: the new block is bigger, but every % still wraps at the old size, so the next enqueue after the grow overwrites the front, silently. Shortest: fill a ring of capacity 1, enqueue twice more.
- Why the tests miss them: while the ring has not wrapped, head is 0 and head + size is below the capacity, so % changes nothing. Every test must take the ring round at least once, and grow it after it has wrapped.
W7-E7 Explain 3 marks

When a ring buffer is full, it can refuse (a bounded queue) or grow. Explain both choices, give a real use for each, and say which level_order and bfs need, and why.
Your answer (saved on this device only)
Model answer and marking points
- Refuse (bounded): raise an error, or make the producer wait, or drop data when full. Memory is fixed. Used for audio and network buffers, and keyboard buffers, where memory must not grow.
- Grow: allocate a block twice as big and copy in queue order; enqueue stays amortised O(1). Used for general-purpose queues such as collections.deque.
- level_order and bfs need a growing queue: they cannot know in advance how many nodes will be waiting at once (a whole level of a tree, a whole frontier of a graph), and refusing would make the search fail.
W7-E8 Apply 4 marks

Describe enqueue and dequeue for a queue on a singly linked list with head and tail, including the empty cases. Explain why the front must be the head, and what goes wrong if dequeue does not reset tail when the queue becomes empty.
Your answer (saved on this device only)
Model answer and marking points
- enqueue: make a node. If the queue is empty, it becomes both head and tail; otherwise set tail.next to it and move tail to it. O(1).
- dequeue: IndexError if empty; otherwise take head.value, move head to head.next; if head is now None, set tail = None too. O(1).
- Front at the head: removing at the head is O(1); removing the last node of a singly linked list needs the node before it, an O(n) walk. So we add at the tail and remove at the head.
- Stale tail: tail still refers to the removed node. If enqueue tests tail to detect emptiness, the new node is linked after that dead node and head stays None: len says 1, but the next dequeue raises. (If it tests head, the bug hides, but tail still keeps a dead node alive.)
W7-E9 Explain 3 marks

Explain why breadth-first order needs a queue, using the binary numbers 1, 10, 11, 100, … generated from "1" (dequeue s, enqueue s + "0" and s + "1"). What order do you get if the queue is replaced by a stack, and why?
Your answer (saved on this device only)
Model answer and marking points
- A queue hands items back in the order they were discovered: everything at one level is dequeued before anything at the next. From "1": dequeue 1, enqueue 10, 11; dequeue 10, enqueue 100, 101; dequeue 11, enqueue 110, 111…
- So the order is 1, 10, 11, 100, 101, 110, 111, …: the binary numbers in increasing order, level by level (by length).
- With a stack, the last item found comes out first: 1, 11, 111, 1111, … (with s + "0" pushed before s + "1"). The search goes deep along one branch and never comes back to 10. That is depth-first order, as in Week 14.

Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:

Question bank (PDF) Answers (PDF) Course repository