Queues (OCR A-Level Computer Science): Revision Notes
📚 Revision Notes
Queues
Overview
A queue is a dynamic data structure that follows the First In, First Out (FIFO) principle. This means the first item added to the queue is the first one to be removed. Queues are widely used in various real-world and computational scenarios, such as managing tasks in printers, handling customer service requests, and simulating real-world queues.
Characteristics of a Queue
- Dynamic Data Structure: The size of a queue can grow or shrink dynamically as items are added or removed.
- FIFO Principle: The first item added is the first item to be removed.
Key Operations
- Enqueue: Adds an item to the rear of the queue.
- Dequeue: Removes an item from the front of the queue.
- Peek/Front: Returns the item at the front without removing it.
- IsEmpty: Checks if the queue is empty.
- IsFull (optional in static implementations): Checks if the queue has reached its maximum capacity.
Use Cases for Queues
- Print Queue: Manages print jobs in the order they are received.
- Task Scheduling: Processes tasks in a first-come, first-served manner.
- Breadth-First Search (BFS): Explores nodes level by level in graph or tree traversal.
- Real-Time Systems: Handles incoming requests or events in the order they occur.
Implementation of Queues
Dynamic Implementation Using a Linked List
A queue can be implemented using a linked list, where each node contains the data and a reference to the next node.
lightbulbExample
Example Pseudocode for Dynamic Queue:
CLASS Node
DATA value
POINTER next
CLASS Queue
POINTER front
POINTER rear
METHOD Enqueue(value)
NEW_NODE ← Node(value)
IF front IS NULL
front ← NEW_NODE
rear ← NEW_NODE
ELSE
rear.next ← NEW_NODE
rear ← NEW_NODE
METHOD Dequeue()
IF front IS NULL
RETURN "Queue Underflow"
ELSE
value ← front.value
front ← front.next
IF front IS NULL
rear ← NULL
RETURN value
METHOD Peek()
IF front IS NULL
RETURN "Queue is Empty"
ELSE
RETURN front.value
METHOD IsEmpty()
RETURN front IS NULL
Static Implementation Using an Array
A queue can also be implemented using a static array with a fixed size.
lightbulbExample
Example Pseudocode for Static Queue:
CLASS Queue
ARRAY data[size]
INTEGER front ← 0
INTEGER rear ← -1
INTEGER count ← 0
METHOD Enqueue(value)
IF count = size
RETURN "Queue Overflow"
ELSE
rear ← (rear + 1) MOD size
data[rear] ← value
count ← count + 1
METHOD Dequeue()
IF count = 0
RETURN "Queue Underflow"
ELSE
value ← data[front]
front ← (front + 1) MOD size
count ← count - 1
RETURN value
METHOD Peek()
IF count = 0
RETURN "Queue is Empty"
ELSE
RETURN data[front]
METHOD IsEmpty()
RETURN count = 0
METHOD IsFull()
RETURN count = size
Types of Queues
- Simple Queue: Operates strictly in FIFO order.
- Circular Queue: The rear wraps around to the front when the end of the array is reached.
- Priority Queue: Elements are dequeued based on their priority rather than their arrival time.
infoNote
Example Scenario
Task Scheduling in a CPU:
- Enqueue: Incoming tasks are added to the queue.
- Dequeue: The CPU processes tasks in the order they were added.
Note Summary
infoNote
Common Mistakes
- Queue Overflow/Underflow:
- Overflow occurs when enqueuing into a full queue (static implementation).
- Underflow occurs when dequeuing from an empty queue.
- Mismanaging Indices in Static Queues:
- Failing to properly update
frontandrearindices, especially in circular queues.
- Confusing FIFO with LIFO:
- Queues follow FIFO (First In, First Out), unlike stacks which use LIFO.
- Not Handling Edge Cases:
- Forgetting to reset the
frontandrearpointers when the queue becomes empty after dequeuing all elements.
infoNote
Key Takeaways
- Queues follow the FIFO principle and are useful in scenarios like task scheduling, BFS, and real-time event handling.
- Key operations include Enqueue, Dequeue, Peek, and IsEmpty.
- Queues can be implemented dynamically using linked lists or statically using arrays.
- Understand specific queue types (e.g., simple, circular, priority) and their use cases.