A stack is a LIFO (last-in, first-out) container with two main operations:

  • Push — put an element on top.
  • Pop — take the top element off.

Common third operation:

  • Peek — look at the top without removing.

Complexity

Op Time
Push Amortized O(1)
Pop O(1)
Peek O(1)
Len O(1)

Real-world uses

  • Function call frames (the program stack).
  • Undo/redo.
  • Depth-first traversal of trees and graphs (iterative).
  • Expression evaluation (Shunting-yard, RPN).
  • Balanced-bracket / syntax checking.

Go implementation choice

A slice already provides O(1) amortized append and O(1) pop from the end, so we back the stack with a slice. We use generics so it works for any type:

type Stack[T any] struct {
    data []T
}

We expose Push, Pop, Peek, Len. We also include a free function BalancedBrackets that uses the stack to validate a string of ()[]{}.

Run the tests

go test ./part2-dsa/ds/stack