SyntaxPilot
Courses/DSA and Coding Problems/Lesson 30
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 30 of 90

Queues: a queue from two stacks, the circular queue

queued

These are the notes for DSA episode 30. A queue serves items in the order they arrived: first in, first out (FIFO). We build it two ways that interviewers love. First from two stacks (LeetCode 232): the obvious way pours the whole stack across and back on every pop, which is O(n) per pop and times out on 2 lakh pops; the fix pours only when the "out" stack is empty, which makes every operation amortized O(1). Then as a circular queue in a fixed-size array (LeetCode 622): shifting every element on each dequeue is O(n); a head index, a count and the remainder operator % make every operation O(1). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

At a railway ticket counter, people join at the back and the clerk serves the front: the person who came first leaves first. That is a queue. A pile of plates in a kitchen is the opposite: you put a plate on top and take a plate from the top, so the last plate in is the first out. That is a stack (LIFO), which we used in episodes 26 to 29.

At the counter In the code
Joining the back of the line enqueue / push (add at the back)
The clerk serving the front person dequeue / pop (remove from the front)
Looking at who is next, without serving peek / front
A pile of plates (take from the top) A stack: last in, first out
A line of people (serve the oldest) A queue: first in, first out

Queues are everywhere in software: printer jobs, ticket bookings, message systems, and breadth-first search (coming in the graphs episodes). They make sure nobody's request jumps the line.

Problem 1: a queue using only stacks

LeetCode 232. Implement a FIFO queue using only stacks. Support:

  • push(x): add x to the back
  • pop(): remove and return the front
  • peek(): return the front without removing it
  • empty(): true if the queue has no items
push 1, push 2, peek → 1, pop → 1, empty → false

Edge cases: popping until the queue is empty, and pushing again after some pops. We test with up to 2 lakh operations, so every operation must be fast.

Brute force: flip the pile, take, flip back

Keep every item in one stack st (newest on top). The front of the queue is at the bottom. To pop, pour the whole stack into a second stack tmp (pouring reverses the order, so the oldest is now on top), take it, and pour everything back.

import java.util.*;

public class Main {
    static Deque<Integer> st = new ArrayDeque<>();
    static Deque<Integer> tmp = new ArrayDeque<>();
    static void push(int x) { st.push(x); }
    static int pop() {
        while (!st.isEmpty()) tmp.push(st.pop());
        int front = tmp.pop();
        while (!tmp.isEmpty()) st.push(tmp.pop());
        return front;
    }
    public static void main(String[] args) {
        push(1); push(2); push(3);
        System.out.println(pop());
        push(4);
        System.out.println(pop());
        System.out.println(pop());
        System.out.println(pop());
    }
}

Output:

1
2
3
4

Correct: first in, first out. In Java, ArrayDeque is the recommended stack: push puts on top, pop takes from the top.

The big input: 2 lakh pops

        int n = 200000;
        for (int i = 0; i < n; i++) push(i);
        long t0 = System.nanoTime(), sum = 0;
        for (int i = 0; i < n; i++) sum += pop();
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("sum " + sum + ", " + ms + " ms");

Result: Time Limit Exceeded (it was still running after 12 seconds locally).

Why the brute force fails

With n items waiting, one pop moves n items there and about n items back: O(n) per pop, and n pops make it O(n²):

Items Moves (about 2n²)
1,000 20 lakh: instant
20,000 80 crore
2 lakh 8 × 10¹⁰: TLE

But right after the first pour, tmp is already in perfect queue order: oldest on top, then the next oldest. Pouring it back throws that work away.

The key insight: two stacks, in and out

A college canteen has two plate racks. The dishwasher stacks clean plates on rack IN. The server takes plates from rack OUT. Only when OUT is empty does a helper turn the whole IN pile over onto OUT, which puts the oldest plate on top. Every plate is flipped across exactly once, and nobody carries plates back.

  1. push(x): always onto in.
  2. pop() / peek(): if out is empty, pour all of in into out.
  3. Then take from the top of out.

Two rules: never pour back, and never pour into a non-empty out (the items in out are older than everything in in, so they must leave first).

Dry run (top of each stack on the right):

Step in out Returns
push 1, 2, 3 1 2 3
pop (out empty: pour) 3 2 1 1
push 4 4 3 2
pop (no pour) 4 3 2
pop (no pour) 4 3
pop (out empty: pour) 4

Amortized O(1)

One unlucky pop can pour n items, so a single pop is not always O(1). But follow one item through its life: pushed onto in, popped off in, pushed onto out, popped off out. Four moves, never more. So any sequence of n operations does at most about 4n moves in total: O(1) per operation on average over the whole sequence. That is called amortized O(1).

The optimal solution in Java (two stacks)

import java.util.*;

public class Main {
    static Deque<Integer> in = new ArrayDeque<>();
    static Deque<Integer> out = new ArrayDeque<>();
    static void push(int x) { in.push(x); }
    static void move() {
        if (out.isEmpty())
            while (!in.isEmpty()) out.push(in.pop());
    }
    static int pop() { move(); return out.pop(); }
    static int peek() { move(); return out.peek(); }
    static boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
    public static void main(String[] args) {
        push(1); push(2);
        System.out.println(peek() + " " + pop() + " " + empty());
        push(3);
        System.out.println(pop() + " " + pop() + " " + empty());
        push(1); push(2); push(3);
        System.out.println(pop());
        push(4);
        System.out.println(pop());
        System.out.println(pop());
        System.out.println(pop());
    }
}

Output:

1 1 false
2 3 true
1
2
3
4

On the big input (2 lakh pushes, 2 lakh pops) it printed sum 19999900000, 250 ms: a fraction of a second instead of a time limit.

The LeetCode-style class version:

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();
    public void push(int x) { in.push(x); }
    private void move() {
        if (out.isEmpty())
            while (!in.isEmpty()) out.push(in.pop());
    }
    public int pop() { move(); return out.pop(); }
    public int peek() { move(); return out.peek(); }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

Two real bugs

Bug 1: pouring every time (the if (out.isEmpty()) is missing):

    static void move() {
        while (!in.isEmpty()) out.push(in.pop());
    }
    // main: push(1); push(2); pop(); push(3); pop();

Output:

1
3

The second pop should be 2. Pouring 3 on top of 2 lets 3 jump the line.

Bug 2: popping an empty queue (push(1); pop(); pop();):

1
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
    at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
    at Main.pop(Main.java:11)
    at Main.main(Main.java:19)

ArrayDeque.pop() throws on an empty deque. LeetCode promises every call is valid; real code should check empty() first.

Problem 2: the circular queue

LeetCode 622. Design a queue that lives in an array of fixed capacity k (it never grows):

  • enQueue(x): add to the back; false if full
  • deQueue(): remove the front; false if empty
  • Front() / Rear(): the first / last item, or -1 if empty
  • isEmpty(), isFull()
k = 3: enQueue(1) true, enQueue(2) true, enQueue(3) true, enQueue(4) false,
       Rear() 3, isFull() true, deQueue() true, enQueue(4) true, Rear() 4

(In the video the methods are written as static functions with lowercase front() and rear() to keep the screen short; the class version is below.)

Brute force: everybody steps forward

Keep the front at index 0. On every dequeue, shift every element one place left, like a line where everyone steps forward when the front person leaves.

public class Main {
    static int[] a;
    static int size = 0;
    static boolean enQueue(int x) {
        if (size == a.length) return false;
        a[size++] = x;
        return true;
    }
    static boolean deQueue() {
        if (size == 0) return false;
        for (int i = 1; i < size; i++) a[i - 1] = a[i];
        size--;
        return true;
    }
    static int front() { return size == 0 ? -1 : a[0]; }
    public static void main(String[] args) {
        a = new int[3];
        System.out.println(enQueue(1) + " " + enQueue(2));
        System.out.println(enQueue(3) + " " + enQueue(4));
        System.out.println(deQueue() + " " + front());
    }
}

Output:

true true
true false
true 2

Correct, but on a full queue of 2 lakh items, served and refilled 2 lakh times:

        int n = 200000;
        a = new int[n];
        for (int i = 0; i < n; i++) enQueue(i);
        long t0 = System.nanoTime(), sum = 0;
        for (int i = 0; i < n; i++) {
            sum += front(); deQueue(); enQueue(i);
        }
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("sum " + sum + ", " + ms + " ms");

Result: Time Limit Exceeded. Every dequeue shifts 2 lakh numbers: 2 lakh × 2 lakh = 4 × 10¹⁰ moves. O(n) per dequeue.

The key insight: move the counter, not the people

At a bank token counter, nobody walks forward when a customer is done; the clerk just calls the next token. So:

  • head = index of the front item; count = how many items are waiting.
  • Dequeue moves head forward by one. Nothing is shifted; the old value is simply ignored.
  • When an index runs past the end, it wraps around to 0, like a clock: 11 o'clock + 3 hours = 2 o'clock, and 14 % 12 = 2.
Operation Formula
first free slot (enQueue) (head + count) % k
dequeue head = (head + 1) % k, count--
rear a[(head + count - 1) % k]
empty / full count == 0 / count == k

Keeping a count makes empty and full trivial to tell apart. The array behaves like a circle: a circular queue, also called a ring buffer.

Dry run, capacity 4:

Moment a[0] a[1] a[2] a[3] head count
start 0 0
enQueue 10, 20, 30, 40 10 20 30 40 0 4 (full)
deQueue twice (10) (20) 30 40 2 2
enQueue 50 → (2+2)%4 = 0 50 (20) 30 40 2 3
enQueue 60 → (2+3)%4 = 1 50 60 30 40 2 4 (full)

Front is a[2] = 30, rear is a[(2+4-1)%4] = a[1] = 60.

The optimal solution in Java (circular queue)

public class Main {
    static int[] a;
    static int head = 0, count = 0;
    static boolean enQueue(int x) {
        if (isFull()) return false;
        a[(head + count) % a.length] = x;
        count++;
        return true;
    }
    static boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % a.length;
        count--;
        return true;
    }
    static int front() { return isEmpty() ? -1 : a[head]; }
    static int rear() {
        return isEmpty() ? -1 : a[(head + count - 1) % a.length];
    }
    static boolean isEmpty() { return count == 0; }
    static boolean isFull() { return count == a.length; }
    public static void main(String[] args) {
        a = new int[3];
        System.out.println(enQueue(1) + " " + enQueue(2) + " " + enQueue(3));
        System.out.println(enQueue(4) + " " + rear() + " " + isFull());
        System.out.println(deQueue() + " " + enQueue(4) + " " + rear());
        System.out.println(front());
    }
}

Output (exactly LeetCode's expected answers):

true true true
false 3 true
true true 4
2

Edge cases, capacity 1:

        a = new int[1];
        System.out.println(front() + " " + rear() + " " + deQueue());
        System.out.println(enQueue(7) + " " + enQueue(8) + " " + rear());
        System.out.println(deQueue() + " " + isEmpty() + " " + front());
-1 -1 false
true false 7
true true -1

The big input (2 lakh items, served and refilled 2 lakh times) printed sum 19999900000, 4 ms.

Bug 3: forgetting %

        a[head + count] = x;      // instead of a[(head + count) % a.length] = x;

On the LeetCode example:

true true true
false 3 true
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
    at Main.enQueue(Main.java:6)
    at Main.main(Main.java:26)

After one dequeue, head = 1 and count = 2, so head + count = 3: past the end. Without the wrap, the free slot at index 0 is never reused.

LeetCode-style class, and the same solutions in other languages

class MyCircularQueue {
    private final int[] a;
    private int head = 0, count = 0;
    public MyCircularQueue(int k) { a = new int[k]; }
    public boolean enQueue(int x) {
        if (isFull()) return false;
        a[(head + count) % a.length] = x;
        count++;
        return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % a.length;
        count--;
        return true;
    }
    public int Front() { return isEmpty() ? -1 : a[head]; }
    public int Rear() { return isEmpty() ? -1 : a[(head + count - 1) % a.length]; }
    public boolean isEmpty() { return count == 0; }
    public boolean isFull() { return count == a.length; }
}

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

class MyQueue {
    stack<int> in, out;
    void move() {
        if (out.empty())
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }
    int pop() { move(); int v = out.top(); out.pop(); return v; }
    int peek() { move(); return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};

class MyCircularQueue {
    vector<int> a;
    int head = 0, count = 0;
public:
    MyCircularQueue(int k) : a(k) {}
    bool enQueue(int x) {
        if (isFull()) return false;
        a[(head + count) % a.size()] = x;
        count++;
        return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % a.size();
        count--;
        return true;
    }
    int Front() { return isEmpty() ? -1 : a[head]; }
    int Rear() { return isEmpty() ? -1 : a[(head + count - 1) % a.size()]; }
    bool isEmpty() { return count == 0; }
    bool isFull() { return count == (int)a.size(); }
};

int main() {
    MyQueue q;
    q.push(1); q.push(2);
    int p = q.peek(), x = q.pop();
    cout << p << " " << x << " " << boolalpha << q.empty() << "\n";
    q.push(3);
    int y = q.pop(), z = q.pop();
    cout << y << " " << z << " " << q.empty() << "\n";

    MyCircularQueue c(3);
    bool e1 = c.enQueue(1), e2 = c.enQueue(2), e3 = c.enQueue(3), e4 = c.enQueue(4);
    cout << e1 << " " << e2 << " " << e3 << " " << e4 << "\n";
    int r = c.Rear(); bool f = c.isFull(), d = c.deQueue(), e5 = c.enQueue(4);
    cout << r << " " << f << " " << d << " " << e5 << " " << c.Rear() << " " << c.Front() << "\n";
}

Output:

1 1 false
2 3 true
true true true false
3 true true true 4 2

In C++, stack::pop() returns nothing, so read top() first. (The calls are in separate statements so the order in which they run is obvious.)

The same solutions in Python

class MyQueue:
    def __init__(self):
        self.inn, self.out = [], []

    def push(self, x):
        self.inn.append(x)

    def _move(self):
        if not self.out:
            while self.inn:
                self.out.append(self.inn.pop())

    def pop(self):
        self._move()
        return self.out.pop()

    def peek(self):
        self._move()
        return self.out[-1]

    def empty(self):
        return not self.inn and not self.out


class MyCircularQueue:
    def __init__(self, k):
        self.a = [0] * k
        self.head = 0
        self.count = 0

    def enQueue(self, x):
        if self.isFull():
            return False
        self.a[(self.head + self.count) % len(self.a)] = x
        self.count += 1
        return True

    def deQueue(self):
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % len(self.a)
        self.count -= 1
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.a[self.head]

    def Rear(self):
        return -1 if self.isEmpty() else self.a[(self.head + self.count - 1) % len(self.a)]

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == len(self.a)


q = MyQueue()
q.push(1); q.push(2)
print(q.peek(), q.pop(), q.empty())
q.push(3)
print(q.pop(), q.pop(), q.empty())

c = MyCircularQueue(3)
print(c.enQueue(1), c.enQueue(2), c.enQueue(3), c.enQueue(4))
print(c.Rear(), c.isFull(), c.deQueue(), c.enQueue(4), c.Rear(), c.Front())

Output:

1 1 False
2 3 True
True True True False
3 True True True 4 2

A Python list is a stack (append / pop()). For a real queue in Python, use collections.deque with append and popleft; list.pop(0) shifts every element, exactly like our slow array.

Complexity

Approach Time per operation Space 2 lakh operations
One stack, pour there and back O(n) per pop O(n) TLE
Two stacks, pour only when out is empty amortized O(1) O(n) 250 ms
Array, shift left on every dequeue O(n) per dequeue O(k) TLE
Circular queue: head, count, % O(1) every operation O(k) 4 ms

The two-stack queue is O(1) amortized: one pop can take O(n), but each item is poured only once, so n operations cost O(n) in total. The circular queue is O(1) for every operation, with no averaging.

Common mistakes

Mistake What you see Why Fix
Pouring in → out on every pop 1, 3 instead of 1, 2 new items land on top of older ones pour only if out.isEmpty()
Pouring out back into in after each pop TLE on 2 lakh pops O(n) per pop never pour back
pop() on an empty queue java.util.NoSuchElementException ArrayDeque.pop() throws when empty check empty() first
peek() on an empty queue, stored in an int NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null peek() returns null on an empty deque, unboxing it to int fails check empty() first
a[head + count] = x (no %) ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3 the index never wraps a[(head + count) % k] = x
Shifting the array on every dequeue TLE O(n) per dequeue move head, keep a count
Only head and tail, no count, k slots can't tell empty from full (head == tail both times) the two states look the same keep a count, or use k + 1 slots

Mini project: a clinic token display

A clinic has a waiting area with 5 chairs. Write a circular queue of capacity 5 that holds token numbers. Read commands like arrive, serve and show: arrive gives the next token number and seats the patient (print "Waiting area full" if there is no chair), serve prints "Now serving token 7", and show prints all waiting tokens from front to rear by walking i = 0 .. count - 1 over a[(head + i) % k]. Extension: when serve is called with nobody waiting, print "No one waiting" instead of crashing.

Practice

  1. Implement a stack using queues (LeetCode 225).
Solution

One queue is enough: after every push, rotate the queue so the new item comes to the front.

    static class MyStack {
        Deque<Integer> q = new ArrayDeque<>();
        void push(int x) {
            q.offer(x);
            for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());
        }
        int pop() { return q.poll(); }
        int top() { return q.peek(); }
        boolean empty() { return q.isEmpty(); }
    }

Push 1, 2, 3, then top(), pop(), pop(), empty() prints 3 3 2 false. Push is O(n), the rest O(1).

  1. Design a circular deque (LeetCode 641): insert and delete at both ends.
Solution

Inserting at the front moves head one step back, wrapped: (head - 1 + k) % k (add k so the value never goes negative).

    static class MyCircularDeque {
        int[] a; int head = 0, count = 0;
        MyCircularDeque(int k) { a = new int[k]; }
        boolean insertFront(int x) {
            if (count == a.length) return false;
            head = (head - 1 + a.length) % a.length;
            a[head] = x; count++; return true;
        }
        boolean insertLast(int x) {
            if (count == a.length) return false;
            a[(head + count) % a.length] = x; count++; return true;
        }
        boolean deleteFront() {
            if (count == 0) return false;
            head = (head + 1) % a.length; count--; return true;
        }
        boolean deleteLast() {
            if (count == 0) return false;
            count--; return true;
        }
        int getFront() { return count == 0 ? -1 : a[head]; }
        int getRear() { return count == 0 ? -1 : a[(head + count - 1) % a.length]; }
    }

With k = 3: insertLast(1) insertLast(2) insertFront(3) insertFront(4) → true true true false; then getRear() deleteLast() insertFront(4) getFront() → 2 true true 4.

  1. Make the circular queue grow: double the array when it is full.
Solution

Copy the items in queue order into the new array, starting at index 0, then reset head.

    static class GrowQueue {
        int[] a = new int[2]; int head = 0, count = 0;
        void enQueue(int x) {
            if (count == a.length) {
                int[] b = new int[a.length * 2];
                for (int i = 0; i < count; i++) b[i] = a[(head + i) % a.length];
                a = b; head = 0;
            }
            a[(head + count) % a.length] = x; count++;
        }
        int deQueue() {
            int v = a[head]; head = (head + 1) % a.length; count--; return v;
        }
    }

Enqueue 1 to 5, then dequeue twice: prints 1 2, and the array has grown to length 8. Doubling makes enqueue amortized O(1), just like ArrayList.

  1. Write the circular queue with head and tail but no count.
Solution

With only head and tail (the next free slot), an empty queue and a full queue both have head == tail. The classic fix is to allocate k + 1 slots and never fill the last one: empty is head == tail, full is (tail + 1) % (k + 1) == head.

    static class HeadTail {
        int[] a; int head = 0, tail = 0;     // tail = next free slot
        HeadTail(int k) { a = new int[k + 1]; }
        boolean isEmpty() { return head == tail; }
        boolean isFull() { return (tail + 1) % a.length == head; }
        boolean enQueue(int x) {
            if (isFull()) return false;
            a[tail] = x; tail = (tail + 1) % a.length; return true;
        }
        boolean deQueue() {
            if (isEmpty()) return false;
            head = (head + 1) % a.length; return true;
        }
    }

With k = 2: isEmpty() enQueue(1) enQueue(2) enQueue(3) isFull() prints true true true false true.

Quick quiz

a = new int[3];
enQueue(1); enQueue(2); enQueue(3);
deQueue(); deQueue();
enQueue(4); enQueue(5);
System.out.println(front() + " " + rear());
  • 1 5
  • 3 5
  • 3 4
  • 4 5
Answer

3 5. After two dequeues, head = 2 and count = 1. 4 goes to (2 + 1) % 3 = 0, 5 goes to (2 + 2) % 3 = 1. The front is a[2] = 3; the rear is a[(2 + 3 - 1) % 3] = a[1] = 5.

Interview questions

  1. Implement a queue using two stacks. What is the complexity? An in stack for pushes and an out stack for pops; pour in into out only when out is empty. Amortized O(1) per operation, O(n) space.
  2. Why is it amortized O(1) when one pop can take O(n)? Each item moves at most four times in its life (push in, pop in, push out, pop out), so n operations do at most about 4n moves.
  3. Why must you never pour into a non-empty out? The items already in out are older than everything in in; pouring would put newer items on top of them and break FIFO order.
  4. Design a circular queue. How do you tell empty from full? Keep a count (empty: 0, full: k), or keep head and tail and leave one slot unused (k + 1 slots).
  5. What does % do in a ring buffer? It wraps an index that runs past the end back to the start: (head + count) % k.
  6. How do you move head backwards safely? (head - 1 + k) % k; in Java, -1 % k is -1, not k - 1.
  7. Where are circular buffers used in real systems? Keyboard and network buffers, audio streaming, logging the last N events, and producer-consumer queues between threads.
  8. What should you use for a queue in Java, C++ and Python? ArrayDeque (offer / poll), std::queue or std::deque, and collections.deque (append / popleft).

Glossary

Term Meaning
Queue A line of items where you add at the back and remove from the front: first in, first out
FIFO First in, first out: the oldest item leaves first
LIFO Last in, first out: the newest item leaves first (a stack)
Stack A pile where you add (push) and remove (pop) only at the top
Enqueue Add an item to the back of a queue (push, offer, enQueue)
Dequeue Remove the item at the front of a queue (pop, poll, deQueue)
Front / Rear The first item (next to leave) / the last item (most recently added)
Peek Look at the front (or top) without removing it
Pouring Popping every item off one stack and pushing it onto another, which reverses the order
Amortized O(1) The average cost per operation over any whole sequence is O(1), even if one operation is sometimes expensive
Circular queue / ring buffer A queue in a fixed array whose indices wrap around to 0 after the end
head The index of the front item in a circular queue
count How many items are in the circular queue right now
% (remainder, modulo) The remainder after division; 14 % 12 = 2, used to wrap indices
Capacity The fixed maximum number of items (k)
ArrayDeque Java's double-ended queue; works as a stack (push/pop) or a queue (offer/poll)
NoSuchElementException Thrown by ArrayDeque.pop() when the deque is empty
ArrayIndexOutOfBoundsException Thrown when an array index is below 0 or at least the array's length
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • A queue is first in, first out. Building it from one stack by pouring there and back on every pop is O(n) per pop and times out on 2 lakh pops.
  • Two stacks, in and out: push onto in; pop from out, pouring all of in into out only when out is empty. Each item is poured once: amortized O(1).
  • A circular queue in a fixed array: don't shift, move head; keep a count; wrap every index with % k. O(1) for every operation; forgetting % gives ArrayIndexOutOfBoundsException.

Next episode: Backtracking: subsets and permutations.