栈和队列

使用两个栈构造一个队列

/*
 * Basic idea:
 *     1. the top of stack1 as queue rear
 *     2. the top of stack2 as queue front
 */
 
#include <stack>
#include <iostream>
 
using namespace std;
 
class Queue {
private:
    stack<int> s1;
    stack<int> s2;
 
public:
    void push(int _node) {
        s1.push(_node);
    }
 
    int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int res = s2.top();
        s2.pop();
        return res;
    }
};

使用两个队列构造一个栈

/*
 * 1. queue2 as a auxiliary storage
 * 2. push: push to the rear of queue1
 * 3. pop: 
 *    3.1. quque1 has only one element, pop it
 *    3.2. pop the elements of queue1, push them to queue2
 *         till queue1 has exactly one left, pop it
 *    then pop elems of queue2 push to queue1
 */
 
#include <queue>
 
using namespace std;
 
class Stack {
private:
    queue<int> q1;
    queue<int> q2;
 
public:
    void push(int _node) {
        q1.push(_node);
    }
 
    int pop() {
        while (q1.size() != 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int res = q1.front();
        q1.pop();
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return res;
    }
};

判断可能的出栈序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

/*
 * The idea is I push all elems of `pushV` into 
 * a stack `s`, simultaneously, I track if the elems 
 * of `popV` equal to the `s.top()`. If it is, I will
 * pop a elem from the stack and track the next elem
 * of `popV` till a mismatch. Then I'll continue to push
 * elems into the stack.
 *
 * When I run out all elems of `pushV`, I check if the
 * stack is empty, if it is, then the `popV` should be
 * a possible pop sequence or vice versa.
 *
 * Credit: https://www.nowcoder.com/profile/248554
 */
 
#include<iostream>
#include<stack>
#include<vector>
 
using namespace std;
 
class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        // border case
        if (pushV.size() == 0) return false;
        
        stack<int> s;
        auto i = 0, j = 0;
        while (i != pushV.size()) {
            s.push(pushV[i++]);
            // KEY POINT here
            while (!s.empty()
                && s.top() == popV[j]
                && j != popV.size()) {
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
};
 
// test
int main() {
    vector<int> pushV = {1,2,3,4,5};
    vector<int> popV = {4,5,3,2,1};
    cout << Solution().IsPopOrder(pushV, popV);
    return 0;
}