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.js 
function render(values) {
    return values.join(" -> ");
}
const stack = [];
for (const value of [10, 20, 30]) {
    stack.push(value);
}
const popped = [];
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

  • JavaScript represents the stack with a mutable Array of Number values. stack.push(value) appends 10, 20, and 30 at the end, making the array end the top of the stack.
  • Pop uses stack.pop(), which removes and returns the last element in O(1) amortized time for a normal JavaScript array. The same stack array is mutated in place rather than replaced.
  • Popped values are collected in a second Array with popped.push(...). The replay shows stack moving from [] to [10, 20, 30], then to [10, 20] after popping 30, and finally to [] with popped = [30, 20, 10].
  • render(popped) uses values.join(" -> "), so console.log prints the deterministic output 30 -> 20 -> 10. Allocation is limited to the short input literal, the stack array, the popped array, and the joined output string, all managed by the JavaScript runtime GC.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.