Queue from Two Stacks

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

Algorithm

The replay uses the same three values in every language, so this R DSA implementation can be compared directly with the rest of the DSA track.

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 = "")

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.