Skip to content

Instantly share code, notes, and snippets.

@lkrych
Created June 13, 2018 15:57
Show Gist options
  • Save lkrych/13274b4999fe791f13c1107d92ce777b to your computer and use it in GitHub Desktop.
Save lkrych/13274b4999fe791f13c1107d92ce777b to your computer and use it in GitHub Desktop.
Stack with minimum using expanded data type
//the key to this implementation is using a different data structure in the stack.
//each val in the stack contains the current minimum at the time of insertion.
type stackVal struct {
val int
min int
}
type stackWithMin struct {
data []stackVal
}
func (s *stackWithMin) pop() int {
popped := s.data[len(s.data)-1]
s.data = s.data[:len(s.data)-1]
return popped.val
}
func (s *stackWithMin) push(item int) {
currentMin := s.min()
if item < currentMin { //update the minimum in the stackVal struct
currentMin = item
}
val := stackVal{
val: item,
min: currentMin,
}
s.data = append(s.data, val)
}
func (s *stackWithMin) min() int {
if s.isEmpty() {
return 100000000000000000 //Not the most elegant way to handle this, but if there is no min, just return a large number
}
data := s.data[len(s.data)-1]
return data.min
}
func (s *stackWithMin) peek() int {
data := s.data[len(s.data)-1]
return data.val
}
func (s *stackWithMin) isEmpty() bool {
return len(s.data) == 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment