Queue Basics

What Is a Queue?

A queue is a linear data structure that follows one strict rule: the first element added is the first element removed. This rule is called FIFO — First In, First Out.

Think of a queue as a line of people waiting at a ticket counter. The person who arrives first is served first. New arrivals join at the back. Nobody cuts in line. The person who has been waiting the longest is always next.

Queue of integers — add at BACK, remove from FRONT:

ENQUEUE 10:       ENQUEUE 20:       ENQUEUE 30:       DEQUEUE:
┌────┐             ┌────┬────┐       ┌────┬────┬────┐  ┌────┬────┐
│ 10 │             │ 10 │ 20 │       │ 10 │ 20 │ 30 │  │ 20 │ 30 │
└────┘             └────┴────┘       └────┴────┴────┘  └────┴────┘
FRONT=BACK          FRONT     BACK    FRONT          BACK  FRONT   BACK

Enqueue adds to the BACK.    Dequeue removes from the FRONT.
10 arrived first, 10 leaves first.

Unlike a stack — where the last element added is the first removed — a queue preserves arrival order. Elements are processed in exactly the order they arrived.

The Three Core Operations

Every queue supports exactly three fundamental operations:

ENQUEUE(value)   — also called offer, add, push
  Add a value to the back of the queue.
  Time: O(1)

DEQUEUE()        — also called poll, remove, pop
  Remove and return the front value.
  Throws an error (or returns null) if the queue is empty.
  Time: O(1)

PEEK() / FRONT()
  Read the front value without removing it.
  Throws an error (or returns null) if the queue is empty.
  Time: O(1)

Supporting operations:
  isEmpty()  → true if the queue has no elements
  size()     → number of elements currently in the queue

All three core operations are O(1) — they only touch the front or back, never traverse the queue. This is the defining performance property of a queue.

Output:
Queue after 3 enqueues: [10, 20, 30]
Size: 3
Peek: 10
Dequeue: 10
Dequeue: 20
Queue after 2 dequeues: [30]
isEmpty: false
isEmpty after last dequeue: true

FIFO in Action — Dry Run

The FIFO property is clearest when enqueues and dequeues interleave:

Operations: ENQUEUE(A), ENQUEUE(B), ENQUEUE(C), DEQUEUE, ENQUEUE(D), DEQUEUE, DEQUEUE, DEQUEUE

State after each operation:
  ENQUEUE(A): front → [A] ← back
  ENQUEUE(B): front → [A, B] ← back
  ENQUEUE(C): front → [A, B, C] ← back
  DEQUEUE    → returns A,  front → [B, C] ← back
  ENQUEUE(D): front → [B, C, D] ← back
  DEQUEUE    → returns B,  front → [C, D] ← back
  DEQUEUE    → returns C,  front → [D] ← back
  DEQUEUE    → returns D,  front → [] ← back  (empty)

Order of returned values: A, B, C, D
Exactly the order they arrived — FIFO preserved throughout.

Notice that D was enqueued after A, B, and C were already enqueued — yet D still exits after C. The queue remembers insertion order and preserves it through any pattern of interleaved enqueues and dequeues.

Key Vocabulary

Front / Head
  The position from which elements are removed.
  The element that has been waiting the longest.
  All dequeue and peek operations act on the front.

Back / Rear / Tail
  The position to which new elements are added.
  All enqueue operations act on the back.

Enqueue / Offer / Add
  Insert a new element at the back.

Dequeue / Poll / Remove
  Remove and return the element at the front.

Peek / Front
  Read the front element without removing it.

Overflow
  Attempting to enqueue into a full queue (fixed-size queues only).

Underflow
  Attempting to dequeue or peek from an empty queue.
  Throws an exception or returns null depending on the language/method.

Why Queues Exist — The Problem They Solve

Queues model situations where fairness and arrival order matter. Any system where things must be processed in the order they arrived uses a queue.

Problem: Process requests in the exact order they were received.

Example 1: Print queue
  Documents sent: Report.pdf, Photo.jpg, Letter.docx
  Printed in that exact order — first sent, first printed.
  A stack would print Letter.docx first — wrong for a printer.

Example 2: Customer service call center
  Callers: Alice at 9:00, Bob at 9:01, Carol at 9:02
  Served:  Alice first, then Bob, then Carol
  FIFO ensures fairness — no caller is skipped.

Example 3: Breadth-First Search (BFS)
  Explore all nodes at distance 1 before distance 2 before distance 3.
  Each node's neighbours are added to the queue when the node is visited.
  FIFO guarantees level-by-level exploration order.

Example 4: Operating system process scheduling
  Processes wait in a ready queue — CPU serves them in order.
  Round-robin scheduling cycles through the queue repeatedly.

Example 5: Asynchronous task processing
  Web server receives requests: R1, R2, R3
  Worker processes R1 first (it arrived first), then R2, then R3.
  Queue decouples the producer (request arrival) from the consumer (worker).

Every time you see "process in arrival order" or "fair scheduling" or "level-by-level," a queue is the natural tool.

Queue vs Stack — One Rule, Opposite Effect

Stack and queue are the two foundational linear data structures. They are structurally identical except for one difference: where removal happens.

STACK (LIFO — Last In, First Out):
  Add at top, remove from top.
  New arrivals push previous elements down.
  The newest element is always served first.

  Input:  1 → 2 → 3
  Output: 3 → 2 → 1   (reversed)

QUEUE (FIFO — First In, First Out):
  Add at back, remove from front.
  New arrivals wait behind everyone already there.
  The oldest element is always served first.

  Input:  1 → 2 → 3
  Output: 1 → 2 → 3   (preserved)

Same 4 operations, different outcomes:

  Operations: ADD(1), ADD(2), ADD(3), REMOVE, REMOVE

  Stack result:  3, 2   (newest first)
  Queue result:  1, 2   (oldest first)

Which to use:
  Need reverse order of arrival?  → Stack
  Need original order of arrival? → Queue
  BFS (level-by-level)?           → Queue
  DFS (depth-first)?              → Stack

How Queues Are Implemented

A queue is an abstraction. The underlying storage can be a linked list, a dynamic array, or a circular array.

Linked-list-backed queue:
  front → [10] → [20] → [30] ← back

  Enqueue: create new node, point old tail's next to it, update tail → O(1)
  Dequeue: read head.data, move head to head.next              → O(1)
  Peek:    read head.data                                       → O(1)
  Pros:    no capacity limit, true O(1) for both ends
  Cons:    pointer overhead per node, scattered memory

Circular array-backed queue:
  arr = [_, 10, 20, 30, _]
         0   1   2   3  4
              ↑           ↑
            front        back

  Enqueue: arr[back % capacity] = value; back++  → O(1)
  Dequeue: value = arr[front % capacity]; front++ → O(1)
  Peek:    arr[front % capacity]                  → O(1)
  Pros:    cache-friendly, no allocation per element
  Cons:    fixed capacity; resize copies all elements

Simple array (non-circular):
  Dequeue shifts all remaining elements left → O(n)
  Never use for queues — defeats the purpose of O(1) dequeue.

In interviews, you use the built-in (Java ArrayDeque, Python deque, C++ std::queue, JS array as approximation). Understanding the implementations matters for explaining trade-offs.

Queue Variants

The basic FIFO queue has three important extensions, each covered in dedicated topics:

Circular Queue:
  Fixed-size array where front and back wrap around using modulo.
  When back reaches the end, it circles back to index 0.
  Efficient use of pre-allocated memory — no wasted slots.

Double-Ended Queue (Deque):
  Insert and remove at BOTH front and back.
  Generalises both queue and stack — FIFO and LIFO in one structure.
  Python's collections.deque and Java's ArrayDeque implement this.

Priority Queue:
  Elements are removed in order of priority, not arrival.
  Highest-priority element is always at the front.
  Implemented with a heap — O(log n) enqueue and dequeue.
  Used in Dijkstra's algorithm, task scheduling, median maintenance.

Where Queues Appear in Real Systems

BFS Graph/Tree Traversal
  The canonical algorithmic use. Enqueue the starting node.
  Dequeue a node, enqueue all its unvisited neighbours.
  FIFO guarantees level-by-level exploration.
  Used for: shortest path in unweighted graphs, web crawlers,
  social network degree of separation.

CPU Process Scheduling
  The ready queue holds processes waiting for CPU time.
  Round-robin scheduling dequeues the next process, gives it
  a time slice, then re-enqueues if not finished.

Network Packet Routing
  Routers maintain queues of packets waiting to be forwarded.
  FIFO ordering ensures packets from one stream arrive in order.

Asynchronous Message Passing
  Producer sends tasks to a queue. Consumer reads and processes.
  Decouples the producer rate from the consumer rate.
  Examples: Kafka, RabbitMQ, AWS SQS — all queue-based systems.

Breadth-First Level Order Tree Traversal
  Print nodes level by level — enqueue root, process level by level.
  Each node's children are enqueued when the node is dequeued.

Keyboard/Mouse Input Buffers
  Operating systems queue keystrokes and mouse events.
  Events are processed in the order they occurred.

Printer Spooler
  Print jobs enqueued in arrival order. Processed FIFO.
  A classic textbook example of queue usage.

Queue in Each Language

Java recommendation:
  Use ArrayDeque as a Queue:
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(10);    // enqueue
    q.poll();       // dequeue — null if empty
    q.peek();       // peek — null if empty

  Not LinkedList — ArrayDeque is faster (array vs pointer-per-node).
  Not the legacy java.util.Queue directly — it's an interface, need an impl.

JavaScript note:
  Array.shift() is O(n) — it shifts every element left by one.
  For O(1) dequeue in JS, implement with a Map-based queue or use
  two arrays (or find a library). For interview problems with small n,
  Array + shift() is acceptable if you state the complexity.

When to Use a Queue

Use a queue when:
  ✓ Processing must happen in arrival order (fairness)
  ✓ BFS or level-order traversal
  ✓ Shortest path in unweighted graphs
  ✓ Rate-limited task buffering (producer-consumer)
  ✓ Simulating any real-world waiting line
  ✓ Sliding window problems with expiry (deque variant)

Do NOT use a queue when:
  ✗ You need to process the most recently added item first → Stack
  ✗ You need to process by priority, not arrival → Priority Queue
  ✗ You need random access by index → Array
  ✗ You need to search by key → Hash Map

Interview recognition signals:
  "shortest path"           → BFS → Queue
  "level order traversal"   → BFS → Queue
  "process in order"        → Queue
  "sliding window maximum"  → Deque (monotonic queue)
  "k closest points"        → Priority Queue
  "all nodes at distance n" → BFS → Queue
  "round-robin"             → Circular Queue

Interview Questions

Q: What is FIFO and how does it define queue behaviour?

FIFO stands for First In, First Out. The element added earliest — the first one enqueued — is the first one removed — the first one dequeued. Every enqueue places the new element at the back behind all existing elements. Every dequeue removes only the front element, which has been waiting the longest. No element can be removed before all elements added before it have been removed.

Q: What is the time complexity of enqueue and dequeue?

Both are O(1) — constant time regardless of how many elements are in the queue. Enqueue attaches a new element at the back (one pointer update for linked list, one array write and index increment for circular array). Dequeue reads and removes the front (one pointer update or index increment). Neither operation traverses the queue. This O(1) guarantee holds for linked-list-backed and circular-array-backed queues.

Q: Why is a simple (non-circular) array a poor choice for a queue?

With a simple array, enqueue appends at index back — O(1). But dequeue removes from index 0 — every remaining element must shift left by one position to fill the gap, costing O(n). After n dequeue operations the entire array has been shifted n times — O(n²) total. A circular array avoids this by treating the array as a ring — both front and back are index pointers that wrap around with modulo, making both enqueue and dequeue O(1) with no shifting.

Q: When would you use a queue instead of a stack for graph traversal?

Use a queue (BFS) when you need the shortest path in an unweighted graph, or when you need to explore all nodes at one distance before nodes at the next distance. Use a stack (DFS) when you need to explore as deeply as possible before backtracking — for cycle detection, topological sort, or path existence. The same traversal code with queue.poll()/offer() replaced by stack.pop()/push() switches between BFS and DFS.

FAQs

Is Python's list a suitable queue?

No — not for production or performance-sensitive code. list.pop(0) (dequeue from front) is O(n) because all elements shift left. list.append() (enqueue at back) is O(1). Using list.pop(0) in a BFS loop of n nodes gives O(n²) total — the BFS appears to work but is too slow for large inputs. Always use collections.deque for queues in Python — popleft() is O(1).

What is the difference between Queue.offer() and Queue.add() in Java?

Both enqueue an element. add() throws IllegalStateException if the queue is at capacity (for bounded queues). offer() returns false instead of throwing. For unbounded queues like ArrayDeque, both always succeed and behave identically. Similarly, poll() returns null on empty while remove() throws NoSuchElementException. The offer/poll/peek trio is safer and preferred.

Can a queue contain duplicate elements?

Yes. A queue has no uniqueness constraint — the same value can be enqueued multiple times. Each duplicate is an independent entry that will be dequeued separately in the order it was enqueued. If uniqueness is required, maintain a separate HashSet of seen elements alongside the queue (as done in BFS traversal to avoid revisiting nodes).

What is the difference between a queue and a deque?

A queue is single-ended — enqueue at back, dequeue from front only. A deque (double-ended queue) allows insert and remove at both ends. Every queue is a deque with half its operations restricted. Java's ArrayDeque and Python's collections.deque are both full deques — you can use them as queues by only using one-end-add and one-end-remove operations. A priority queue is different again — removal order is by priority, not position.

Quick Quiz

Question 1: You enqueue 1, 2, 3, 4. Then dequeue twice. What is at the front?

• ›A) 1
• ›B) 2
• ›C) 3
• ›D) 4

Answer: C) 3. After enqueueing 1, 2, 3, 4, the queue is [1, 2, 3, 4] with 1 at the front. First dequeue returns 1. Second dequeue returns 2. Now 3 is at the front.

Question 2: Which problem is most naturally solved with a queue?

• ›A) Checking if brackets are balanced
• ›B) Finding the shortest path in an unweighted graph
• ›C) Evaluating a postfix expression
• ›D) Implementing undo functionality

Answer: B) Shortest path in an unweighted graph. BFS uses a queue to explore nodes level by level — all nodes at distance k are processed before any node at distance k+1. This level-by-level guarantee is what makes BFS find the shortest path. The other three problems use stacks.

Question 3: What is the time complexity of list.pop(0) in Python and why should you avoid it for queues?

• ›A) O(1) — same as list.pop()
• ›B) O(log n) — binary search to find index 0
• ›C) O(n) — all elements shift left after removal from index 0
• ›D) O(1) amortized — same as dynamic array operations

Answer: C) O(n). Python's list is a dynamic array. Removing from index 0 requires every subsequent element to shift one position left — O(n) work for n elements. In a BFS loop processing n nodes, this gives O(n²) total. Use collections.deque.popleft() instead — O(1).

Question 4: What distinguishes FIFO (queue) from LIFO (stack)?

• ›A) Queue holds more elements than a stack
• ›B) Stack is faster for all operations than queue
• ›C) Queue processes elements in arrival order; stack processes in reverse arrival order
• ›D) Queue supports random access; stack does not

Answer: C) FIFO vs reverse order. Both structures support O(1) operations. Neither supports random access. The single difference is the removal rule: queue removes the oldest element (first in, first out), stack removes the newest element (last in, first out). Same input, different output order.

Summary

A queue is a First In, First Out data structure. Elements are added at the back and removed from the front. The element that has been waiting the longest is always the next to be removed.

The key ideas to carry forward:

• ›FIFO — arrival order is preserved; oldest element is always served first
• ›Three operations — enqueue O(1), dequeue O(1), peek O(1) — always constant time
• ›Front = oldest element (next to leave); Back = newest element (last to leave)
• ›Linked-list-backed — true O(1) both ends, pointer overhead per node
• ›Circular-array-backed — cache-friendly, fixed capacity, modulo arithmetic for wrap-around
• ›Never use a plain array — pop(0) / shift() is O(n), not O(1)
• ›Java — use Queue<E> with ArrayDeque<E> via offer/poll/peek
• ›Python — use collections.deque with append/popleft/[0]
• ›Queue vs Stack — same structure, one rule: FIFO for order preservation, LIFO for reversal
• ›Recognition signals — "shortest path," "level order," "BFS," "arrival order," "round-robin"

In the next topic, you will explore Queue Operations — the complete API for every queue operation across all four languages, edge case handling, and when each method variant is appropriate.