行百里者半九十 ——栈与队列

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 30. 包含 min 函数的栈

1、 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解：

栈的特性是先进后出，而队列是先进先出，队列的插入操作最简单，直接插入栈A即可，队列的删除操作，即出队列，就需要将栈A中的元素出栈，再压入到栈B，再对栈B出栈，如此出队的顺序才满足先入先出。

#include <iostream>
#include <stack>

using namespace std;

//用两个栈实现队列
class CQueue{
public:
    CQueue(){
    }

    //入队 - 在队尾插入整数
    void appendTail(int value) {
        mStack1.push(value);
    }

    //出队 - 在队首删除整数并返回
    //先判断栈2是否不为空，栈2不为空，肯定是先将栈2出栈，栈2尾的元素肯定是最先进入的
    //再判断栈1(执行到此栈2必空)，栈1为空，就返回-1，否则栈1元素压入栈2，再将栈2尾元素出栈
    int deleteHead() {
        if(!mStack2.empty()){
            int tmp = mStack2.top();
            mStack2.pop();
            return tmp;;
        }
        if(mStack1.empty()) return -1;

        while(!mStack1.empty()){
            int tmp = mStack1.top();
            mStack2.push(tmp);
            mStack1.pop();
        }
        int tmp = mStack2.top();
        mStack2.pop();
        return tmp;;
    }
private:
    stack<int> mStack1;
    stack<int> mStack2;
};

int main()
{
    cout << "Two Stack Make a Queue" << endl;
    CQueue queue;
    queue.appendTail(1);
    queue.appendTail(2);
    queue.appendTail(3);
    cout << queue.deleteHead() << endl;
    queue.appendTail(5);
    cout << queue.deleteHead() << endl;
    cout << queue.deleteHead() << endl;
    cout << queue.deleteHead() << endl;

    return 0;
}

2、包含 min 函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路：
如何在时间复杂度为O(1)的情况下获取栈A中最小元素，可以借助一个辅助栈B。在每次push入栈时，和栈顶的元素比较。
如果压入的元素比栈顶元素小(包括等于)，则同时压入栈A、B，如果压入的元素比栈顶元素大，则只压入栈A。栈A保存所有元素，则栈B中保存A中的非严格降序的子序列。
还有一点，在调用pop函数对A出栈时，也要同时更新栈B的元素，保持降序子序列与A同步。

#include <iostream>
#include <stack>

using namespace std;

class MinStack{
public:
    MinStack() {}

    void push(int x) {
        mStack1.push(x);
        if(mStack2.empty() || x < mStack2.top())
            mStack2.push(x);
    }

    void pop() {
        if(mStack1.top() == mStack2.top())
            mStack2.pop();
        mStack1.pop();  //栈1和栈2要等比较完之后才能出栈
    }

    int top() {
        return mStack1.top();
    }

    int min() {
        return mStack2.top();
    }
private:
    stack<int> mStack1;
    stack<int> mStack2;
};

int main()
{
    cout << "Min Stack!" << endl;
    MinStack* minStack = new MinStack();

    minStack->push(0);
    minStack->push(1);
    minStack->push(0);
    cout << minStack->min() << endl;
    minStack->pop();
    cout << minStack->top() << endl;
    cout << minStack->min() << endl;

    return 0;
}