Last in, first out vs first in, first out
- A stack is a pile of plates. You put a plate on top (push), and you take the plate from the top (pop). The last plate you put down is the first one you take: LIFO, last in, first out. Undo, the back button and your program’s function calls all work like this.
- A queue is the line at a bakery. People join at the back (enqueue) and are served from the front (dequeue). The first to arrive is the first served: FIFO, first in, first out. Print jobs, messages and “visit these places in order” work like this.
Both only allow access at the ends, and that’s the point: pushing, popping, enqueuing and dequeuing are all O(1).
Stacks and queues are restricted sequences with O(1) operations at the ends: a stack exposes one end (LIFO), a queue adds at one end and removes at the other (FIFO), and a deque allows both ends. They’re the natural structures for depth-first (stack, including the call stack) and breadth-first (queue) traversal, for matching nested structure, and, in their monotonic variants, for “next greater/smaller element” problems in O(n).
In practice the interesting parts are choosing the right type per language (Java’s Stack and LinkedList are legacy choices; Swift has no standard deque), recursion depth as a hidden stack that can overflow, and the amortized analysis of a queue built from two stacks. All in the Detailed version.
import DequeModule // swift-collections, for the queue below
// Stack: an Array, using the end as the top
var stack: [String] = []
stack.append("home") // push
stack.append("product")
let current = stack.popLast() // pop → "product" (nil if empty)
let top = stack.last // peek → "home"
// Queue: Deque from swift-collections (Swift has no queue in the standard library)
var queue: Deque<String> = []
queue.append("job 1") // enqueue at the back
queue.append("job 2")
let next = queue.popFirst() // dequeue from the front → "job 1"// ArrayDeque works as both a stack and a queue
val stack = ArrayDeque<String>()
stack.addLast("home") // push
stack.addLast("product")
val current = stack.removeLast() // pop → "product"
val top = stack.lastOrNull() // peek → "home"
val queue = ArrayDeque<String>()
queue.addLast("job 1") // enqueue at the back
queue.addLast("job 2")
val next = queue.removeFirst() // dequeue from the front → "job 1"// ArrayDeque works as both a stack and a queue (prefer it to Stack and LinkedList)
Deque<String> stack = new ArrayDeque<>();
stack.push("home"); // push adds to the FRONT
stack.push("product");
String current = stack.pop(); // pop → "product"
String top = stack.peek(); // peek → "home"
Queue<String> queue = new ArrayDeque<>();
queue.offer("job 1"); // enqueue at the back
queue.offer("job 2");
String next = queue.poll(); // dequeue from the front → "job 1" (null if empty)// Stack: an array, using the end as the top
const stack: string[] = [];
stack.push("home"); // push
stack.push("product");
const current = stack.pop(); // pop → "product" (undefined if empty)
const top = stack.at(-1); // peek → "home"
// Queue: no built-in queue type; an array plus a front index
const queue: string[] = [];
let head = 0;
queue.push("job 1"); // enqueue at the back
queue.push("job 2");
const next = queue[head++]; // dequeue from the front → "job 1"Each language has a quirk:
- Swift has no queue type in the standard library. Use
Dequefrom Apple’s swift-collections package, or keep an index to the front of an array. Don’t useremoveFirst()on anArrayas a queue: it shifts every element, O(n). - Kotlin’s
ArrayDequedoes both jobs. Pick one end for a stack (usually the last) and use both ends for a queue. - Java’s
ArrayDequeis the recommended type for both. Its stack methodspush/pop/peekwork on the front, which matters when you print it (see the senior puzzle). The oldStackclass is synchronized and slower. - TypeScript arrays are stacks out of the box (
push,pop). There’s no queue type:shift()re-indexes every element (O(n)), so for long queues keep a head index, as above, or a small ring buffer.
Same pushes, opposite order
Predict the output
1, 2 and 3 are added to a stack and to a queue, then taken out until both are empty. What gets printed?
var stack: [Int] = []
var queue: [Int] = []
for n in [1, 2, 3] {
stack.append(n)
queue.append(n)
}
var fromStack: [Int] = []
while let n = stack.popLast() { fromStack.append(n) }
var fromQueue: [Int] = []
while !queue.isEmpty { fromQueue.append(queue.removeFirst()) } // fine for 3 items
print(fromStack.map(String.init).joined(separator: " "))
print(fromQueue.map(String.init).joined(separator: " "))val stack = ArrayDeque<Int>()
val queue = ArrayDeque<Int>()
for (n in listOf(1, 2, 3)) {
stack.addLast(n)
queue.addLast(n)
}
val fromStack = buildList { while (stack.isNotEmpty()) add(stack.removeLast()) }
val fromQueue = buildList { while (queue.isNotEmpty()) add(queue.removeFirst()) }
println(fromStack.joinToString(" "))
println(fromQueue.joinToString(" "))Deque<Integer> stack = new ArrayDeque<>();
Queue<Integer> queue = new ArrayDeque<>();
for (int n : List.of(1, 2, 3)) {
stack.push(n);
queue.offer(n);
}
StringJoiner fromStack = new StringJoiner(" ");
while (!stack.isEmpty()) fromStack.add(String.valueOf(stack.pop()));
StringJoiner fromQueue = new StringJoiner(" ");
while (!queue.isEmpty()) fromQueue.add(String.valueOf(queue.poll()));
System.out.println(fromStack);
System.out.println(fromQueue);const stack: number[] = [];
const queue: number[] = [];
for (const n of [1, 2, 3]) {
stack.push(n);
queue.push(n);
}
const fromStack: number[] = [];
while (stack.length > 0) fromStack.push(stack.pop()!);
const fromQueue: number[] = [];
while (queue.length > 0) fromQueue.push(queue.shift()!); // fine for 3 items
console.log(fromStack.join(" "));
console.log(fromQueue.join(" "));The stack hands back the most recent element first (LIFO), so it reverses the order: 3 2 1. The queue hands back the oldest element first (FIFO), so it keeps the order: 1 2 3. Reversing is one of the classic uses of a stack.
Queues from stacks, and why amortized matters
A queue can be built from two stacks: push onto inbox; to dequeue, pop from outbox, refilling it from inbox (which reverses the order) only when it’s empty. Each element moves at most twice, so dequeue is O(1) amortized, though a single dequeue can be O(n). That’s fine for throughput and wrong for a latency-sensitive path, the same trade-off as dynamic-array growth.
Stacks you don’t see
- The call stack. Recursion is a stack the runtime manages for you, with a hard size limit: roughly 512 KB to 8 MB depending on platform and thread (secondary threads get less); a JavaScript engine typically allows around ten thousand frames. Recursion depth proportional to input size (a linked list, a degenerate tree, user-controlled nesting) can crash with a stack overflow; converting to an explicit stack moves the data to the heap.
- BFS queues hold a whole frontier: for a wide graph that’s O(V) memory, which matters on mobile.
- Bounded queues (
ArrayBlockingQueue,Channel(capacity),AsyncStreambuffering policies, a Node stream’shighWaterMark) are how producer/consumer systems apply backpressure instead of growing until they run out of memory.
Printing a Java stack
Predict the output
1, 2, 3 are pushed onto a stack. What does printing it show?
var stack: [Int] = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)val stack = ArrayDeque<Int>()
stack.addLast(1)
stack.addLast(2)
stack.addLast(3)
println(stack)Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack);const stack: number[] = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack);An Array used as a stack appends at the end, so it prints in insertion order, top last: [1, 2, 3].
addLast puts each element at the end, and toString lists from first to last: [1, 2, 3], top last.
ArrayDeque.push is addFirst: the top of the stack is the front of the deque, and iteration (and toString) goes from front to back: [3, 2, 1], top first. The legacy Stack class does the opposite ([1, 2, 3]), so code and logs that depend on iteration order change meaning when someone "modernizes" Stack to ArrayDeque.
push appends at the end, so the array prints in insertion order, top last: [ 1, 2, 3 ].
| Swift | Kotlin | Java | TypeScript | |
|---|---|---|---|---|
| Stack | Array: append, popLast, last | ArrayDeque: addLast, removeLast, last() | ArrayDeque: push, pop, peek (front!) | array: push, pop, at(-1) |
| Queue | Deque (swift-collections) or array + head index | ArrayDeque: addLast, removeFirst | ArrayDeque/Queue: offer, poll, peek | array + head index, or a ring buffer |
| Avoid | Array.removeFirst() as a queue (O(n)) | ArrayList.removeAt(0) (O(n)) | Stack (synchronized), LinkedList (cache-unfriendly) | shift() on long queues (O(n)) |
| Blocking/bounded | AsyncStream buffering policy | Channel(capacity) | ArrayBlockingQueue, LinkedBlockingQueue | stream highWaterMark, async iterators |
Gotchas: check leftovers after matching, Java push iterates top-first, recursion depth from user input, Character == in Java.
Check this part
Which order does a stack return elements in?
What is wrong with using
removeFirst()on a SwiftArrayas a queue?What is wrong with usingremoveAt(0)on anArrayListas a queue?What is wrong with usingremove(0)on anArrayListas a queue?What is wrong with usingshift()on a long array as a queue?You
append1, 2, 3 to anArrayused as a stack and print it. What shows?YouaddLast1, 2, 3 to anArrayDequeused as a stack and print it. What shows?Youpush1, 2, 3 onto anArrayDequeand print it. What shows?Youpush1, 2, 3 onto an array used as a stack and log it. What shows?A queue made of two stacks: what is the cost of dequeue?