代码随想录1刷—栈和队列篇

基础理论

• 队列是先进先出，栈是先进后出。

栈和队列是STL（C++标准库）里面的两个数据结构。C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。三个最为普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

栈

• 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。**栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。**所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

• 栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。**我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的低层结构。**deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

• **SGI STL中 队列底层实现缺省情况下一样使用deque实现的。**我们也可以指定vector为栈的底层实现，初始化语句如下：

std::stack<int, std::vector<int> > third;  	// 使用vector为底层容器的栈
1

队列

• 类比栈的情况，队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器，**SGI STL中队列一样是以deque为缺省情况下的底部结构。所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。**也可以指定list 为起底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third; 		// 定义以list为底层容器的队列
1

232. 用栈实现队列

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 result = stackout.top();
        stackout.pop();
        return result;
    }
    
    int peek() {
        int ans = this->pop();
        stackout.push(ans);
        return ans;
    }
    
    bool empty() {
        if(stackin.empty() && stackout.empty()) return true;
        else return false;
    }
};
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

225. 用队列实现栈

两个队列的方案

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

    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        int size = queue1.size()-1;
        while(size--){
            queue2.push(queue1.front());//注意：queue的pop是弹出删除没返回值，queue的front是得到第一个元素，得到了要删再删~
            queue1.pop();
        }
        int result = queue1.front();
        queue1.pop();
        queue1 = queue2;            // 再将que2赋值给que1
        while (!queue2.empty()) {   // 清空que2
            queue2.pop();
        }
        return result;
    }
    
    int top() {
        return queue1.back();
    }
    
    bool empty() {
        return queue1.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

一个队列的方案

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

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

    }
    
    void push(int x) {
        queue.push(x);
    }
    
    int pop() {
        int size = queue.size() - 1;
        while(size--){  				//全部添加到队尾 再弹出
            queue.push(queue.front());
            queue.pop();
        }
        int result = queue.front();   	//此时弹出的元素顺序就是栈的顺序了
        queue.pop();
        return result;
    }
    
    int top() {
        return queue.back();
    }
    
    bool empty() {
        return queue.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

20. 有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<int> stack;
        for(int i = 0; i < s.size();i++){
            if (s[i] == '(') stack.push(')');
            else if (s[i] == '{') stack.push('}');
            else if (s[i] == '[') stack.push(']');
            else if (stack.empty() || stack.top() != s[i]) return false;
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else stack.pop(); // stack.top() 与 s[i]相等，栈弹出元素
        }
        return stack.empty();
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以在对字符串进行反转一下，就得到了最终的结果。也是栈的思想，但直接拿字符串作为栈，这样可以省去栈转为字符串然后还要翻转的操作。案代码如下：

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(!result.empty() && result.back() == s) {
                result.pop_back();
            }
            else {
                result.push_back(s);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

150. 逆波兰表达式求值

逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

逆波兰表达式相当于二叉树中的后序遍历。 可以把运算符作为中间节点，然后按照后序遍历的规则画出一个二叉树。但是，没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化就可以了。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        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] == "/") st.push(num2 / num1);
            } 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

239. 滑动窗口最大值

单调队列

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

class Solution {
public:
    class MyQueue{          //单调队列（从大到小）
        public:     
        deque<int> que;     // 使用deque来实现单调队列
        void pop(int value){
            if(!que.empty() && value == que.front()){
                que.pop_front();
            }
        } // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
          // 同时pop之前判断队列当前是否为空。
          
        void push(int value){
            while(!que.empty() && value > que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
         // 这样就保持了队列里的数值是单调从大到小的了。

        int front(){
            return que.front();
        } // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    };

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for(int i = 0;i < k;i++){   // 先将前k的元素放进队列
            que.push(nums[i]);
        }          
        result.push_back(que.front());// result 记录前k的元素的最大值
        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
37
38
39
40

347. 前 K 个高频元素（太晕了！！要看很多次！！）

优先级队列

C++中，使用优先级队列需要包含头文件<queue>，优先级队列的定义如下：

priority_queue<typename, container, functional>
typename是数据的类型；container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的**less和greater**这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。

定义一个优先级队列的示例如下：

//构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
priority_queue<int, vector<int>, less<int>> priQueMaxFirst;

//构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue<int, vector<int>, greater<int>> priQueMinFirst;

//默认大顶堆
priority_queue<int> priQueFirst;

自定义比较方式

• 当数据类型并不是基本数据类型，而是自定义的数据类型时，就不能用greater或less的比较方式了，而是需要自定义比较方式，有两种自定义比较方式的方法：

  • 运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。如下：

  • 若希望水果价格高为优先级高，则重载小于“<”运算符

    //大顶堆
    struct fruit
    {
    	string name;
    	int price;
    	friend bool operator < (fruit f1,fruit f2)
    	{
    		return f1.peice < f2.price;
    	}
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    若希望水果价格低为优先级高，则重载大于“>”运算符

    //小顶堆
    struct fruit
    {
    	string name;
    	int price;
    	friend bool operator < (fruit f1,fruit f2)
    	{
    		return f1.peice > f2.price;  //此处是 >
    	}
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

  • 仿函数

    //大顶堆
    struct myComparison
    {
    	bool operator () (fruit f1,fruit f2)
    	{
    		return f1.price < f2.price;
    	}
    };
    
    //此时优先队列的定义应该如下
    priority_queue<fruit,vector<fruit>,myComparison> q;
    
    //小顶堆改为"return f1.price > f2.price;"即可
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

题目分析

具体操作为：

1、借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
2、维护一个元素数目为 k 的最小堆
3、每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
4、如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
5、最终，堆中的 k 个元素即为前 k 个高频元素

class Solution {
public:
    // 小顶堆 采用自定义比较方式（仿函数）
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            //注意 it为iterator迭代器类型，迭代器相当于一个指针，所以：
            //可使用解引用操作符（*操作符）来访问迭代器所指向的元素，如*iter = 0;
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(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
34
35
36
37
38
39

复杂度分析

题外话：排序总结表格

• in-place 占用常数内存，不占用额外内存
• out-place 占用额外内存

栈里面的元素在内存中是连续分布的么？

• 栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不是连续分布。

• 缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？

  答案是：不连续的。

递归和栈

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。所以栈与递归之间在某种程度上是可以转换的！

相信大家应该遇到过一种错误就是栈溢出，系统输出的异常是Segmentation fault（当然不是所有的Segmentation fault 都是栈溢出导致的） ，如果你使用了递归，就要想一想是不是无限递归了，那么系统调用栈就会溢出。而且 在企业项目开发中，尽量不要使用递归！ 在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）