스택은 모든 요소들을 Pop하기 이전에는 그 값들을 엑세스할 수 없다는 단점이 있다. 기껏해야 스택 맨 위에 있는 요소(Top)만을 Peek()를 통해 알 수 있는 정도이다.

따라서 최소값을 갖는 요소를 구하기 위해서는 스택에 요소를 추가할 때, 최소값에 대한 정보를 함께 저장해야 한다. 예를 들어, 매번 요소가 추가될 때, 기존 최소값과 추가되는 요소 값을 비교하여 추가 요소가 더 작으면 현재 요소까지의 최소값은 새로 추가되는 요소값이 된다. 따라서 스택에 요소 값을 저장할 때, 요소값과 함께 그 요소까지의 최소값을 함께 저장하면 Min() 메서드 는 O(1) 의 Time Complexity를 갖게 된다. 하지만, 이러한 방식은 스택의 메모리가 요소값 저장소의 2배를 차지한다는 단점이 있다.

이러한 단점을 해결하기 위해 별도의 최소값 전용 스택을 내부에 두고 최소값에 변동이 있을 때에만, 즉 추가 요소값이 기존 최소보다 작은 경우에만, 최소값 스택에 추가하는 방식을 생각해 볼 수 있다. 아래는 이러한 방식을 이용한 코드 샘플이다.

class MinStack
{
    Stack<int> _stack = new Stack<int>();
    Stack<int> _minstk = new Stack<int>();

    public void Push(int value)
    {
        _stack.Push(value);

        if (_minstk.Count == 0 || value < _minstk.Peek())
        {
            _minstk.Push(value);
        }
    }

    public int Pop()
    {
        int value = _stack.Pop();
        if (value == _minstk.Peek())
        {
            _minstk.Pop();
        }
        return value;
    }

    public int Min()
    {
        return _minstk.Peek();
    }
}