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): addxto the backpop(): remove and return the frontpeek(): return the front without removing itempty():trueif 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.
push(x): always ontoin.pop()/peek(): ifoutis empty, pour all ofinintoout.- 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;falseif fulldeQueue(): remove the front;falseif emptyFront()/Rear(): the first / last item, or-1if emptyisEmpty(),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
headforward 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
- 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).
- 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.
- 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.
- Write the circular queue with
headandtailbut nocount.
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 53 53 44 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
- Implement a queue using two stacks. What is the complexity? An
instack for pushes and anoutstack for pops; pourinintooutonly whenoutis empty. Amortized O(1) per operation, O(n) space. - 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.
- Why must you never pour into a non-empty
out? The items already inoutare older than everything inin; pouring would put newer items on top of them and break FIFO order. - Design a circular queue. How do you tell empty from full? Keep a
count(empty: 0, full: k), or keepheadandtailand leave one slot unused (k + 1 slots). - What does
%do in a ring buffer? It wraps an index that runs past the end back to the start:(head + count) % k. - How do you move
headbackwards safely?(head - 1 + k) % k; in Java,-1 % kis-1, notk - 1. - 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.
- What should you use for a queue in Java, C++ and Python?
ArrayDeque(offer/poll),std::queueorstd::deque, andcollections.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,
inandout: push ontoin; pop fromout, pouring all ofinintooutonly whenoutis empty. Each item is poured once: amortized O(1). - A circular queue in a fixed array: don't shift, move
head; keep acount; wrap every index with% k. O(1) for every operation; forgetting%givesArrayIndexOutOfBoundsException.
Next episode: Backtracking: subsets and permutations.