C++数据结构与算法——栈与队列

C++���二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

• 一、用栈实现队列（力扣232）
• 二、用队列实现栈（力扣225）
• 三、有效的括号（力扣20）
• 四、 删除字符串中的所有相邻重复项（力扣1047）
• 五、逆波兰表达式求值（力扣150）
• 六、滑动窗口最大值（力扣239）
• 七、前 K 个高频元素（力扣347）

  一、用栈实现队列（力扣232）

  请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

  实现 MyQueue 类：

  void push(int x) 将元素 x 推到队列的末尾

  int pop() 从队列的开头移除并返回元素

  int peek() 返回队列开头的元素

  boolean empty() 如果队列为空，返回 true ；否则，返回 false

  说明：

  你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

  示例 1：

  输入：

  [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]

  [[], [1], [2], [], [], []]

  输出：

  [null, null, null, 1, 1, false]

  解释：

  MyQueue myQueue = new MyQueue();

  myQueue.push(1); // queue is: [1]

  myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

  myQueue.peek(); // return 1

  myQueue.pop(); // return 1, queue is [2]

  myQueue.empty(); // return false

  class MyQueue {public:    MyQueue() {    }    // 两个栈配合实现队列    stack s1;    stack s2;    void push(int x) {        s1.push(x);        updateS2(s1,s2);    }        int pop() {        int result =s2.top();        s2.pop();        updateS1(s1,s2);        return result;    }        int peek() {        return s2.top();    }        bool empty() {        if(s2.size()==0){            return true;        }        return false;    }    // 更新s2    void updateS2(stack s1,stack &s2){        // 先将s2清空，再将s1中所有元素添加到s2中        int s2Size = s2.size();        for(int i=0;i            s2.pop();        }        // 将s1中所有元素添加到s2中        int s1Size = s1.size();        for(int i=0;i            int temp = s1.top();            s2.push(temp);            s1.pop();        }    }    void updateS1(stack        // 先将s1清空，再将s2中所有元素添加到s1中        int s1Size = s1.size();        for(int i=0;i            s1.pop();        }        // 将s1中所有元素添加到s2中        int s2Size = s2.size();        for(int i=0;i            int temp = s2.top();            s1.push(temp);            s2.pop();        }    }};/** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj = new MyQueue(); * obj-push(x); * int param_2 = obj-pop(); * int param_3 = obj-peek(); * bool param_4 = obj-empty(); */

  二、用队列实现栈（力扣225）

  请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

  实现 MyStack 类：

  void push(int x) 将元素 x 压入栈顶。

  int pop() 移除并返回栈顶元素。

  int top() 返回栈顶元素。

  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

  注意：你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

  你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

  示例：

  输入：

  [“MyStack”, “push”, “push”, “top”, “pop”, “empty”]

  [[], [1], [2], [], [], []]

  输出：

  [null, null, null, 2, 2, false]

  解释：

  MyStack myStack = new MyStack();

  myStack.push(1);

  myStack.push(2);

  myStack.top(); // 返回 2

  myStack.pop(); // 返回 2

  myStack.empty(); // 返回 False

  class MyStack {public:    MyStack() {    }    // 使用一个队列完成    queue q;    void push(int x) {        q.push(x);    }        int pop() {        // 将前面的重新添加到队列尾端        int qSize = q.size()-1;        for(int i=0;i            q.push(q.front());            q.pop();        }        int result = q.front();        q.pop();        return result;    }        int top() {        return q.back();    }        bool empty() {        if(q.size()==0){            return true;        }        return false;    }};/** * Your MyStack object will be instantiated and called as such: * MyStack* obj = new MyStack(); * obj-push(x); * int param_2 = obj->pop(); * int param_3 = obj->top(); * bool param_4 = obj->empty(); */

  三、有效的括号（力扣20）

  给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

  有效字符串需满足：

  左括号必须用相同类型的右括号闭合。

  左括号必须以正确的顺序闭合。

  每个右括号都有一个对应的相同类型的左括号。

  示例 1：

  输入：s = “()”

  输出：true

  示例 2：

  输入：s = “()[]{}”

  输出：true

  示例 3：

  输入：s = “(]”

  输出：false

  提示：

  1 public: bool isValid(string s) { if(s.length()%2!=0) return false; stack if(s[i]=='(') st.push(')'); else if(s[i]=='[') st.push(']'); else if(s[i]=='{') st.push('}'); else if(st.empty()||s[i]!=st.top()) return false; else st.pop(); } return st.empty(); }};public: string removeDuplicates(string s) { // 使用栈 stack if(st.empty()||st.top()!=s[i]){ st.push(s[i]); } else{ st.pop(); } } if(st.empty()) return ""; string result; while(!st.empty()){ result+= st.top(); st.pop(); } reverse(result.begin(),result.end()); return result; }};