栈练习_栈的使用练习

第一题：用两个栈实现队列

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int result = stack2.top();
        stack2.pop();
        return result;
        
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

第二题：包含min函数的栈

class Solution {
public:
    //stack2为辅助栈，每次存放输入进来小的数，Stack2由下到上依次递减
    stack<int>stack1,stack2;
    
    void push(int value) {
        stack1.push(value);
        if(stack2.empty()){
            stack2.push(value);
        }
        else if(value <= stack2.top()){
            stack2.push(value);
        }
    }
    void pop() {
        if(stack1.top() == stack2.top())
            stack2.pop();
        stack1.pop();
    }
    int top() {
        return stack1.top();
    }
    int min() {
        return stack2.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第三题：栈的压入、弹出序列

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() != popV.size()) return false;
        
        stack<int> sta;
        int i=0;
        for(auto x:pushV){
            sta.push(x);
            while(sta.size() && sta.top() == popV[i])
            {
                sta.pop();
                i++;
            }
        }
        return sta.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18