「代码随想录算法训练营」第九天 | 栈与队列 part1

232. 用栈实现队列

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/
题目难度:简单
文章讲解:https://programmercarl.com/0232.用栈实现队列.html
视频讲解:https://www.bilibili.com/video/BV1nY4y1w7VC
题目状态:看视频讲解后通过

思路:
通过两个栈来实现队列。

  • 创建两个栈stackInstackOut
  • 当入队的时候,直接把元素入stackIn栈中即可;
  • 当出队的时候,若stackOut中没有元素时,先将stackIn中的元素入stackOut中,再从stackOut中出栈;
  • 当返回队头时,直接调用出队的代码即可;
  • 当判断是否为空队的时候,只需要判断两个栈是否都为空即可。

代码实现:

class MyQueue {
public:
    stack<int> stackIn;
    stack<int> stackOut;
    MyQueue() {

    }
    
    void push(int x) {
        stackIn.push(x);
    }
    
    int pop() {
        if(stackOut.empty()) {
            while(!stackIn.empty()) {
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
        int res = stackOut.top();
        stackOut.pop();
        return res;
    }
    
    int peek() {
        int res = this->pop();
        stackOut.push(res);
        return res;
    }
    
    bool empty() {
        return stackIn.empty() && stackOut.empty();
    }
};

/**
 * 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. 用队列实现栈

题目链接:https://leetcode.cn/problems/implement-stack-using-queues/
题目难度:简单
文章讲解:https://programmercarl.com/0225.用队列实现栈.html
视频讲解:https://www.bilibili.com/video/BV1Fd4y1K7sm
题目状态:看代码随想录思路后通过

思路一(两个队列):

  • 创建两个队列,一个是用来各种操作的队列que1,一个用来存储元素的辅助队列que2
  • 入栈:将元素压入que1中即可;
  • 出栈:将que1中除了最后一个元素以外的其他元素压入que2中,并将que1中的最后一个元素输出,最后将que2中的元素再返给que1并清空que2
  • 输出栈头:返回que1的队尾;
  • 判断栈是否为空:返回que1队列是否为空。

代码实现:

class MyStack {
public:
    queue<int> que1;
    queue<int> que2;
    MyStack() {

    }
    
    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size = que1.size();
        size--;
        while(size--) {
            que2.push(que1.front());
            que1.pop();
        }
        int res = que1.front();
        que1.pop();
        que1 = que2;
        while(!que2.empty()) {
            que2.pop();
        }
        return res;
    }
    
    int top() {
        return que1.back();
    }
    
    bool empty() {
        return que1.empty();
    }
};

/**
 * 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();
 */

思路二(一个队列)

  • 创建一个队列que
  • 入栈:将元素压入que中即可;
  • 出栈:将que中除了最后一个元素以外的其他元素重新压入que中,并将que刚开始的最后一个元素(现在是第一个元素)弹出;
  • 输出栈头:返回que的队尾;
  • 判断栈是否为空:返回que队列是否为空。

代码实现:

class MyStack {
public:
    queue<int> que;
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        size--;
        while(size--) {
            que.push(que.front());
            que.pop();
        }
        int res = que.front();
        que.pop();
        return res;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

/**
 * 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. 有效的括号

题目链接:https://leetcode.cn/problems/valid-parentheses/
题目难度:简单
文章讲解:https://programmercarl.com/0020.有效的括号.html
视频讲解:https://www.bilibili.com/video/BV1AF411w78g
题目状态:看代码随想录思路后通过

思路:

  • 若字符串中元素的个数为奇数,说明括号肯定不匹配,直接返回false
  • 创建一个栈;
  • 如果遍历的元素是括号的左半部分,将对应的右半部分压入到栈中;
  • 如果遍历到的元素是括号的右半部分,则判断栈中的元素是否和该括号对应,若不对应,说明两个括号无法匹配,则返回false
  • 若栈中元素和遍历到的元素匹配且最终栈为空,则返回true

代码实现:

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

1047. 删除字符串中的所有相邻重复项

题目链接:https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
题目难度:简单
文章讲解:https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html
视频讲解:https://www.bilibili.com/video/BV12a411P7mw
题目状态:通过

个人思路:

  • 创建一个栈来存放字符串中的元素;
  • 遍历字符串;
  • 若栈不为空且遍历到的字符串中的元素等于栈中的元素,将栈中元素弹出;
  • 相反,若遍历到的元素不等于栈中的元素,则将元素压入栈中;
  • 遍历完成后,将栈中的元素依次弹出,并存储在一个string类型的变量res中;
  • 反转res并返回。

代码实现:

class Solution {
public:
    string removeDuplicates(string s) {
        int size = s.size();
        stack<char> st;
        for(auto &sElem : s) {
            if(!st.empty() && sElem == st.top()) st.pop();
            else st.push(sElem);
        }
        string res;
        while(!st.empty()) {
            res += st.top();
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

热门相关:司令,以权谋妻   完美隐婚   特工皇后不好惹   大师救命   大数据修仙