Queues (OCR A-Level Computer Science): Revision Notes
📚Revision Notes
Queues
Overview
A queue is a linear data structure that stores data in a First-In, First-Out (FIFO) order. This means the first item added to the queue is the first one to be removed. Queues are commonly used in scenarios where order matters, such as task scheduling, managing print jobs, or simulating real-world lines.
Structure of a Queue
A queue supports two primary operations:
- Enqueue: Adds an element to the back of the queue.
- Dequeue: Removes and returns the element from the front of the queue. Other useful operations include:
- Peek: Retrieves the front element without removing it.
- isEmpty: Checks if the queue is empty.
- isFull (optional in fixed-size implementations): Checks if the queue has reached its capacity.
Types of Queues
- Simple Queue: Basic FIFO structure.
- Circular Queue: Connects the end of the queue back to the beginning, efficiently using available space.
- Priority Queue: Elements are dequeued based on priority rather than order.
- Deque (Double-Ended Queue): Allows insertion and deletion at both ends.
Implementing a Queue
Using Arrays (Procedural Approach)
- Enqueue Operation:
- Check if the queue is full (optional for dynamic arrays).
- Increment the rear pointer.
- Insert the new element at the rear index.
- Dequeue Operation:
- Check if the queue is empty.
- Retrieve the element at the front index.
- Increment the front pointer.
Note
Pseudocode Example:
# Simple Queue using a fixed-size array
MAX_SIZE = 10
queue = [None] * MAX_SIZE
front = 0
rear = -1
size = 0
def enqueue(element):
global rear, size
if size == MAX_SIZE:
print("Queue Overflow")
return
rear = (rear + 1) % MAX_SIZE # Circular increment
queue[rear] = element
size += 1
def dequeue():
global front, size
if size == 0:
print("Queue Underflow")
return None
element = queue[front]
front = (front + 1) % MAX_SIZE # Circular increment
size -= 1
return element
Using Linked Lists (Alternative Data Structure)
In a linked list implementation:
- Enqueue: Create a new node and link it at the end.
- Dequeue: Remove the node from the front and update the front pointer.
Using Object-Oriented Programming (OOP)
Example
Example in Python:
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
return "Queue Underflow"
return self.items.pop(0)
def peek(self):
if self.is_empty():
return None
return self.items[0]
def is_empty(self):
return len(self.items) == 0
Examples
Note
Using a Queue to Simulate a Print Queue:
def simulate_print_queue(documents):
queue = Queue()
for doc in documents:
queue.enqueue(doc)
while not queue.is_empty():
print(f"Printing: {queue.dequeue()}")
Note
Circular Queue Implementation:
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.front = 0
self.rear = -1
self.size = 0
self.capacity = capacity
def enqueue(self, item):
if self.size == self.capacity:
return "Queue Overflow"
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
self.size += 1
def dequeue(self):
if self.size == 0:
return "Queue Underflow"
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
Note Summary
Note
Common Mistakes
- Not Handling Underflow/Overflow:
- Forgetting to check if the queue is empty before dequeuing or peeking.
- In fixed-size implementations, failing to handle overflow when enqueuing.
- Index Mismanagement in Circular Queues:
- Incorrectly updating front or rear pointers in circular queues.
- Confusing LIFO with FIFO:
- Mistaking a queue for a stack. Remember that queues operate on a First-In, First-Out basis.
Note
Key Takeaways
- A queue is a FIFO data structure with key operations: enqueue, dequeue, and peek.
- Queues can be implemented using arrays, linked lists, or classes in OOP.
- Understand the principles of implementation rather than memorising specific code patterns.
- Practice implementing and tracing queues to strengthen your grasp of their behaviour in different contexts.