Data Structures – Queues

What Are Queues?

A queue is a linear data structure that follows the First In, First Out (FIFO) rule. The first element added is always the first one removed. Think of it as a digital waiting line — once you’re in, you must wait until all elements before you have been processed.

Queues are used whenever data or tasks must be handled in the same order they arrive. You’ll find them in CPU scheduling, printer job management, message buffering, and data communication systems. They maintain order, fairness, and predictability — three qualities every stable system needs.

The queue ensures that each element gets processed without skipping or rearranging order. This makes it ideal for managing shared system resources or timed task execution.

Learning Outcomes

• Define what a queue is and explain how FIFO behaviour works.
• Perform and trace basic queue operations step by step.
• Identify real-world applications where queues are essential.
• Implement a queue in Python using both arrays and linked lists.
• Differentiate between queue types: simple, circular, priority, and deque.

Core Concepts of Queues

Every queue operates on a defined set of core functions that preserve its FIFO order. These operations control how data moves — from the moment it enters the structure until it exits.

These basic operations define how a queue behaves and how elements flow through it. Together, they maintain a consistent order of execution that mirrors real-world task management systems.

Representations of a Queue

Queues can be implemented in multiple ways depending on how you want to manage memory and data flow. The two most common implementations are array-based and linked-list-based.

1. Array-Based Implementation

In this method, a fixed-size array or list is used to store queue elements. It uses two pointers or indices — front and rear — to track the positions where elements are added or removed.

• New elements are added at the rear of the queue.
• Removals occur from the front.
• When the array becomes full, no more elements can be added unless space is cleared.

# Array-based Queue Example in Python
class Queue:
    def __init__(self, size):
        self.queue = []
        self.size = size

    def enqueue(self, item):
        if len(self.queue) >= self.size:
            print("Queue Overflow")
        else:
            self.queue.append(item)

    def dequeue(self):
        if not self.queue:
            print("Queue Underflow")
            return None
        return self.queue.pop(0)

    def peek(self):
        return self.queue[0] if self.queue else None

# Example
q = Queue(3)
q.enqueue(10)
q.enqueue(20)
q.dequeue()
print(q.queue)

This code shows a simple queue where elements are added at the end and removed from the front. However, every time you call pop(0), Python shifts all elements left — which makes the operation O(n) in time complexity.

2. Linked-List Implementation

The linked-list approach uses nodes to represent elements. Each node stores data and a reference to the next node. This makes it flexible — there’s no fixed size, and memory is used only when needed.

• The front pointer marks the node to be dequeued next.
• The rear pointer marks where new nodes will be enqueued.
• Both operations take constant time, O(1).

# Linked-list-based Queue Example in Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear:
            self.rear.next = new_node
        self.rear = new_node
        if not self.front:
            self.front = new_node

    def dequeue(self):
        if not self.front:
            print("Queue Underflow")
            return None
        item = self.front.data
        self.front = self.front.next
        if not self.front:
            self.rear = None
        return item

With this structure, removing the front element doesn’t require shifting any data. Each enqueue and dequeue operation happens in constant time — making it suitable for programs that process large or continuous streams of input.

Activity: Trace the Queue

Follow the operations below and observe how the queue content changes after each step. Remember that the front element is always the first to be removed.

After completing all operations, the queue contains [10, 15, 20]. The front now points to 10 and the rear to 20.

Applications and Types of Queues

A. Applications of Queues

Queues are used wherever tasks must be handled in the order they arrive. They provide fairness and efficiency in real-world systems that process multiple requests simultaneously.

• Print Spoolers: Multiple documents sent to a printer are stored in a queue. The first document sent is printed first.
• Task Scheduling: Operating systems manage processes waiting for CPU time using queues.
• Network Buffers: Routers and switches store data packets in queues before transmission.
• Customer Service Systems: Chat or support tickets are served in the order they’re received.
• Simulation Systems: Used to model real-world waiting lines such as banks, call centres, or traffic lanes.
• Graph Traversal (BFS): Queues help explore nodes level by level in Breadth-First Search algorithms.

B. Types of Queues

Queues can be classified based on how elements are stored and accessed. Each type serves a unique purpose depending on the program’s memory constraints or scheduling needs.

1. Simple Queue

The simple queue is the most basic form of a queue. It follows the strict FIFO rule — elements are inserted at the rear and removed from the front. Once the rear reaches the end of the array, no more elements can be added unless the queue is reset.

# Simple Queue Example in Python
queue = [10, 20, 30]
queue.pop(0)  # removes the front element
print(queue)  # Output: [20, 30]

This method is straightforward but inefficient for large datasets. After every dequeue, all elements shift left — consuming extra processing time.

2. Circular Queue

A circular queue solves the wasted-space problem of simple queues. When the rear reaches the end of the array, it wraps around to use available space at the front. The array behaves like a loop — reusing freed-up slots efficiently.

# Circular Queue Concept
Queue Size: 5
Operations:
1. enqueue(10) → [10, –, –, –, –]
2. enqueue(20) → [10, 20, –, –, –]
3. enqueue(30) → [10, 20, 30, –, –]
4. dequeue()   → [–, 20, 30, –, –]
5. enqueue(40) → [–, 20, 30, 40, –]
6. enqueue(50) → [–, 20, 30, 40, 50]
7. enqueue(60) → [60, 20, 30, 40, 50]  # rear wraps to index 0

Circular queues are ideal for programs with limited memory, such as network buffering, streaming systems, and embedded devices.

3. Priority Queue

A priority queue assigns a priority value to each element. Instead of processing strictly by order, it serves higher-priority elements first. If two items share the same priority, the FIFO rule still applies.

# Priority Queue Example in Python
class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])  # lower number = higher priority

    def dequeue(self):
        if not self.queue:
            print("Queue Underflow")
            return None
        return self.queue.pop(0)

pq = PriorityQueue()
pq.enqueue("Backup files", 3)
pq.enqueue("Process payments", 1)
pq.enqueue("Update dashboard", 2)
print(pq.dequeue())  # ('Process payments', 1)

Priority queues are useful in systems that must balance urgency and fairness — like task schedulers, network traffic managers, and emergency response systems.

4. Deque (Double-Ended Queue)

A deque — short for Double-Ended Queue — allows insertion and removal of elements at both ends. It can act as both a queue and a stack depending on how you use it.

# Deque Example using collections.deque
from collections import deque

dq = deque()
dq.append(10)        # Add at rear
dq.appendleft(20)    # Add at front
dq.pop()             # Remove from rear
dq.popleft()         # Remove from front
print(dq)            # deque([])

Deques are highly efficient, supporting O(1) insertions and deletions from both ends. They are widely used in browser history navigation, undo/redo systems, and palindrome checking.

Python Implementation of Queues

Now that you’ve explored queue concepts and types, let’s see how to build them in Python. We’ll compare three implementations — array-based, linked-list, and collections.deque — and discuss which one performs best in real systems.

A. Array-Based Implementation

In an array-based queue, elements are added to the end of a list and removed from the front using pop(0). Although simple, this approach becomes inefficient for large queues because each removal shifts all remaining elements left.

# Array-based Queue Example
class Queue:
    def __init__(self, size):
        self.queue = []
        self.size = size

    def enqueue(self, item):
        if len(self.queue) >= self.size:
            print("Queue Overflow")
        else:
            self.queue.append(item)

    def dequeue(self):
        if not self.queue:
            print("Queue Underflow")
            return None
        return self.queue.pop(0)

queue = Queue(3)
queue.enqueue(10)
queue.enqueue(20)
queue.dequeue()
print(queue.queue)  # Output: [20]

Better Alternative: Using collections.deque

Python’s built-in collections.deque offers constant-time operations (O(1)) for both insertion and deletion from either end. It’s optimised for queue and stack behaviour and is widely used in production systems.

from collections import deque

queue = deque()
queue.append(10)
queue.append(20)
queue.append(30)
queue.popleft()  # Removes front element efficiently
print(queue)  # deque([20, 30])

B. Linked-List Implementation

The linked-list version offers the same performance as deque but gives you full control over how memory is managed. Each element dynamically links to the next, making it ideal for unpredictable data streams.

# Linked List Queue Example
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear:
            self.rear.next = new_node
        self.rear = new_node
        if not self.front:
            self.front = new_node

    def dequeue(self):
        if not self.front:
            print("Queue Underflow")
            return None
        item = self.front.data
        self.front = self.front.next
        if not self.front:
            self.rear = None
        return item

This method eliminates the need to shift elements, reducing time complexity for enqueue and dequeue operations to O(1). It’s particularly useful for systems like web servers or real-time task schedulers.

Activities and Summary

A. Activity – Try It Yourself

• Modify the Array-Based Queue: Change it to handle names instead of numbers. Example: enqueue("Anna"), enqueue("Ben"), dequeue(), enqueue("Carla") → ["Ben", "Carla"]
• Display Queue After Each Operation: Print the current queue content after every enqueue or dequeue to visualise changes.
• Implement a Priority Queue: Add a priority value for each element and process the highest priority first.
• Simulation Challenge: Create a task manager simulation where each task has a different priority and observe how the queue behaves.

B. Challenge Question

If the system removes elements faster than new ones are added, what will eventually happen to the queue? How can you handle this in real-world applications like load balancers or network buffers?

C. Summary

• A queue follows the FIFO principle — first in, first out.
• Key operations include enqueue (add), dequeue (remove), peek (view front), and isEmpty/isFull (status check).
• Common types: Simple, Circular, Priority, and Deque.
• Real-world uses: task scheduling, CPU management, buffering, and simulations.
• For performance, collections.deque is the preferred Python implementation.