Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

stack.go

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())
}