Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.sh 
#!/usr/bin/env bash
set -euo pipefail

render() {
  local out=""
  for value in "$@"; do
    if [[ -n "$out" ]]; then out+=" -> "; fi
    out+="$value"
  done
  printf '%s\n' "$out"
}

in_stack=()
out_stack=()
for value in 10 20 30; do in_stack+=("$value"); done
while (( ${#in_stack[@]} > 0 )); do out_stack+=("${in_stack[-1]}"); unset 'in_stack[-1]'; done
removed=()
while (( ${#out_stack[@]} > 0 )); do removed+=("${out_stack[-1]}"); unset 'out_stack[-1]'; done
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

  • Keep the explicit stack/queue operations. Library shortcuts that only produce the final list hide the data-structure behavior this lesson is meant to replay.
  • The final output uses a deterministic a -> b -> c format for cross-language comparison.
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.