Queue | Murad's Blog

FIFO (First In, First Out) data structure. The first element enqueued is the first dequeued. Think: task scheduling, BFS, message queues (Kafka, RabbitMQ).

Core Structure

text

Queue:
  data[]
  front = 0
  rear  = -1

enqueue(val):  data[++rear] = val
dequeue():     return data[front++]
peek():        return data[front]
isEmpty():     return front > rear

Core Operations

Operation	Description	Time	Space
enqueue(val)	Add to rear	O(1)	O(1)
dequeue()	Remove from front	O(1)	O(1)
peek()	View front without removing	O(1)	O(1)
isEmpty()	Check if empty	O(1)	O(1)

Types

Type	Description	Use Case
Simple Queue	FIFO, linear	Task scheduling
Circular Queue	Rear wraps to front	Buffer, fixed-size pool
Deque (Double-ended)	Insert/remove from both ends	Sliding window problems
Priority Queue	Dequeue by priority, not order	Dijkstra, heap-based

Circular Queue

Avoids wasted space in array-backed queues by wrapping indices.

text

enqueue(val):
  if isFull(): throw overflow
  rear = (rear + 1) % capacity
  data[rear] = val

dequeue():
  if isEmpty(): throw underflow
  val = data[front]
  front = (front + 1) % capacity
  return val

isFull():  return (rear + 1) % capacity == front
isEmpty(): return front == rear

	Time	Space
Complexity	O(1)	O(n)

Queue via Two Stacks

Implement queue using two stacks — common interview problem.

text

enqueue(val):  stack1.push(val)

dequeue():
  if stack2.isEmpty():
    while stack1 not empty:
      stack2.push(stack1.pop())
  return stack2.pop()

	Enqueue	Dequeue (amortized)
Time	O(1)	O(1) amortized

Elements are moved from stack1 to stack2 only when stack2 is empty — each element moves once total.

BFS with Queue

Queue is the backbone of Breadth-First Search — processes nodes level by level.

text

bfs(root):
  queue = [root]
  while queue not empty:
    node = queue.dequeue()
    visit(node)
    for each neighbor of node:
      if not visited: queue.enqueue(neighbor)

	Time	Space
Complexity	O(V + E)	O(V)

Priority Queue (Heap-backed)

Elements dequeued by priority, not insertion order. Backed by a min-heap or max-heap.

text

// Min-heap priority queue
enqueue(val, priority): heap.insert(val, priority)
dequeue():              return heap.extractMin()
peek():                 return heap.min()

Operation	Time
enqueue	O(log n)
dequeue	O(log n)
peek	O(1)

Java: PriorityQueue<> is a min-heap by default. Pass a custom comparator for max-heap or custom ordering.

Deque (Double-Ended Queue)

Supports insert and remove from both front and rear.

text

addFront(val)   removeFront()
addRear(val)    removeRear()

Use case: Sliding window maximum/minimum (monotonic deque)
Java: ArrayDeque — preferred over Stack and LinkedList for both stack and queue needs

Operation	Time
Add/remove front or rear	O(1)

Common Interview Patterns

Pattern	Problem Examples
BFS	Level-order traversal, shortest path
Sliding window	Max in window, moving average
Task scheduling	CPU scheduling, rate limiting
Queue via stacks	Implement queue with two stacks
Monotonic deque	Sliding window maximum

Stack vs Queue

	Stack	Queue
Order	LIFO	FIFO
Insert	push → top	enqueue → rear
Remove	pop ← top	dequeue ← front
Traversal	DFS	BFS
Java class	`Deque` / `ArrayDeque`	`Queue` / `ArrayDeque`