Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.go 
package main

import (
	"fmt"
	"strings"
)

func render(values []int) string {
	parts := make([]string, 0, len(values))
	for _, value := range values {
		parts = append(parts, fmt.Sprint(value))
	}
	return strings.Join(parts, " -> ")
}

func main() {
	inStack := []int{}
	outStack := []int{}
	for _, value := range []int{10, 20, 30} { inStack = append(inStack, value) }
	for len(inStack) > 0 { outStack = append(outStack, inStack[len(inStack)-1]); inStack = inStack[:len(inStack)-1] }
	removed := []int{}
	for len(outStack) > 0 { removed = append(removed, outStack[len(outStack)-1]); outStack = outStack[:len(outStack)-1] }
	fmt.Println(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

  • Go represents both stacks as []int slices: inStack := []int{} receives enqueues and outStack := []int{} supplies dequeues.
  • Enqueue uses append(inStack, value) for 10, 20, and 30; append may grow the backing array, while the replay-visible state becomes inStack=[10, 20, 30].
  • The transfer loop pops from the end with inStack[len(inStack)-1], appends that value to outStack, and shrinks the input slice with inStack = inStack[:len(inStack)-1], producing outStack=[30, 20, 10].
  • The dequeue loop uses the same end-pop pattern on outStack, appending values to removed as [10, 20, 30]. The len(...) > 0 guards prevent empty-slice indexing.
  • Reslicing changes slice headers and can keep backing arrays alive while a slice is retained; this small replay drains both stack slices immediately.
  • render converts the removed int values with fmt.Sprint, joins them with strings.Join(parts, " -> "), and fmt.Println 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.