Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

Basic Implementation

basic.ts 
function render(values: number[]) {
    return values.join(" -> ");
}
const stack: number[] = [];
for (const value of [10, 20, 30]) {
    stack.push(value);
}
const popped: number[] = [];
while (stack.length > 0) {
    popped.push(stack.pop());
}
console.log(render(popped));

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • TypeScript declares stack and popped as number[], and render(values: number[]) formats numeric arrays.
  • Push uses stack.push(value) for 10, 20, and 30, mutating the same array from [] to [10, 20, 30]. The array end is the stack top.
  • Pop runs inside while (stack.length > 0), so the replay never observes an undefined pop, though TypeScript's array pop() type is still possibly undefined in stricter settings.
  • Popped values are appended with popped.push(...). The trace shows stack = [10, 20] with popped = [30], then stack = [] with popped = [30, 20, 10].
  • console.log(render(popped)) prints 30 -> 20 -> 10. Visible allocation is the short input literal, the stack array, the popped array, and the joined output string; mutation is limited to push and pop operations.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.