DSA Queues

A queue is a First-In-First-Out (FIFO) collection where elements are added at the back and removed from the front, just like a line of people waiting.

What Is a Queue?

A queue only allows adding elements at one end, called the rear or back, and removing elements from the other end, called the front. Because the first element added is the first one removed, this ordering is called First-In-First-Out. Queues model waiting lines, print jobs, and any scenario where fairness — 'first come, first served' — matters.

Enqueue and Dequeue

Adding an element to a queue is called enqueue, and removing the front element is called dequeue. A correct queue implementation must perform both operations in O(1) time; if either operation degrades to O(n), the structure stops behaving like a true queue for large inputs, which is exactly the pitfall of using a plain array-backed list naively.

  • enqueue(value): add value to the rear of the queue — O(1) with the right data structure.
  • dequeue(): remove and return the value at the front — O(1) with the right data structure.
  • peek() / front(): look at the front value without removing it — O(1).
  • is_empty(): check whether the queue has any elements — O(1).
  • size(): report how many elements are currently queued — O(1).

Example

from collections import deque

queue = deque()
queue.append("first")   # enqueue
queue.append("second")  # enqueue
queue.append("third")   # enqueue

print(queue.popleft())  # dequeue -> first
print(queue[0])         # peek -> second
print(len(queue))       # size -> 2

Example

from collections import deque

class TaskQueue:
    def __init__(self):
        self._tasks = deque()

    def enqueue(self, task):
        self._tasks.append(task)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._tasks.popleft()

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


scheduler = TaskQueue()
scheduler.enqueue("print job A")
scheduler.enqueue("print job B")
scheduler.enqueue("print job C")

while not scheduler.is_empty():
    print("Processing:", scheduler.dequeue())
# Processing: print job A
# Processing: print job B
# Processing: print job C
Note: Using a plain Python list with list.pop(0) to dequeue looks correct but is O(n), because every remaining element must shift left one position. Always use collections.deque, which supports O(1) appends and pops from both ends.

Queues vs. Stacks

PropertyStackQueue
OrderLast-In-First-OutFirst-In-First-Out
Add operationpush (top)enqueue (rear)
Remove operationpop (top)dequeue (front)
Real-world analogyStack of platesLine at a checkout counter

Example

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}

def breadth_first_order(start):
    visited = {start}
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


print(breadth_first_order("A"))  # ['A', 'B', 'C', 'D']
Note: Python's collections.deque is implemented internally as a doubly linked list of blocks, which is exactly why it gives O(1) performance at both ends — the same reasoning you saw with linked lists applies directly here.

Exercise: DSA Queues

What ordering principle does a queue follow?

Keep Going

Data Structures Interview QuestionsPractice real questions asked for Data StructuresSoftware Engineer SalarySee what Software Engineer roles pay in the marketAuto Apply for JobsApply to open roles related to Data Structures and tweak your resume