What a stack is
A stack is a collection where you can only add and remove elements at one end, called the top. The last element added is the first one removed, an order known as LIFO (last in, first out). A pile of plates works the same way: you put a plate on top and you take a plate from the top.
A stack supports a small set of operations, all of them fast:
- push adds an element on top;
- pop removes and returns the top element;
- peek reads the top element without removing it;
- empty check tells whether there is anything left.
Each of these takes constant time, O(1), in a slice-based stack (push is amortized constant time, because the slice sometimes has to grow).
Building a stack from a Go slice
Go has no built-in stack type. The idiomatic stack is a plain slice where the end of the slice is the top:
- push is
stack = append(stack, x); - peek is
stack[len(stack)-1]; - pop is
stack = stack[:len(stack)-1], which shortens the slice by one; - the stack is empty when
len(stack) == 0.
The end of the slice is the right place for the top because append and re-slicing the last element are cheap, while adding and removing at the front would shift every element.
var s []int
s = append(s, 10)
s = append(s, 20)
s = append(s, 30)
fmt.Println(s, len(s), s[len(s)-1]) // [10 20 30] 3 30
s = s[:len(s)-1]
fmt.Println(s, len(s)) // [10 20] 2
Because append may return a different slice, you must assign its result back to the variable, as in s = append(s, x). The zero value of a slice is nil, which already behaves as an empty stack, so var s []int is all the setup you need.
Wrapping it in a type
When the stack is used in several places, a small struct with methods keeps the intent clear. The methods that change the stack take a pointer receiver, because they reassign the slice field:
type Stack struct {
items []int
}
func (s *Stack) Push(x int) { s.items = append(s.items, x) }
func (s *Stack) Pop() (int, bool) {
if len(s.items) == 0 {
return 0, false
}
last := len(s.items) - 1
x := s.items[last]
s.items = s.items[:last]
return x, true
}
func (s *Stack) Peek() (int, bool) {
if len(s.items) == 0 {
return 0, false
}
return s.items[len(s.items)-1], true
}
func (s *Stack) Len() int { return len(s.items) }
After pushing 1, 2 and 3, Len() is 3 and Peek() returns 3. Three pops return 3, 2 and 1 with true, and a fourth pop returns 0, false. The second return value follows Go's usual value, ok pattern: the caller can tell an empty stack apart from a stored zero.
A classic use: matching brackets
A stack is the natural tool whenever the most recent unfinished thing must be handled first. Checking that brackets are balanced is the standard example. Push every opening bracket; when a closing bracket arrives, it must match the opening bracket on top of the stack.
func balanced(s string) bool {
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
var stack []rune
for _, ch := range s {
switch ch {
case '(', '[', '{':
stack = append(stack, ch)
case ')', ']', '}':
if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
The function returns true for "([]{})" and for the empty string, and false for "(]", "((" and ")". The final comparison len(stack) == 0 catches opening brackets that were never closed, and the len(stack) == 0 test inside the loop catches a closing bracket with nothing to match. In the condition, the length test comes first, so the stack is never indexed when it is empty.
The loop uses range over a string, which yields runes (Unicode code points), so the stack is a []rune and the map goes from rune to rune. Indexing a string with s[i] would give bytes instead, which only works for ASCII text.
Gotchas
- Popping or peeking an empty stack panics.
stack[len(stack)-1]on an empty slice evaluatesstack[-1]and stops the program with an index out of range error. Always checklen(stack) > 0first. - Forgetting to assign
append. Writingappend(stack, x)on its own line is a compile error, because the result is unused. The fix isstack = append(stack, x). - Passing a stack to a function. A slice is passed by value: the callee gets a copy of the slice header (pointer, length, capacity). If the function pushes or pops, the caller's slice keeps its old length. Pass a pointer to the slice, or return the new slice, or use a struct with pointer-receiver methods as above.
- Shared backing arrays. Popping with
s[:len(s)-1]doesn't clear the old element or free its memory. A laterappendoverwrites that slot. If another slice still points to the same array, it sees the change: witha := []int{1, 2, 3}andb := a[:2], the statementb = append(b, 99)turnsainto[1 2 99]. - Stacks of pointers. Popped pointer elements stay reachable through the backing array until they are overwritten. For large objects, set the slot to
nilbefore shortening the slice.
When to reach for a stack
Stack problems tend to share one of these shapes:
- matching or nesting, such as brackets, tags or function calls;
- undo-style behaviour, where the latest action is the first to be reversed;
- the next greater or smaller element, where a stack holds the elements still waiting for an answer;
- replacing recursion with an explicit stack, for instance in a depth-first search, so a deep input can't overflow the call stack.
In each case every element is pushed once and popped at most once, so the total work stays linear in the input size.
Key takeaways
- A stack is last in, first out: push, pop and peek all work at the top.
- In Go, a slice is the stack:
appendto push, indexlen-1to peek, re-slice to pop. - Check for an empty stack before peeking or popping, because an empty slice panics.
- Always assign the result of
appendback, and remember that slices are passed by value. - Reach for a stack when the most recent unfinished item must be resolved first.