Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.R 
render <- function(values) {
  paste(values, collapse = " -> ")
}

in_stack <- c()
out_stack <- c()
for (value in c(10, 20, 30)) in_stack <- c(in_stack, value)
while (length(in_stack) > 0) {
  out_stack <- c(out_stack, in_stack[length(in_stack)])
  in_stack <- in_stack[-length(in_stack)]
}
removed <- c()
while (length(out_stack) > 0) {
  removed <- c(removed, out_stack[length(out_stack)])
  out_stack <- out_stack[-length(out_stack)]
}
cat(render(removed), "\n", sep = "")

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

  • in_stack <- c() and out_stack <- c() start as empty R vectors.
  • Enqueue appends onto the input stack with in_stack <- c(in_stack, value) for the pinned values 10, 20, and 30.
  • After enqueue, the trace shows in_stack = [10, 20, 30] and out_stack = [].
  • This source treats the right end of each vector as the stack top.
  • Transfer runs while length(in_stack) > 0.
  • in_stack[length(in_stack)] reads the top value from the input stack.
  • out_stack <- c(out_stack, in_stack[length(in_stack)]) pushes that value to the output stack.
  • in_stack <- in_stack[-length(in_stack)] removes the old top by negative indexing.
  • The transfer reverses the stack, producing out_stack = [30, 20, 10] and emptying in_stack.
  • Dequeue then pops from the right end of out_stack with out_stack[length(out_stack)].
  • Each popped scalar is appended to removed with removed <- c(removed, ...).

Replay steps

start:      in [], out [], removed []
enqueue:    in [10, 20, 30], out []
transfer:   in [], out [30, 20, 10]
dequeue:    out [], removed [10, 20, 30]
  • render(removed) uses paste(values, collapse = " -> "), and cat(render(removed), "\n", sep = "") prints 10 -> 20 -> 30.
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.