程序员代码面试指南1.1：设计getMin功能的栈

思路

用两个栈来实现，其中一个作为最小栈，操作思路：

1. push时，只有最小栈为空或者当前元素 ≤ 最小栈顶元素时，才push到最小栈中；
2. pop时，只有栈顶元素等于最小栈顶元素时，才将最小栈顶元素弹出。

由于数据保证没有不合法的操作，这里就不做判空异常了。

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<int> stk, stkMin;

int getMin()
{
    return stkMin.top();
}

void push(int num)
{
    if (stkMin.empty()) stkMin.push(num);            //最小栈为空
    else if (num <= getMin()) stkMin.push(num);        //当前元素 ≤ 最小栈顶元素

    stk.push(num);
}

void pop()
{    
    int num = stk.top();
      stk.pop();

    if (num == getMin())        //栈顶元素等于最小栈顶元素
    {
        stkMin.pop();
    }
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        string s;
        cin >> s;

        if (s == "push")        //push操作还需要额外读入一个数字
        {
            int num;
            cin >> num;
            push(num);
        }
        else if (s == "pop")
        {
            pop();
        }
        else                    //只有getMin操作需要输出
        {
            cout << getMin() << endl;
        }
    }

    return 0;
}