Queue

How Queue Works

A queue is an abstract data type that operates on the FIFO (First-In, First-Out) principle. The element that is inserted first is the one that gets removed first. Think of it like a line at a ticket counter: the first person in line is the first person served.

A queue supports two primary operations:

Enqueue — Adds an element to the rear (back) of the queue. This is an O(1) operation.
Dequeue — Removes and returns the element at the front of the queue. This is an O(1) operation.

Additional operations commonly provided:

Peek (or Front) — Returns the front element without removing it. O(1) time.
isEmpty — Checks whether the queue has no elements. O(1) time.
Size — Returns the number of elements currently in the queue. O(1) time.

Queues can be implemented using arrays, linked lists, or circular buffers. The array-based implementation is simple but may waste space unless a circular approach is used. The linked-list implementation allows the queue to grow dynamically without wasted capacity.

Common real-world applications of queues include:

Task scheduling — Operating systems use queues to manage processes waiting for CPU time.
Breadth-First Search (BFS) — Graph traversal algorithms rely on queues to explore nodes level by level.
Print spooling — Print jobs are queued and processed in order.
Message buffers — Asynchronous communication systems use queues to buffer messages between producers and consumers.
Rate limiting — Request queues help manage traffic to web services.

Interactive Visualization

Experiment with the queue below. Enter a value and click an operation button to see how it works step by step. Use the playback controls to step through or auto-play the animation.

Queue: [15, 42, 8, 23, 7]. Use the operation buttons below.

from collections import deque
queue = deque()
# Enqueue
queue.append(val)
# Dequeue
val = queue.popleft()

Speed No steps

Code Implementation

Below is a complete queue implementation with enqueue, dequeue, peek, and isEmpty operations in three languages.

from collections import deque


class Queue:
    def __init__(self):
        """Initialize an empty queue using a deque for O(1) operations."""
        self._data = deque()

    def enqueue(self, value):
        """Add an element to the rear of the queue. O(1)"""
        self._data.append(value)

    def dequeue(self):
        """Remove and return the front element. O(1)
        Raises IndexError if the queue is empty.
        """
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        return self._data.popleft()

    def peek(self):
        """Return the front element without removing it. O(1)
        Raises IndexError if the queue is empty.
        """
        if self.is_empty():
            raise IndexError("Peek from an empty queue")
        return self._data[0]

    def is_empty(self):
        """Check whether the queue is empty. O(1)"""
        return len(self._data) == 0

    def size(self):
        """Return the number of elements in the queue. O(1)"""
        return len(self._data)

    def __str__(self):
        """Return a string representation (front on the left)."""
        return "Queue([" + ", ".join(str(x) for x in self._data) + "])"


# Example usage
q = Queue()
for val in [15, 42, 8, 23, 7]:
    q.enqueue(val)

print(q)            # Queue([15, 42, 8, 23, 7])
print(q.peek())     # 15
print(q.dequeue())  # 15
print(q.dequeue())  # 42
print(q)            # Queue([8, 23, 7])
print(q.is_empty()) # False
print(q.size())     # 3

Complexity Analysis

The table below summarizes the time and space complexities for common queue operations.

Operation	Time Complexity	Notes
Enqueue	O(1)	Element is added at the rear; no shifting needed
Dequeue	O(1)	Element is removed from the front (amortized O(1) for array-based)
Peek	O(1)	Direct access to the front element
isEmpty	O(1)	Simple check on the size or pointer comparison
Search	O(n)	Must scan from front to rear; not a standard queue operation
Space	O(n)	Proportional to the number of elements stored

Real-World Applications

🖨️

Print Spooler Jobs are queued and processed in order

🌐

Web Server Requests HTTP requests wait in a queue before being handled

🤖

BFS Graph Search BFS uses a queue to explore nodes level-by-level

📦

Message Queues Kafka, RabbitMQ, and SQS are industrial-grade queues

Practice

Given a string, return the first non-repeating character. If every character repeats, return an empty string "".

Given an array and window size k, return a list containing the maximum value of each sliding window of size k.

Quiz

Q1. What principle does a queue follow?

LIFO (Last-In, First-Out)

FIFO (First-In, First-Out)

FILO (First-In, Last-Out)

Random access

A queue follows the FIFO principle: the first element added (enqueued) is the first one removed (dequeued), just like a real-world line of people.

Q2. What is the time complexity of the enqueue operation?

O(1)

O(n)

O(log n)

O(n log n)

Enqueue adds an element at the rear of the queue. With a linked-list or circular buffer implementation, this is done in constant time O(1) since we maintain a rear pointer.

Q3. If you enqueue 10, 20, 30 (in that order) and then dequeue once, which element is returned?

30

20

10

None of the above

Since a queue is FIFO, the first element enqueued (10) is the first one dequeued. After dequeue, the queue contains [20, 30].

Q4. Which algorithm relies on a queue for its traversal order?

Depth-First Search (DFS)

Binary Search

Quick Sort

Breadth-First Search (BFS)

BFS uses a queue to explore all neighbors at the current depth level before moving to nodes at the next depth level. DFS, in contrast, uses a stack (or recursion).

Q5. What does the peek operation do on a queue?

Removes and returns the front element

Returns the front element without removing it

Returns the rear element without removing it

Checks if the queue is empty

Peek returns the element at the front of the queue without modifying the queue. It allows you to inspect the next element that would be dequeued, which is useful for conditional logic before committing to a dequeue.