Created
June 13, 2018 15:57
-
-
Save lkrych/13274b4999fe791f13c1107d92ce777b to your computer and use it in GitHub Desktop.
Stack with minimum using expanded data type
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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