DSA Queues

A queue is a linear data structure that follows the FIFO — First In, First Out principle. The first element added to the queue is the first one to be removed. This is the opposite behavior of a stack.

A real-world analogy is a line at a movie ticket counter. The person who arrives first gets served first. New arrivals join the back of the line, and people leave from the front.

Core Queue Operations

  • Enqueue — Add an element to the rear (back) of the queue.
  • Dequeue — Remove an element from the front of the queue.
  • Front/Peek — View the element at the front without removing it.
  • isEmpty — Check whether the queue is empty.

Implementing a Queue in Python

Method 1: Using a Python List (Not Recommended for Large Data)

A list can simulate a queue, but removing from the front using pop(0) is O(n) because all other elements shift. For small queues this is fine; for large data, use collections.deque.


queue = []

# Enqueue
queue.append("Alice")
queue.append("Bob")
queue.append("Carol")
print("Queue:", queue)
# Output: Queue: ['Alice', 'Bob', 'Carol']

# Dequeue (from front)
served = queue.pop(0)
print("Served:", served)
print("Queue after dequeue:", queue)
# Output: Served: Alice
# Output: Queue after dequeue: ['Bob', 'Carol']

Method 2: Using collections.deque (Recommended)

deque (double-ended queue) is optimized for fast additions and removals from both ends. Both append() and popleft() run in O(1).


from collections import deque

queue = deque()

# Enqueue
queue.append("Task 1")
queue.append("Task 2")
queue.append("Task 3")
print("Queue:", queue)
# Output: Queue: deque(['Task 1', 'Task 2', 'Task 3'])

# Dequeue
completed = queue.popleft()
print("Completed:", completed)
# Output: Completed: Task 1

Method 3: Custom Queue Class


from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return "Queue is empty"
        return self.items.popleft()

    def front(self):
        if self.is_empty():
            return "Queue is empty"
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Usage
q = Queue()
q.enqueue("Order 1")
q.enqueue("Order 2")
q.enqueue("Order 3")

print("Front:", q.front())        # Output: Front: Order 1
print("Dequeue:", q.dequeue())    # Output: Dequeue: Order 1
print("Size:", q.size())          # Output: Size: 2

Types of Queues

1. Simple Queue (Linear Queue)

The basic form of a queue where elements are added at the rear and removed from the front. Once the front pointer moves past a position, that space is not reused.

2. Circular Queue

The rear of the queue wraps around to the front when the end of the storage space is reached. This makes efficient use of memory by reusing empty spaces left by dequeued elements.


# Simple circular queue concept using modulo
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def enqueue(self, item):
        if self.size == self.capacity:
            return "Queue is full"
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            return "Queue is empty"
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

cq = CircularQueue(3)
cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")
print(cq.dequeue())   # Output: A
cq.enqueue("D")       # Reuses the slot freed by A
print(cq.dequeue())   # Output: B

3. Priority Queue

Elements are removed based on priority rather than arrival order. The element with the highest priority is dequeued first. Python's heapq module supports this efficiently.


import heapq

priority_queue = []

# Push with priority (lower number = higher priority)
heapq.heappush(priority_queue, (2, "Medium priority task"))
heapq.heappush(priority_queue, (1, "High priority task"))
heapq.heappush(priority_queue, (3, "Low priority task"))

# Pop always returns the item with the lowest priority number
print(heapq.heappop(priority_queue))   # Output: (1, 'High priority task')
print(heapq.heappop(priority_queue))   # Output: (2, 'Medium priority task')

4. Deque (Double-Ended Queue)

Elements can be added or removed from both ends. Python's collections.deque implements this natively.


from collections import deque

dq = deque()
dq.append("middle")        # Add to right
dq.appendleft("start")    # Add to left
dq.append("end")          # Add to right

print(dq)                  # deque(['start', 'middle', 'end'])

dq.popleft()               # Remove from left
dq.pop()                   # Remove from right
print(dq)                  # deque(['middle'])

Real-World Applications of Queues

1. Print Spooler

Documents sent to a printer are queued. The first document sent is the first to be printed.

2. CPU Scheduling

Operating systems use queues to manage which process gets CPU time next.

3. Breadth-First Search (BFS)

BFS uses a queue to explore nodes level by level in graphs and trees. This topic is covered in detail in the Graph section of this course.

4. Customer Service Systems

Support ticket systems queue incoming requests, ensuring they are handled in the order received.

Big O Summary for Queue Operations

  • Enqueue — O(1)
  • Dequeue — O(1) with deque; O(n) with list
  • Peek (front) — O(1)
  • Search — O(n)
  • Space — O(n)

Key Points

  • A queue follows FIFO — the first element in is the first element out.
  • Core operations are enqueue (add to rear) and dequeue (remove from front).
  • Use collections.deque for efficient O(1) enqueue and dequeue operations.
  • Types include simple queue, circular queue, priority queue, and deque.
  • Queues are essential for BFS graph traversal, task scheduling, and real-time processing systems.
  • Priority queues extend the concept by serving elements based on importance, not just arrival order.
Previous lessons
Back to courses
Next lessons

Leave a Comment