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.

infoNote

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)

lightbulbExample

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

infoNote

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()}")

infoNote

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

infoNote

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.

infoNote

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 memorizing specific code patterns.
Practice implementing and tracing queues to strengthen your grasp of their behaviour in different contexts.

Queues Simplified Revision Notes for A-Level OCR Computer Science

Queues

Overview

Structure of a Queue

Types of Queues

Implementing a Queue

Using Arrays (Procedural Approach)

Using Linked Lists (Alternative Data Structure)

Using Object-Oriented Programming (OOP)

Examples

Note Summary

Common Mistakes

Key Takeaways

500K+ Students Use These Powerful Tools to Master Queues For their A-Level Exams.

Other Revision Notes related to Queues you should explore