Go

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 no nil for 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

All 36 Generics questions