Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

Algorithm

Basic Implementation

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

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • TypeScript declares inStack, outStack, and removed as number[], and render(values: number[]) formats numeric arrays.
  • Enqueue appends 10, 20, and 30 with inStack.push(value), mutating the input stack from [] to [10, 20, 30].
  • Transfer runs while inStack.length > 0, using inStack.pop() and outStack.push(...). The transfer and removal loops are length-guarded, so the replay never observes an undefined pop, though TypeScript's array pop() type is still possibly undefined in stricter settings.
  • The transfer reverses order in the arrays: inStack = [10, 20, 30], outStack = [] becomes inStack = [], outStack = [30, 20, 10].
  • The removal loop pops outStack into removed, producing removed = [10, 20, 30] and outStack = [], which is the FIFO queue order.
  • console.log(render(removed)) prints 10 -> 20 -> 30. Visible allocation is the short input literal, the three arrays, and the joined output string; mutation is limited to push and pop operations.
input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.