Stacks and Queues

Stack Push/Pop

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

Algorithm

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

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

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

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))
}

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.