A stack is last-in-first-out: the most recently pushed value is the first one popped. Go has no built-in Stack type; a slice with Push/Pop methods is the idiomatic way to build one.
The rule
Last in, first out
Values come off in the reverse of the order they went on.
- Push: add a value to the top.
- Pop: take the top value off and hand it back.
- Peek: look at the top value without removing it.
A stack is last-in-first-out: Push adds to the top, Pop removes from the top, Peek reads the top without removing it. Try it below.
Purpose
Hold values while the only one you need back is the most recent.
Input
Values pushed one at a time onto a []int.
Output
The most recently pushed value, handed back by Pop.
Constraints
- Popping an empty stack has to be guarded, or the index goes negative.
- Only the top is reachable. Getting at the middle means popping down to it.
- The backing array is kept after a pop, so a stack that spiked once stays large.
Push appends to the end of the slice. Pop reads and removes that same end, the top of the stack; Peek reads it without removing it. Both report false instead of panicking when the stack is empty.
type Stack []int
func (s *Stack) Push(v int) {
*s = append(*s, v)
}
func (s *Stack) Pop() (int, bool) {
if len(*s) == 0 {
return 0, false
}
v := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return v, true
}
func (s Stack) Peek() (int, bool) {
if len(s) == 0 {
return 0, false
}
return s[len(s)-1], true
}Pushing 1, 2, 3 and popping once removes 3, leaving [1 2] behind. Pop always removes from the end, never the front.
var s Stack
s.Push(1)
s.Push(2)
s.Push(3)
v, _ := s.Pop()
fmt.Println(v)
fmt.Println(s)Stack operations
| Operation | Behavior |
|---|---|
Push(v) | Appends v to the end of the slice, the top of the stack. |
Pop() | Removes and returns the last element. ok is false if the stack is empty. |
Peek() | Reads the last element without removing it. |
len(s) | Number of elements currently on the stack. |
Growth
The whole program main.go Show
package main
import "fmt"
type Stack []int
func (s *Stack) Push(v int) { *s = append(*s, v) }
func (s *Stack) Pop() (int, bool) {
if len(*s) == 0 {
return 0, false
}
v := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return v, true
}
func (s Stack) Peek() (int, bool) {
if len(s) == 0 {
return 0, false
}
return s[len(s)-1], true
}
func main() {
var s Stack
s.Push(1)
s.Push(2)
s.Push(3)
v, _ := s.Pop()
fmt.Println(v)
fmt.Println(s)
}A slice-backed stack's Push is cheap on average: append only allocates a bigger array and copies when the current one runs out of room, and it doubles the room each time, so that happens on a smaller and smaller share of pushes as the stack grows.
$ go run stack.go
3
[1 2]