重拾C++之菜鸟刷算法第6篇—栈与队列

栈与队列

一、用栈实现队列

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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(双端队列)来模拟一个栈,只要是标准的栈操作即可。

232. 用栈实现队列 - 力扣(LeetCode)

题解

class MyQueue {
public:
    stack<int> inPut;
    stack<int> outPut;

    MyQueue() {

    }
    
    void push(int x) {
        inPut.push(x);
    }
    
    int pop() {
        if(outPut.empty()){
            while(!inPut.empty()){
                int tmp = inPut.top();
                outPut.push(tmp);
                inPut.pop();
            }
        }
        int result = outPut.top();
        outPut.pop();
        return result;
    }
    
    int peek() {
        int tmp = this->pop();
        outPut.push(tmp);
        return tmp;
    }
    
    bool empty() {
        if(inPut.empty() && outPut.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

二、用队列实现栈

题目

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

225. 用队列实现栈 - 力扣(LeetCode)

题解

class MyStack {
public:
    queue<int> numOut;
    queue<int> copyOut;

    MyStack() {

    }
    
    void push(int x) {
        numOut.push(x);
    }
    
    int pop() {
        int count = numOut.size();
        // 计算主的队列长度,注意留下最后一个元素
        while(--count){
            copyOut.push(numOut.front());
            numOut.pop();
        }
        // push出最后一个元素
        int result = numOut.front();
        numOut.pop();
        // 将备份的数据拿出来
        numOut = copyOut;
        // 清空备份区
        while(!copyOut.empty()){
            copyOut.pop();
        }
        return result;
    }
    
    int top() {
        return numOut.back();
    }
    
    bool empty() {
        return numOut.empty();
    }
};

三、有效的括号

题目

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

20. 有效的括号 - 力扣(LeetCode)

题解

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

简化版本

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

四、删除字符串中的所有相邻重复项

题目

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)

题解

class Solution {
public:
        string removeDuplicates(string s) {
        stack<char> result;
        for (int i = 0; i < s.size(); i++) {
            if (!result.empty() && s[i] == result.top()) {
                result.pop();
            }
            else{
                result.push(s[i]);
            }
        }
        string final;
        int length = result.size();
        for (int i = 0; i < length; i++) {
            final += result.top();
            result.pop();
        }

        for (int i = 0, j = final.size() - 1; i < j; i++, j--) {
            swap(final[i], final[j]);
        }
        return final;
    }
};

五、逆波兰表达式求值

知识点

  • stoll 将字符串转换为 long long int
  • 后缀表达式:遇到数字则入栈,遇到运算符则去除栈顶两个数字进行运算,并将结果压入栈中

题目

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*''/'
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

150. 逆波兰表达式求值 - 力扣(LeetCode)

题解

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据,需要用longlong
        stack<long long> st; 
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出(其实不弹出也没事)
        return result;
    }
};

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>