Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

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

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • Go represents the stack as stack := []int{}. Pushing 10, 20, and 30 uses append(stack, value), which may grow the backing array while preserving the replay-visible order [10, 20, 30].
  • Pop reads the top with stack[len(stack)-1], appends that value to popped, then shrinks the slice header with stack = stack[:len(stack)-1].
  • The loop guard len(stack) > 0 prevents an empty-slice index. Reslicing can keep the backing array alive while the slice is retained, but this replay drains the stack immediately.
  • The trace records stack=[], then stack=[10, 20, 30], then the first pop to popped=[30] and stack=[10, 20], followed by popped=[30, 20, 10] and stack=[].
  • render converts each popped int with fmt.Sprint, joins the strings with strings.Join(parts, " -> "), and fmt.Println prints 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.