Queue

A Queue is a FIFO (First In, First Out) data structure. The first element added is the first one removed. Like a line at a checkout counter.

Basic Operations

• Enqueue: Add an element to the back of the queue.
• Dequeue: Remove an element from the front of the queue.
• Front: Look at the front element.
• isEmpty: Check whether the queue is empty.

Implementation with a Python List

queue = []

# Enqueue
queue.append(10)
queue.append(20)
queue.append(30)

# Dequeue (inefficient: O(n))
first = queue.pop(0)
print(first)  # 10

Note: pop(0) on a Python list is O(n) because every element must be shifted.

Implementation with collections.deque

from collections import deque

queue = deque()

# Enqueue
queue.append(10)
queue.append(20)
queue.append(30)

# Dequeue (efficient: O(1))
first = queue.popleft()
print(first)  # 10

# Front
print(queue[0])  # 20

Class Implementation

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

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

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

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

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

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

Time Complexity

Queue Applications

1. BFS: Graph traversal level by level.
2. Print Queue: Document printing queue.
3. Task Scheduling: Process queue in an OS.
4. Buffer: Streaming data.
5. Message Queue: Communication between services.

q = Queue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(q.dequeue())  # A
print(q.front())    # B

A Queue restricts access to two opposite ends. If you need access from both ends, use a Deque.