代码随想录笔记--栈与队列篇

1--用栈实现队列

利用两个栈，一个是输入栈，另一个是输出栈；

#include <iostream>
#include <stack>

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) {
        in_stk.push(x);
    }
    
    int pop() {
        if(out_stk.empty()){
            while(!in_stk.empty()){
                out_stk.push(in_stk.top());
                in_stk.pop();
            }
        }
        int tmp = out_stk.top();
        out_stk.pop();
        return tmp;
    }
    
    int peek() {
        if(out_stk.empty()){
            while(!in_stk.empty()){
                out_stk.push(in_stk.top());
                in_stk.pop();
            }
        }
        return out_stk.top();
    }
    
    bool empty() {
        if(out_stk.empty() && in_stk.empty()) return true;
        else return false;
    }
private:
    std::stack<int> in_stk, out_stk;
};

int main(int argc, char* argv[]){
    MyQueue Queue;
    Queue.push(1);
    Queue.push(2);
    Queue.push(3);
    std::cout << Queue.pop() << std::endl;
    std::cout << Queue.peek() << std::endl;

    return 0;
}

2--用队列实现栈

主要思路：

弹出栈顶元素时，需要将队列前 size - 1 个元素先弹出再重新加入到队列中；

#include <iostream>
#include <queue>

class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        for(int i = 1; i <= size - 1; i++){
            q.push(q.front());
            q.pop();
        }
        int tmp = q.front();
        q.pop();
        return tmp;
    }
    
    int top() {
        int size = q.size();
        for(int i = 1; i <= size - 1; i++){
            q.push(q.front());
            q.pop();
        }
        int tmp = q.front();
        q.pop();
        q.push(tmp);
        return tmp;
    }
    
    bool empty() {
        return q.empty();
    }
private:
    std::queue<int> q;
};

int main(int argc, char* argv[]){
    MyStack stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    std::cout << stk.pop() << std::endl;
    std::cout << stk.top() << std::endl;
    return 0;
}

3--有效的括号

主要思路：

基于栈，遇到左括号，入栈对应的右括号。遇到右括号，判断当前栈顶元素是否与右括号相等，相等则表示之前曾遇到对应的左括号，表明匹配成功并弹出栈顶元素，否则返回 false；

最后判断栈是否为空，即是否有未匹配的左括号；

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

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> stk;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(') stk.push(')');
            else if(s[i] == '[') stk.push(']');
            else if(s[i] == '{') stk.push('}');
            else{
                if(stk.empty()) return false;
                else if(stk.top() != s[i]) return false;
                else stk.pop(); // 匹配
            }
        }
        return stk.empty();
    }
};

int main(int argc, char* argv[]){
    std::string test = "()[]{}";
    Solution S1;
    bool res = S1.isValid(test);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}