stack.go

// Package stack provides a generic LIFO stack backed by a slice, plus a
// classical balanced-brackets checker that uses the stack.
package stack

// Stack is a last-in, first-out container.
//
// The zero value is a usable empty stack:
//
//	var s stack.Stack[int]
//	s.Push(1)
type Stack[T any] struct {
	data []T
}

// New returns a new empty stack with the given initial capacity.
func New[T any](initialCap int) *Stack[T] {
	if initialCap < 0 {
		initialCap = 0
	}
	return &Stack[T]{data: make([]T, 0, initialCap)}
}

// Len returns the number of elements currently on the stack.
func (s *Stack[T]) Len() int {
	return len(s.data)
}

// Push adds v to the top of the stack.
func (s *Stack[T]) Push(v T) {
	s.data = append(s.data, v)
}

// Pop removes and returns the top of the stack along with true. If the stack
// is empty it returns the zero value of T and false.
func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	n := len(s.data)
	if n == 0 {
		return zero, false
	}
	v := s.data[n-1]
	s.data[n-1] = zero // help GC if T contains pointers
	s.data = s.data[:n-1]
	return v, true
}

// Peek returns the top of the stack without removing it.
func (s *Stack[T]) Peek() (T, bool) {
	var zero T
	n := len(s.data)
	if n == 0 {
		return zero, false
	}
	return s.data[n-1], true
}

// Snapshot returns a copy of the stack contents from bottom to top.
func (s *Stack[T]) Snapshot() []T {
	out := make([]T, len(s.data))
	copy(out, s.data)
	return out
}

// BalancedBrackets reports whether the brackets in s ( () [] {} ) are
// matched and properly nested. Non-bracket runes are ignored.
func BalancedBrackets(s string) bool {
	pair := map[rune]rune{')': '(', ']': '[', '}': '{'}
	st := New[rune](len(s) / 2)
	for _, ch := range s {
		switch ch {
		case '(', '[', '{':
			st.Push(ch)
		case ')', ']', '}':
			top, ok := st.Pop()
			if !ok || top != pair[ch] {
				return false
			}
		}
	}
	return st.Len() == 0
}