Implement a generic stack and a generic FIFO queue. What are the gotchas?
Question 132MediumGo 1.22 to 1.25
type Stack[T any] struct{ items []T }
func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }
func (s *Stack[T]) Pop() (T, bool) {
var zero T
if len(s.items) == 0 {
return zero, false
}
i := len(s.items) - 1
v := s.items[i]
s.items[i] = zero // avoid memory leak for pointer types
s.items = s.items[:i]
return v, true
}
type Queue[T any] struct {
buf []T
head, size int
}
func (q *Queue[T]) Enqueue(v T) {
if q.size == len(q.buf) { // grow ring buffer
nb := make([]T, max(1, 2*len(q.buf)))
for i := range q.size {
nb[i] = q.buf[(q.head+i)%len(q.buf)]
}
q.buf, q.head = nb, 0
}
q.buf[(q.head+q.size)%len(q.buf)] = v
q.size++
}
func (q *Queue[T]) Dequeue() (T, bool) {
var zero T
if q.size == 0 {
return zero, false
}
v := q.buf[q.head]
q.buf[q.head] = zero
q.head = (q.head + 1) % len(q.buf)
q.size--
return v, true
}
Gotchas interviewers probe:
- Return
(T, bool), because there is nonilfor T. - Zero out popped slots, or the GC keeps the pointed-to objects alive.
q = q[1:]as a queue leaks the backing array and never reuses space. A ring buffer avoids that.- The zero value
Stack[T]{}is ready to use, so no constructor is needed. - Neither type is goroutine-safe. Add a mutex or document that.
More on Generics
- Q130How does the Go compiler implement generics (GC shape stenciling with dictionaries)? What are the performance implications?
- Q131When should you NOT use generics?
- Q133Implement a generic binary search tree keyed by
cmp.Orderedwith an in-order iterator. - Q134Implement a generic
Set[T]with union, intersection and iteration. - Q135Design a thread-safe generic cache with a
GetOrLoadmethod. What concurrency pitfalls exist? - Q136Write generic
Map,FilterandReducefor slices. Why aren't they in the standard library'sslicespackage?