Skip to content

Instantly share code, notes, and snippets.

@patrickdappollonio
Last active April 8, 2016 19:41
Show Gist options
  • Save patrickdappollonio/eb570ac0f10289c6a9195f0dc3e11b9e to your computer and use it in GitHub Desktop.
Save patrickdappollonio/eb570ac0f10289c6a9195f0dc3e11b9e to your computer and use it in GitHub Desktop.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
package main
import (
"fmt"
"sort"
)
type Stack struct {
st []int
ordered []int
}
type IntSlice []int
func (p IntSlice) Len() int {
return len(p)
}
func (p IntSlice) Less(i, j int) bool {
return p[i] < p[j]
}
func (p IntSlice) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
}
// CreateStack creates an empty stack of
// integers
func CreateStack() *Stack {
st := make([]int, 0)
ordered := make([]int, 0)
return &Stack{st, ordered}
}
// Push should append an element at the end of the stack
func (s *Stack) Push(x int) {
s.st = append(s.st, x)
s.ordered = append(s.ordered, x)
sort.Sort(IntSlice(s.ordered))
}
// Pop should return the first element in the stack
// and remove it
func (s *Stack) Pop() int {
if len(s.st) == 0 {
panic("Stack is empty")
}
number := s.st[0]
s.st = append([]int{}, s.st[1:]...)
for pos, val := range s.ordered {
if val == number {
s.ordered = append(s.ordered[:pos], s.ordered[pos+1:]...)
break
}
}
return number
}
// GetMin returns the smallest number in the stack
func (s *Stack) GetMin() int {
if len(s.ordered) == 0 {
panic("Stack is empty")
}
return s.ordered[0]
}
func main() {
// Create an empty stack
st := CreateStack()
// Push a few numbers
st.Push(1)
st.Push(5)
st.Push(1)
st.Push(3)
// Print the stack
fmt.Println("Stack:", st.st)
// Pop an element
fmt.Println("Pop first")
n := st.Pop()
fmt.Println("Popped element:", n)
fmt.Println("Stack:", st.st)
// Find the smallest number
fmt.Println("Smallest number:", st.GetMin())
// Popping one and trying again
st.Pop()
fmt.Println("Smallest number:", st.GetMin())
// Popping one and trying again
st.Pop()
fmt.Println("Smallest number:", st.GetMin())
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment