代码随想录学习记录——栈与队列篇

232、用栈实现队列

因为要求用两个栈来实现，而由于栈只能实现先进后出，那就一个栈完成输入功能，另一个实现输出功能，因此在放入的时候就按照顺序将元素放入输入栈中，然后当要输出的时候就判断输出栈中是否为空，如果不为空就输出顶端一个，如果为空就将当前输入栈中的元素不停拿出来放入输出栈中，这样的顺序也是正确的。

class MyQueue {
public:
    stack stIn;
    stack stOut;
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty()){
            //将stIn中的元素都放入out中
            while(stIn.empty() == false){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return( stIn.empty() && stOut.empty());
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

注意这里的peek()函数查看顶端元素，不用再去写一遍代码否则就要写逻辑判断输出栈是否为空，可以直接复用pop()的代码再塞回去就可以了。

225、用队列实现栈

这道题一开始也是想着用两个队列来跟上一道题类似的思路实现一个栈，但是发现由于栈和队列特性的不同，并无法做到这样的实现。

于是便参考了代码随想录的代码：

class MyStack {
public:
    queue que1;
    queue que2;
    MyStack() {

    }
    
    void push(int x) {
        QIn.push(x);
    }
    
    int pop() {
        int size = que1.size();
        size--;
        while(size--){
            que2.push(que1.front());
            que1.pop();
        }
        int result = que1.front();
        que1.pop();
        que1 = que2;
        while(!que2.empty()){
            que2.pop();
        }
        return result;
    }
    
    int top() {
        return que1.back();
    }
    
    bool 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();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

20、有效的括号

这道题的思路比较容易想到的就是：用一个栈和一个map来实现，map存放着正确的括号映射关系；然后逐渐查看字符串：

• 如果是左的括号，就将其压入栈中
• 如果是右的括号，就从栈中弹出顶部元素并在map中查看是否匹配，如果匹配则继续运行，如果不匹配就说明出错

因此根据上方的思路，只需要加上部分细节的处理即可：

class Solution {
public:
    bool isValid(string s) {
        unordered_map Map1{{'(',')'},{'[',']'},{'{','}'}};
        stack st1;
        for(char c : s){
            if(Map1.find(c) != Map1.end()){
                st1.push(c);//如果是左括号就压进去
            }
            else{
                if(!st1.empty()){
                    char temple1 = st1.top();
                    if(Map1[temple1] != c){
                        return false;//出现不匹配则返回错误
                    }
                    st1.pop();
                }else{//出现一个右括号可是栈为空则匹配不上
                    return false;
                }
                
            }
        }
        if(!st1.empty()){
            return false;//如果读完了还不为空说明数目不对等
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

这道题的思路也是比较清晰的，可以建立一个栈，然后不断读取字符串的字符，判断当前字符是否与顶部字符相同，如果相同则说明重复，那么就不做处理，相当于删除；如果不相同就压入栈中，是我们要保留的元素。完成之后再将栈中的元素读出，再做一次翻转即可：

class Solution {
public:
    string removeDuplicates(string s) {
        stack st;
        for( char c : s ){
            if(st.empty()){
                st.push(c);//如果当前字符为空那就
            }
            else{
                //不为空，就判断是否一样，如果不一样就压入，一样就 删除
                if( st.top() == c){
                    st.pop();
                }else{
                    st.push(c);
                }
            }
        }
        string result = "";
        while( !st.empty() ){
            result += st.top();
            st.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

150、逆波兰表达式求值

这道题就是后缀表达式的求解，还是很简单的。

如果遇到了数字那么就将其压入栈中，如果是运算符那么就弹出栈顶的两个元素并进行运算，再压入栈中即可。

class Solution {
public:
    int evalRPN(vector& tokens) {
        //这道题就是典型的后缀表达式
        stackst;
        for(int i = 0; i < tokens.size() ; i++){
            if( tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/" ){
                int num1 = st.top();
                st.pop();
                int 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] == "*" ){
                    long long temnum1 = num1;
                    long long temnum2 = num2;
                    long long temple = temnum1 * temnum2;
                    st.push(temple);
                }
            }else{
                //如果不是运算符，那么就是数字，就要将其压入堆栈
                st.push(stoi(tokens[i]));
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

但是要注意在进行相乘的时候可能会超过int的表示范围，即发生了溢出，那么就需要对int进行单独的处理，即用long long的类型来表示。

239、滑动窗口最大值

这道题难度也是不小，如果采用我们现有的数据结构（队列、栈等）很难能够较好地完成这道题目。那我们的目标是在每次滑动窗口的时候都用一个数据结构来存放当前窗口内的最大值，同时也随着窗口的移动，里面的元素一进一出。但虽然队列很容易实现一进一出的功能，但它并不能够完成排序的工作。因此我们需要写一个自己的队列，让它能够为我们完成排序的工作，然后每次查看当前窗口最大值的时候就输出顶部的元素即可。

但仔细想想，我们是否需要维护当前窗口中所有的值呢？假设我们当前的数据为[2,3,5,1,4]，k=3，那假设我们在第一个窗口[2,3,5]之中只储存5，而不储存2和3，当窗口移动的时候并不会影响到最大值的这个结果，因此2和3在5存在的情况下并不能作为最大值，那么移动到[5,1,4]，这个时候如果我们仍然只储存5，而不储存1和4，那当再次移动的时候（假设后面还有）是不是就5移动走了，我们就不知道最大值是多少了，因此这种情况就需要存储4这个数据。

这就给我们提供了思路，我们可以设计一个存入数据的时候很特殊的队列，其存入时流程如下：

• 如果当前队列为空，直接将元素放入
• 如果队列不为空，则需要判断大小关系，即按照从大到小的顺序，将元素插入到它正确的位置，同时比它小的元素都可以移出去了，这其中的原理是这些比它小的元素一定比当前元素先进入队列，那就肯定先出去（比如2之后插入3），那么比它小的元素出去的话也不会影响到最大值的结果（因为当前元素在的话最大值只可能是当前元素或者更大的元素），那么插入了3，就可以移除2了，不需要维持了，它不会对我们的最大值产生影响。

而这个队列在移除元素的时候，只有是当前元素等于队列最大的元素的时候，才需要进行移除。这样就实现了我们的要求。但我们这个要求最好的实现方式是能够有一个可以在两边进行插入的队列，因此我们选择deque双端队列。它所拥有的方法有：

• push_back()：在队列尾部添加元素，无返回值
• push_front()：在队列头部添加元素，无返回值
• pop_back()：删除队列尾部的元素，无返回值
• pop_front()：删除队列头部的元素，无返回值
• front() ：获得队列头部元素
• back()：获得队列尾部元素

因此具体的代码为：

class Solution {
private:
    class MyQueue{//设计我们想要的单调队列
    public:
        deque que;
        void pop(int value){//只有当前的元素等于顶部元素才可以弹出
            if ( !que.empty() && value == que.front()){
                que.pop_front();//移动窗口时要弹出的元素如果是最大值就弹出
            }
        }
        void push( int value){
            while(!que.empty() && value >que.back()){
                que.pop_back();//把队列尾部那些小的都不要
            }
            que.push_back(value);//插入合适的位置
        }    
        int front(){
            return que.front();
        }
    };
public:
    vector maxSlidingWindow(vector& nums, int k) {
        MyQueue que;
        vector result;
        for ( int i = 0; i < k ; i++ ){
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k ; i < nums.size() ; i++){
            que.pop(nums[i - k]);//移除元素
            que.push(nums[i]);//加入元素
            result.push_back(que.front());
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

347、前k个高频元素

这道题是要输出指定的前k个高频元素，这一开始肯定是想到可以用map来统计元素的个数，但问题是统计之后我们应该怎么选出前k个呢？那么这里要用的就是优先级队列，它其实本质是一个堆，只不过它必须从某一端取元素，从另一端加入元素，因此就可以认为具有队列的性质。而且这个优先级队列我们是可以设置按照元素的某种规律来进行排序的，它实际上使用二叉树的最大堆或者最小堆来完成排序的。那么下一个问题是我们要用最大堆来排序还是最小堆来排序呢？虽然这里要求是要前k个高频元素，但我们可以采用最小堆，只要在插入的时候保持元素的个数一直为k即可，那么具体的实现代码为：

class Solution {
public:
    class mycomparison{
        //用来比较的
    public:
        bool operator()(const pair & Ihs, const pair &rhs){
            return Ihs.second > rhs.second;
        }
    };
    vector topKFrequent(vector& nums, int k) {
        //先统计出现的频率
        unordered_mapmap;
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }
        //对频率进行排序，需要用到小顶堆
        priority_queue,vector>,mycomparison> pri_que;
        //不断加入，同时大于k就移除最小的
        for(unordered_map::iterator it = map.begin(); it != map.end(); it++){
            pri_que.push(*it);
            if( pri_que.size() > k){
                pri_que.pop();
            }
        }
        //用一个数组来存输出
        vectorresult(k);
        for(int i = k-1; i >= 0; i--){
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

需要补充一下这个优先级队列的用法， 其定义为：

priority_queue 变量名
1

• Type为参数的类型，例如在本题代码中我们参数类型为pair
• Container为容器类型，例如vector、queue等，不能为list，本次中我们参数类型为pair，因此容器类型为vectot>
• Functional为比较的方式，可以看到这里我们是把类的运算符()重写了，因此待回传进去比较的时候是Functional(paira,pairb)这样来调用的，因此重写这个括号运算符才能够满足需求