OCR H446 data structures / AQA 7517 data structures
Implement a queue using collections.deque with enqueue and dequeue operations.
A queue follows first in, first out. Items join at the rear and leave from the front; collections.deque provides efficient operations at both ends. Trace head and tail positions after each enqueue or dequeue.
Watch out: Removing from the front of a normal Python list repeatedly can be less efficient than using a deque.
Study this example, identify inputs and outputs, then trace the key variables. Run and adapt it in Python 3.
from collections import deque
class Queue:
def __init__(self): self.items = deque()
def enqueue(self, value): self.items.append(value)
def dequeue(self):
if not self.items: raise IndexError("queue underflow")
return self.items.popleft()
def is_empty(self): return not self.items
q = Queue(); q.enqueue('A'); q.enqueue('B')
Implement a queue using collections.deque with enqueue and dequeue operations. Download the starter, design your solution, and add tests before revealing the answer.
Download starter + solution ZIP ↓
Stretch task: investigate time/space complexity or data validation, then write an evaluation of your approach.
from collections import deque
class Queue:
def __init__(self): self.items = deque()
def enqueue(self, value): self.items.append(value)
def dequeue(self):
if not self.items: raise IndexError("queue underflow")
return self.items.popleft()
def is_empty(self): return not self.items
q = Queue(); q.enqueue('A'); q.enqueue('B')
assert q.dequeue() == 'A' and q.dequeue() == 'B' and q.is_empty()
print('Queue tests passed')
Change one boundary condition in the starter or reference program. Predict which test fails, then repair it and document why.
Concept check: Why use deque rather than list.pop(0) for a large queue?
deque.popleft() is efficient; removing the first list element shifts the remaining elements.
Describe the algorithm or design in your own words; include a normal test, a boundary test and an invalid input. Compare your answers with the reference solution and record one improvement.
Progress is stored only in this browser.
Want extra practice? Try interactive Python tracing and debugging questions →