文章目录

• 一、栈和队列
• 二、刷题

一、栈和队列

栈：类比羽毛球筒，具有先进后出的性质，只在 栈顶 进行操作。

• 栈的定义：栈顶下标初始化为 $0$ 表示栈空。

队列：类比排队买票，具有先进后出的性质，在 队尾插入 元素，在 队头弹出 元素。

• 队列的定义：队头下标为 $0$，队尾下标为 $-1$ 表示队列为空。

二、刷题

LeetCode 20 有效的括号 原题链接

    $(1)$ 从前往后走，如果遇到左括号压栈之后继续往后走，遇到右括号判断和栈顶元素是否匹配，如果匹配将栈顶元素弹出，不匹配则不合法；
    $(2)$ 只到走到最后同时栈中所有元素都弹出，此时栈为空则合法，如果栈中有剩余则不合法；

class Solution {public:    bool isValid(string s) { stack<char> stk; for (auto c : s) {     if (c == '(' || c == '{' || c == '[') stk.push(c);     else {  if (stk.size() && abs(c - stk.top()) <= 2) stk.pop();  else return false;     } } return stk.empty();    }};

LeetCode 225 用队列实现栈 原题链接

    $(1)$ 队列：进 [ ] 出，其中进表示插入元素的位置，出表示弹出元素的位置，队头方向为右方向；
    $(2)$ 栈：[ ] 进出，其中进表示插入元素的位置，出表示弹出元素的位置，在同一位置进行插入和弹出操作；
    $(3)$ 用 先进先出的逻辑实现 后进先出的逻辑；
    $(4)$队列 $1$ 用来推数据， 队列 $2$ 用来备份数据，缓存；注意：完成之后要保持队列 $1$ 中数据原有的顺序；

class MyStack {public:    queue<int> p, q;    MyStack() {    } void push(int x) { p.push(x);    } int pop() { while (p.size() > 1) q.push(p.front()), p.pop(); int t = p.front(); p.pop(); while (q.size()) p.push(q.front()), q.pop(); return t;    } int top() { while (p.size() > 1) q.push(p.front()), p.pop(); int t = p.front(); p.pop(); q.push(t); while (q.size()) p.push(q.front()), q.pop(); return t;    } bool empty() { return p.empty();    }};

LeetCode 232 用栈实现队列 原题链接

    $(1)$ 用 先进后出的逻辑实现 先进先出的逻辑；
    $(2)$ 栈 $1$ 用来操作数据，栈 $2$ 用来备份数据；

class MyQueue {public:    stack<int> a, b;    MyQueue() {    } void push(int x) { a.push(x);    } int pop() { while (a.size() > 1) b.push(a.top()), a.pop(); int t = a.top(); a.pop(); while (b.size()) a.push(b.top()), b.pop(); return t;    } int peek() { while (a.size() > 1) b.push(a.top()), a.pop(); int t = a.top(); while (b.size()) a.push(b.top()), b.pop(); return t;    } bool empty() { return a.empty();    }};

LeetCode 150 逆波兰表达式 原题链接

    $(1)$ 后缀表达式的优点是做运算的时候不需要考虑括号和优先级；
    $(2)$ 不断地遍历，将字符加到栈里面，如果遇到一个操作符的话就把栈顶的两个元素用这个操作符操作一下然后放到栈里，最后栈顶元素就是最终的结果；
    $(3)$ 注意： 取整和下取整只对于负数时候是不同的。例如，$-1.2$ 下取整是 $-2$，取整是 $-1$，C++ 中的除法是取整；先弹出的是 b，后弹出的是 a；

class Solution {public:    stack<int> stk;    int evalRPN(vector<string>& tokens) { for (auto c : tokens) {     if (c == "+" || c == "-" || c == "*" || c == "/")      {  auto b = stk.top(); stk.pop();  auto a = stk.top(); stk.pop();  if (c == "+") a += b;  else if (c == "-") a -= b;  else if (c == "*") a *= b;  else a /= b;  stk.push(a);     }     else // 注意：要加上     {  stk.push(stoi(c));     }     } return stk.top();    }};