DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Queue Implementation

What This Page Covers

The previous page covered operations using language built-ins. This page builds complete, production-quality queue classes from the ground up — three backend implementations and one advanced design pattern.

Implementation 1: Fixed-Size Circular Array Queue
  Underlying structure: fixed-capacity array with front/rear index pointers
  Teaches:  modulo arithmetic wrap-around, isFull vs isEmpty distinction
  Use when: capacity is known, maximum throughput required

Implementation 2: Dynamic Array Queue
  Underlying structure: resizable circular array
  Teaches:  automatic doubling, element copy during resize
  Use when: general-purpose, unknown capacity

Implementation 3: Linked List Queue
  Underlying structure: singly linked list with head and tail pointers
  Teaches:  true O(1) both ends, the tail-null bug, empty queue edge cases
  Use when: guaranteed O(1) per operation, no capacity limit

Advanced Pattern: Two-Stack Queue
  Implements a queue using two stacks — no linked list, no array tricks
  Teaches:  amortized O(1) dequeue via lazy transfer
  Use when: interview problem asks "implement queue using stacks"

Implementation 1: Fixed-Size Circular Array Queue

The key insight: instead of shifting elements when dequeuing, use two index pointers — front and rear. When an index reaches the end of the array, wrap it back to 0 using modulo. The array behaves as a ring — no element ever moves.

Circular array state, capacity=5:

Initial:  front=0, rear=0, size=0
  [_, _, _, _, _]
   0  1  2  3  4

Enqueue 10,20,30:
  [10, 20, 30, _, _]
   0   1   2  3  4
   ↑front         rear=3

Dequeue:
  front = (0+1)%5 = 1
  [10, 20, 30, _, _]   returns 10
        ↑front    rear=3

Enqueue 40,50,60 (wrap-around):
  rear = 3 → enqueue 40 at [3], rear=4
  rear = 4 → enqueue 50 at [4], rear=0  (wraps!)
  rear = 0 → enqueue 60 at [0], rear=1
  [60, 20, 30, 40, 50]
        ↑front=1   rear=1, size=5 (full)

isFull:  size == capacity
isEmpty: size == 0
(Do NOT use front == rear — it's true for both full and empty!)

Java

public class CircularArrayQueue<T> {

    private Object[] data;     // Underlying fixed array
    private int      front;    // Index of the front element
    private int      rear;     // Index where next element will be inserted
    private int      size;     // Current number of elements
    private final int capacity;

    @SuppressWarnings("unchecked")
    public CircularArrayQueue(int capacity) {
        this.capacity = capacity;
        this.data     = new Object[capacity];
        this.front    = 0;
        this.rear     = 0;
        this.size     = 0;
    }

    // ENQUEUE — O(1)
    public void enqueue(T value) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full (capacity: " + capacity + ")");
        }
        data[rear] = value;
        rear       = (rear + 1) % capacity;   // Wrap rear with modulo
        size++;
    }

    // DEQUEUE — O(1)
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        T value    = (T) data[front];
        data[front] = null;                    // Help GC — clear the slot
        front      = (front + 1) % capacity;  // Wrap front with modulo
        size--;
        return value;
    }

    // PEEK — O(1)
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        return (T) data[front];
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull()  { return size == capacity; }
    public int     size()    { return size; }
    public int     capacity(){ return capacity; }

    @Override
    public String toString() {
        if (isEmpty()) return "Queue: [] (empty)";
        StringBuilder sb = new StringBuilder("Queue (front→back): [");
        for (int i = 0; i < size; i++) {
            sb.append(data[(front + i) % capacity]);
            if (i < size - 1) sb.append(", ");
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        CircularArrayQueue<Integer> q = new CircularArrayQueue<>(5);

        q.enqueue(10); q.enqueue(20); q.enqueue(30);
        System.out.println(q);                            // [10, 20, 30]
        System.out.println("Peek:     " + q.peek());     // 10
        System.out.println("Size:     " + q.size());     // 3
        System.out.println("Dequeue:  " + q.dequeue());  // 10
        System.out.println("Dequeue:  " + q.dequeue());  // 20

        // Now front has wrapped — add more to test wrap-around
        q.enqueue(40); q.enqueue(50); q.enqueue(60);
        System.out.println(q);                            // [30, 40, 50, 60]
        System.out.println("isFull:   " + q.isFull());   // true

        // Overflow attempt
        try { q.enqueue(99); }
        catch (IllegalStateException e) {
            System.out.println("Overflow: " + e.getMessage());
        }
    }
}

Output:
Queue (front→back): [10, 20, 30]
Peek:     10
Dequeue:  10
Dequeue:  20
Queue (front→back): [30, 40, 50, 60]
isFull:   true
Overflow: Queue is full (capacity: 5)

Dry Run: Circular Array Wrap-Around

capacity=5, data=[_,_,_,_,_], front=0, rear=0, size=0

enqueue(10): data[0]=10, rear=(0+1)%5=1, size=1
  [10, _, _, _, _]  front=0, rear=1

enqueue(20): data[1]=20, rear=2, size=2
enqueue(30): data[2]=30, rear=3, size=3
  [10, 20, 30, _, _]  front=0, rear=3

dequeue(): value=data[0]=10, data[0]=null, front=(0+1)%5=1, size=2
  [null, 20, 30, _, _]  front=1, rear=3

dequeue(): value=data[1]=20, front=2, size=1
  [null, null, 30, _, _]  front=2, rear=3

enqueue(40): data[3]=40, rear=4, size=2
enqueue(50): data[4]=50, rear=(4+1)%5=0, size=3   ← WRAP! rear goes back to 0
enqueue(60): data[0]=60, rear=1, size=4
  [60, null, 30, 40, 50]  front=2, rear=1

toString: iterate i=0..3: data[(2+0)%5]=data[2]=30, data[3]=40, data[4]=50, data[0]=60
  Output: [30, 40, 50, 60] ✓

Why size and not front==rear for isEmpty/isFull:
  After all 4 elements: front=2, rear=1 (not equal)
  If queue were empty with same indices: front==rear would be true
  Both states can have front==rear — only size distinguishes them.

Implementation 2: Dynamic Array Queue

A dynamic array queue is a circular array that automatically doubles its capacity when full. The resize must re-linearize the elements — copy them starting at index 0 in the new array, resetting front to 0 and rear to size.

Java

public class DynamicArrayQueue<T> {

    private Object[] data;
    private int      front;
    private int      rear;
    private int      size;
    private int      capacity;

    private static final int INITIAL_CAPACITY = 4;

    @SuppressWarnings("unchecked")
    public DynamicArrayQueue() {
        capacity = INITIAL_CAPACITY;
        data     = new Object[capacity];
        front    = 0;
        rear     = 0;
        size     = 0;
    }

    // ENQUEUE — O(1) amortized
    public void enqueue(T value) {
        if (size == capacity) resize();
        data[rear] = value;
        rear       = (rear + 1) % capacity;
        size++;
    }

    // RESIZE — double capacity, re-linearize elements — O(n)
    @SuppressWarnings("unchecked")
    private void resize() {
        int      newCapacity = capacity * 2;
        Object[] newData     = new Object[newCapacity];

        // Copy elements in logical order starting at index 0
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % capacity];
        }

        data     = newData;
        front    = 0;          // Reset front to 0
        rear     = size;       // Reset rear to size (next empty slot)
        capacity = newCapacity;

        System.out.println("  [Resize] capacity: " + (newCapacity / 2)
                           + " → " + newCapacity);
    }

    // DEQUEUE — O(1)
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Empty");
        T value    = (T) data[front];
        data[front] = null;
        front      = (front + 1) % capacity;
        size--;
        return value;
    }

    // PEEK — O(1)
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Empty");
        return (T) data[front];
    }

    public boolean isEmpty()  { return size == 0; }
    public int     size()     { return size; }
    public int     capacity() { return capacity; }

    public static void main(String[] args) {
        DynamicArrayQueue<Integer> q = new DynamicArrayQueue<>();
        System.out.println("Initial capacity: " + q.capacity()); // 4

        for (int i = 1; i <= 9; i++) {
            q.enqueue(i * 10);
            System.out.printf("  Enqueue %2d | size=%d | capacity=%d%n",
                               i * 10, q.size(), q.capacity());
        }
    }
}

Output:
Initial capacity: 4
  Enqueue 10 | size=1 | capacity=4
  Enqueue 20 | size=2 | capacity=4
  Enqueue 30 | size=3 | capacity=4
  Enqueue 40 | size=4 | capacity=4
  [Resize] capacity: 4 → 8
  Enqueue 50 | size=5 | capacity=8
  Enqueue 60 | size=6 | capacity=8
  Enqueue 70 | size=7 | capacity=8
  Enqueue 80 | size=8 | capacity=8
  [Resize] capacity: 8 → 16
  Enqueue 90 | size=9 | capacity=16

Why Re-Linearize During Resize?

Before resize (capacity=4, front=2, rear=1, size=4):
  data = [30, 40, 10, 20]   (elements wrapped around)
           ↑rear      ↑front

If we just copy to a new array naively:
  newData = [30, 40, 10, 20, _, _, _, _]
  front=2 still points to 10, rear=1 still points to 30
  But 10 is at index 2, and we've doubled to 8 — modulo changes!
  (front + i) % 8 would give wrong indices.

Re-linearization (correct approach):
  Copy elements in LOGICAL order (front first):
    newData[0] = data[(2+0)%4] = data[2] = 10
    newData[1] = data[(2+1)%4] = data[3] = 20
    newData[2] = data[(2+2)%4] = data[0] = 30
    newData[3] = data[(2+3)%4] = data[1] = 40
  
  newData = [10, 20, 30, 40, _, _, _, _]
  Reset front=0, rear=4 (size)
  Now all modulo arithmetic works correctly with the new capacity.

Implementation 3: Linked List Queue

Java

public class LinkedListQueue<T> {

    private static class Node<T> {
        T       data;
        Node<T> next;
        Node(T d) { data = d; next = null; }
    }

    private Node<T> head;   // front — dequeue here
    private Node<T> tail;   // back  — enqueue here
    private int     size;

    public LinkedListQueue() { head = null; tail = null; size = 0; }

    // ENQUEUE — O(1)
    public void enqueue(T value) {
        Node<T> newNode = new Node<>(value);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail      = newNode;
        }
        size++;
    }

    // DEQUEUE — O(1)
    public T dequeue() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Empty");
        T       value   = head.data;
        Node<T> removed = head;
        head = head.next;
        if (head == null) tail = null;   // CRITICAL: clear tail when empty
        removed.next = null;             // Detach removed node — help GC
        size--;
        return value;
    }

    // PEEK — O(1)
    public T peek() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Empty");
        return head.data;
    }

    public boolean isEmpty() { return head == null; }
    public int     size()    { return size; }
    public void    clear()   { head = null; tail = null; size = 0; }

    @Override
    public String toString() {
        if (isEmpty()) return "Queue: [] (empty)";
        StringBuilder sb   = new StringBuilder("Queue (front→back): [");
        Node<T>       curr = head;
        while (curr != null) {
            sb.append(curr.data);
            if (curr.next != null) sb.append(", ");
            curr = curr.next;
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> q = new LinkedListQueue<>();

        q.enqueue(10); q.enqueue(20); q.enqueue(30);
        System.out.println(q);                            // [10, 20, 30]
        System.out.println("Dequeue: " + q.dequeue());   // 10
        System.out.println("Dequeue: " + q.dequeue());   // 20
        System.out.println("Dequeue: " + q.dequeue());   // 30 — queue now empty
        System.out.println("isEmpty: " + q.isEmpty());   // true
        // Next enqueue must correctly set both head AND tail
        q.enqueue(99);
        System.out.println("After re-enqueue: " + q);    // [99]
        System.out.println("head==tail: " + (q.head == q.tail)); // true (both at 99)
    }
}

Output:
Queue (front→back): [10, 20, 30]
Dequeue: 10
Dequeue: 20
Dequeue: 30
isEmpty: true
After re-enqueue: Queue (front→back): [99]

Advanced Pattern: Two-Stack Queue

Problem: Implement a queue using only two stacks — no array, no linked list.

Insight: One stack (inbox) receives all enqueues. The other stack (outbox) serves all dequeues. When outbox is empty, transfer all elements from inbox to outbox — this reversal restores FIFO order (the bottom of inbox, which is the oldest element, becomes the top of outbox, which is dequeued first).

Enqueue A, B, C:
  inbox=[A, B, C] (C on top)   outbox=[]

Dequeue:
  outbox empty → transfer inbox to outbox:
    pop C from inbox → push C to outbox
    pop B from inbox → push B to outbox
    pop A from inbox → push A to outbox
  inbox=[]  outbox=[C, B, A] (A on top)
  pop A from outbox → return A ✓ (oldest element first)

Dequeue again:
  outbox=[C, B] (B on top) — still has elements, no transfer needed
  pop B from outbox → return B ✓

Enqueue D:
  inbox=[D]   outbox=[C]
  No transfer — outbox still has C

Dequeue:
  outbox not empty → pop C → return C ✓
  
Dequeue:
  outbox empty → transfer inbox: pop D → push D
  outbox=[D]  → pop D → return D ✓

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class TwoStackQueue<T> {

    private Deque<T> inbox   = new ArrayDeque<>();  // Receives enqueues
    private Deque<T> outbox  = new ArrayDeque<>();  // Serves dequeues

    // ENQUEUE — always to inbox — O(1)
    public void enqueue(T value) {
        inbox.push(value);
    }

    // TRANSFER — move all from inbox to outbox (reversing order) — O(n)
    private void transfer() {
        while (!inbox.isEmpty()) {
            outbox.push(inbox.pop());
        }
    }

    // DEQUEUE — from outbox; transfer if outbox empty — O(1) amortized
    public T dequeue() {
        if (outbox.isEmpty()) {
            if (inbox.isEmpty()) throw new java.util.NoSuchElementException("Empty");
            transfer();
        }
        return outbox.pop();
    }

    // PEEK — peek outbox front; transfer if outbox empty — O(1) amortized
    public T peek() {
        if (outbox.isEmpty()) {
            if (inbox.isEmpty()) throw new java.util.NoSuchElementException("Empty");
            transfer();
        }
        return outbox.peek();
    }

    public boolean isEmpty() { return inbox.isEmpty() && outbox.isEmpty(); }
    public int     size()    { return inbox.size() + outbox.size(); }

    public static void main(String[] args) {
        TwoStackQueue<Integer> q = new TwoStackQueue<>();

        q.enqueue(1); q.enqueue(2); q.enqueue(3);
        System.out.println("Peek:    " + q.peek());       // 1
        System.out.println("Dequeue: " + q.dequeue());    // 1
        System.out.println("Dequeue: " + q.dequeue());    // 2

        q.enqueue(4); q.enqueue(5);

        System.out.println("Dequeue: " + q.dequeue());    // 3
        System.out.println("Dequeue: " + q.dequeue());    // 4
        System.out.println("Dequeue: " + q.dequeue());    // 5
        System.out.println("isEmpty: " + q.isEmpty());    // true
    }
}

Output:
Peek:    1
Dequeue: 1
Dequeue: 2
Dequeue: 3
Dequeue: 4
Dequeue: 5
isEmpty: true

Two-Stack Queue — Amortized Analysis

Why dequeue is O(1) amortized even though transfer is O(n):

Each element passes through the system exactly twice:
  1. Pushed onto inbox  (1 operation per element)
  2. Transferred to outbox (1 operation per element)
  3. Popped from outbox (1 operation per element)
  Total: 3 operations per element = O(1) per element

For n total enqueue+dequeue operations:
  Total transfers across ALL dequeue calls ≤ n (each element transferred once)
  n enqueues + n transfers + n pops = 3n = O(n)
  Amortized per operation: O(n) / n = O(1)

Worst case single dequeue: O(n) (triggers transfer of all n inbox elements)
Amortized over sequence:   O(1) per operation

Implementation Comparison

Property	Fixed Circular Array	Dynamic Array	Linked List	Two-Stack Queue
Enqueue	O(1)	O(1) amortized	O(1)	O(1)
Dequeue	O(1)	O(1)	O(1)	O(1) amortized
Peek	O(1)	O(1)	O(1)	O(1) amortized
Max capacity	Fixed at creation	Unlimited	Unlimited	Unlimited
Memory per element	Value only	Value only	Value + pointer	Value only (in stacks)
Memory layout	Contiguous	Contiguous	Scattered	Contiguous (stack arrays)
Cache performance	Excellent	Excellent	Poor	Good
Overflow possible	Yes	No	No	No
Best for	Known capacity, hot-path	General purpose	Guaranteed O(1)	Interview: queue from stacks

Common Mistakes in Implementation

Not re-linearizing elements during resize. When a circular array queue resizes, front may not be 0 — elements wrap around. Copying the raw array bytes into a new array preserves the wrapped layout, but the modulo arithmetic then uses the wrong capacity. Always copy elements in logical order (index 0 = front, index size-1 = rear) and reset front=0, rear=size after copying.

Using front == rear as the only isEmpty or isFull check. Both an empty and a full circular array queue can have front == rear. Use a size counter (or a boolean full flag) to distinguish the two states. The size == 0 and size == capacity checks are unambiguous.

Forgetting tail = null when the last element is dequeued from a linked-list queue. Setting head = null makes isEmpty() return true, but tail still holds a stale pointer. The next enqueue() takes the non-empty branch, sets tail.next = newNode on garbage memory, and silently corrupts the queue. After head = null, always set tail = null.

Two-stack queue: transferring eagerly instead of lazily. Transfer should happen only when outbox is empty and a dequeue is requested — not on every enqueue. Eager transfer (moving inbox to outbox on every enqueue) gives O(n) per enqueue instead of O(1) amortized.

Not handling the single-element edge case in linked-list queue. When a queue has exactly one element and it is dequeued, head becomes null but tail still points to the removed node. The check if (head == null) tail = null must cover this case. Forgetting it means re-enqueueing after full dequeue produces a broken state.

Interview Questions

Q: What is the time and space complexity of the Two-Stack Queue?

Enqueue is O(1) — always push to the inbox stack. Dequeue is O(1) amortized — each element is pushed to inbox once, transferred to outbox once, and popped from outbox once; total work per element is O(3) = O(1). In the worst case, a single dequeue triggers an O(n) transfer, but across n operations the total transfer work is O(n) — O(1) amortized. Space is O(n) for n elements distributed across the two stacks.

Q: Why must the circular array queue use a size counter instead of relying on front == rear to detect empty and full states?

When the queue is empty, front == rear is true (both at the same position). When the queue is completely full, front == rear is also true — rear has wrapped all the way around and landed back on front. Without a size counter, these two states are indistinguishable. The counter makes isEmpty() and isFull() unambiguous: size == 0 and size == capacity respectively.

Q: Why must elements be re-linearized (not just raw-copied) when resizing a circular array queue?

A circular array queue's elements may wrap around — for example, elements at indices [3, 4, 0, 1] with front=3 and capacity 5. Raw-copying to a new array of capacity 10 preserves the same indices but changes how modulo arithmetic works. The formula (front + i) % capacity now uses the old front and new capacity together, giving wrong indices. Re-linearizing copies elements in logical order to indices [0, 1, 2, 3] and resets front=0, rear=size, making modulo arithmetic correct for the new capacity.

Quick Quiz

Question 1: A circular array queue has capacity=5, front=3, rear=3, size=5. What does isFull() return and why can't you use front==rear alone?

›A) false — because front equals rear, which usually means empty
›B) true — size == capacity is the unambiguous check
›C) Error — this state is impossible
›D) true — because rear has caught up to front

Answer: B) true — size == capacity. When fully filled, rear wraps back to equal front — same position as the empty state. Only the size counter distinguishes them. front == rear is true for BOTH empty (size=0) and full (size=capacity) states.

Question 2: During resize of a circular array queue with front=2, capacity=4, size=4, what are front and rear after re-linearization into a new array of size 8?

›A) front=2, rear=2 — unchanged
›B) front=0, rear=4
›C) front=0, rear=2
›D) front=2, rear=6

Answer: B) front=0, rear=4. Re-linearization copies the 4 elements in logical order to indices 0–3 of the new array. front is reset to 0 (beginning of the re-linearized elements), and rear is reset to size = 4 (the next empty slot). This makes modulo arithmetic consistent with the new capacity.

Question 3: In the Two-Stack Queue, when does transfer from inbox to outbox happen?

›A) On every enqueue — inbox is always flushed to outbox
›B) Lazily — only when outbox is empty AND a dequeue or peek is requested
›C) On every dequeue regardless of outbox state
›D) At fixed intervals of n operations

Answer: B) Lazily, only when outbox is empty. This is the key to amortized O(1). Each element is transferred at most once. If outbox still has elements, dequeue pops directly without any transfer. Eager transfer (on every enqueue) would give O(n) per enqueue.

Question 4: In a linked-list queue, you dequeue the last element. head becomes null. What MUST also happen?

›A) size is decremented — nothing else required
›B) tail must also be set to null
›C) The next node must be found before removing head
›D) front must be reset to 0

Answer: B) tail = null. After dequeuing the last element, head = null signals empty. But tail still holds a dangling pointer to the removed node. The next enqueue takes the non-empty branch (because tail != null) and calls tail.next = newNode on garbage memory — silent corruption. Clearing tail = null whenever head becomes null is mandatory.

Summary

Four complete queue implementations each with distinct tradeoffs:

Fixed Circular Array Queue:

›front, rear, size — three state variables
›rear = (rear + 1) % capacity on enqueue; front = (front + 1) % capacity on dequeue
›isEmpty: size == 0; isFull: size == capacity — never front == rear alone
›Fastest — contiguous memory, no allocation per element, no resizing

Dynamic Array Queue:

›Same as fixed circular array but resize doubles capacity
›Re-linearize on resize: copy logical order (front first), reset front=0, rear=size
›O(1) amortized enqueue — geometric series proof: total copy work ≈ n

Linked List Queue:

›head (front) and tail (back) — both maintained at all times
›Enqueue: tail.next = newNode; tail = newNode (special-case empty queue)
›Dequeue: head = head.next; if head == null then tail = null — the CRITICAL tail-null step
›True O(1) — no amortized cost, no resizing

Two-Stack Queue:

›inbox receives all enqueues; outbox serves all dequeues
›Transfer only when outbox is empty — lazy transfer = amortized O(1) dequeue
›Amortized proof: each element pushed once, transferred once, popped once = O(1) per element
›The canonical interview design pattern

In the next topic, you will explore Queue Collection Frameworks — the built-in queue implementations across Java, Python, C++, and JavaScript with their complete APIs, performance characteristics, and when to choose each.

←

PreviousQueue Operations

NextQueue Collection Frameworks

→