stack.go

// Idiomatic and efficient stack. Uses a single array. 

type Stack interface {
  // Push adds an item to a stack.
  Push(i int) 
  // Pop is the item that was popped, max and sz represent the state of the stack after the pop.
  Pop() (cur,max, sz int)
  // Peek the current state of the stack. An empty stack returns all zeros. 
  Peek() (cur,max, sz int)
}

type frame struct { max, cur int }
type stack []frame 

func NewStack() Stack {
  return &stack{}
}

func (s* stack) Push(item int) {
  sz:= 0; f := frame {cur: item}
  if _, f.max, sz = s.Peek(); sz == 0 || f.max < item {
    f.max = item
  } 
  *s = append(*s, f)
}

func (s *stack) Pop() (cur,max,sz int) {
  if sz = len(*s); sz > 0 {
    cur = (*s)[sz-1].cur
    *s = (*s)[:sz-1]
    _, max, sz = s.Peek()
  }
  return
}

func (s stack) Peek() (cur,max,sz int) { 
  if sz = len(s); sz > 0 {
    cur, max,sz = s[sz-1].cur, s[sz-1].max, sz
  } 
  return 
}