实现一个栈，push、pop、求栈中最小值min的时间复杂度为O(1)

使用平台：vs2013

一个问题肯定不止一种解法，我下面给的是利用两个栈来求去栈中最小值，当然一个栈也可以求取问题。一个栈的求解这里就只给出思路。
    一个栈求解：每次push，push两个值，当前要push的值，和最小值，这样就可以实现一个栈求解问题，但是这样做的话每次取栈顶的值或者push时会比较麻烦。所以可以借助pair来存取当前值和最小值。

---

问题分析：

每次插入时：
    1.先判断_min是否为空，为空则插入时_s和_min同时插入
    2.如果_min栈顶的值大于等于即将要插入的值，_s和 _min同时插入

每次删除时：
     1. 首先要判断，_s是否还有元素，可以删除
     2. 当_min的栈顶元素和 _s的栈顶元素相同时，同时pop

代码部分：

#pragma once
#include<iostream>
using namespace std;

#include<assert.h>
#include<stack>

//问题1：实现一个栈，push、pop、min的时间复杂度为O(1)
class Stack
{
public:
    void Push(const int x)
    {
        if (_min.empty())
        {
            _s.push(x);
            _min.push(x);
            return;
        }
        //注意判断条件为>=，当_min的栈顶元素大于、等于x时，都需要插入
        if (_min.top() >= x)
            _min.push(x);
        _s.push(x);
    }

    void Pop()
    {
        //若_s不为空，则_min肯定也不为空
        if (_s.empty())
            return;
        if (_s.top() == _min.top())
            _min.pop();
        _s.pop();
    }

    int StackMin()
    {
        assert(!_min.empty());
        return _min.top();
    }
protected:
    stack<int> _s;
    stack<int> _min;
};

测试部分：

void TestStack()
{
    Stack s;
    s.Push(6);
    s.Push(7);
    s.Push(2);
    s.Push(2);
    s.Push(3);
    cout <<"min?"<< s.StackMin() << endl;

    s.Pop();
    s.Pop();
    cout << "min?" << s.StackMin() << endl;

    s.Pop();
    s.Pop();
    cout << "min?" << s.StackMin() << endl;

    s.Pop();
    s.Pop();//空
    cout << "min?" << s.StackMin() << endl;//出现断言提示
}

目前正处于学习中，可能有许多不全面之处和错误，希望大家谅解和指出，便于共同学习和进步！！！

栈和队列常见面试题
1、判断元素出栈合法性
2、使用两个栈实现一个队列
3、使用两个队列实现一个栈
4、利用一个数组实现两个栈