package stack

import "gitee.com/guuzaa/algorithm/constraints"

type MinStack[T constraints.Ordered] struct {
	top *minNode[T]
}

type minNode[T constraints.Ordered] struct {
	prev     *minNode[T]
	min, val T
}

func NewMinStack[T constraints.Ordered]() MinStack[T] {
	return MinStack[T]{nil}
}

func (s *MinStack[T]) Push(val T) {
	var n *minNode[T]
	if s.top == nil || s.top.min > val {
		n = &minNode[T]{s.top, val, val}
	} else {
		n = &minNode[T]{s.top, s.top.min, val}
	}
	s.top = n
}

func (s *MinStack[T]) Peek() T {
	return s.top.val
}

func (s *MinStack[T]) GetMin() T {
	return s.top.min
}

func (s *MinStack[T]) Pop() T {
	n := s.top
	s.top = s.top.prev
	return n.val
}