1. Stack
This is your good ol’ LIFO (last-in, first-out) structure. Just imagine a Pringles tube. A basic stack should have the following methods:
- Len
- Peek
- Push
- Pop
In Go, you can use a slice as the underlying data structure.
type Stack[T any] struct {
store []T
}
func NewStack[T any]() *Stack[T] {
return &Stack[T]{
store : make([]T, 0), // Unnecessary
}
}
func (s *Stack[T]) Len() int {
return len(s.store)
}
func (s *Stack[T]) Push(x T) {
s.store = append(s.store, x)
}
func (s *Stack[T]) Peek() (x T, ok bool) {
size := len(s.store)
if size < 1 {
return x, false
}
x = s.store[size - 1]
return x, true
}
func (s *Stack[T]) Pop() (x T, ok bool) {
size := len(s.store)
if size < 1 {
return x, false
}
topIdx := size - 1
x = s.store[topIdx]
var zero T
s.store[topIdx] = zero // prevents memory leak
s.store = s.store[:topIdx]
return x, true
}Notice how initiating the store slice in the NewStack[T any]() constructor is optional? This is because we have enough guardrails to prevent accessing a zero slice by index. A slice variable in Go is just a header that contains a pointer to an underlying fixed array and bounds. Even if you don’t initialize it by calling make(), an empty header with no underlying array will still be created. Nothing will go wrong as long as you don’t access things by index like s.store[0]. The moment you push the first element, the append() operation will allocate a properly defined slice with its own underlying array.
2. Queue
A queue is FIFO (first-in, first-out), just like how you are served at the hot dog truck.
type Queue[T any] struct {
store []T
}
func NewQueue[T any]() *Queue[T] {
return &Queue[T]{
store: make([]T, 0), // Unnecessary
}
}
func (q *Queue[T]) Len() int {
return len(q.store)
}
func (q *Queue[T]) Front() (x T, ok bool) {
if len(q.store) < 1 {
return x, false
}
return q.store[0], true
}
func (q *Queue[T]) Enqueue(x T) {
q.store = append(q.store, x)
}
func (q *Queue[T]) Dequeue() (x T, ok bool) {
if len(q.store) < 1 {
return x, false
}
x = q.store[0]
var zero T
q.store[0] = zero // prevents memmory leak
q.store = q.store[1:]
return x, true
}That’s it!
Common mistakes in implementing stack and queue in Go include:
- Forgetting to check the size of the stack before returning results for
Peek(),Pop(),Front(),Dequeue(). - Forgetting to zero out the top element before reducing the slice size by one when popping/dequeueing, leading to a potential memory leak if the element is a pointer or contains pointers.