🔥 栈和队列

概念

• 栈：先进后出
• 队列：先进先出

从Carl哥的代码随想录笔记中make下的一些概念
栈与队列的概念
抛出的问题：

1. C++中stack 是容器么？
2. 我们使用的stack是属于那个版本的STL？
3. 我们使用的STL中stack是如何实现的？
4. stack 提供迭代器来遍历stack空间么？

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的低层结构。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现，初始化queue的语句如下：

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

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

我这里讲的都是C++ 语言中情况， 使用其他语言的同学也要思考栈与队列的底层实现问题， 不要对数据结构的使用浅尝辄止，而要深挖起内部原理，才能夯实基础。

剑指 Offer 09. 用两个栈实现队列

弹出栈的部分，简单的画个图 模拟一下栈。

栈的进出，只有当栈为空return-1

class CQueue {public:    CQueue() {    } void appendTail(int value) { s1.push(value);    } int deleteHead() { if(s1.empty()) return -1; while(s1.size() > 1){     s2.push(s1.top());     s1.pop(); } int val = s1.top(); s1.pop(); while(!s2.empty()){     s1.push(s2.top());     s2.pop(); } return val;    }private:    stack<int> s1;    stack<int> s2;};

剑指 Offer 30. 包含min函数的栈

需要借助辅助栈

最小栈保存的最小元素可以重复添加

class MinStack {public:    /** initialize your data structure here. */    MinStack() { s1_min.push(INT_MAX);    } void push(int x) { s1.push(x); // 对于非最小的 重复压入一个最小 if(x > s1_min.top()){     x =  s1_min.top(); } s1_min.push(x);    } void pop() { s1.pop(); s1_min.pop();    } int top() { return s1.top();    } int min() { return s1_min.top();    }private:    stack<int> s1;    stack<int> s1_min;};

栈的压入、弹出序列

class Solution {public:    bool IsPopOrder(vector<int> pushV,vector<int> popV) { // 定义一个栈 当栈顶的元素和序列的元素相等则弹出 stack<int> s1; int j=0; for(int i=0; i<pushV.size(); ++i){     s1.push(pushV[i]);     while(!s1.empty() &&s1.top() == popV[j]){  s1.pop();  j++;     } } if(s1.size() == 0)     return true; return false;    }};

翻转字符串之翻转单词顺序

《剑指offer》 第58.1题 翻转字符串之翻转单词顺序

class Solution {public:    string ReverseSentence(string str) { stack<char> temp; string res =""; for(int i = str.length() - 1; i>=0; i--){     if(str[i]!= ' ')  temp.push(str[i]);     else{  // 如果栈非空，则将其全部的元素赋值给res  while(!temp.empty()){      res.push_back(temp.top());      temp.pop();  }  res.push_back(' ');     } } while(!temp.empty()){     //循环结束时，将栈中的元素赋值给字符串     res.push_back(temp.top());     temp.pop(); } return res;    }};

其實這道題的实现思路用下面的字符串的方法更加清晰。

用字符串的方法做：

class Solution {public:    string ReverseSentence(string str) { // 字符串的方法可以完成 string res = ""; string tmp = ""; // 定义一个临时字符串存储单词词组 for(unsigned int i = 0; i < str.size(); ++i){     if(str[i] == ' ') res = " " + tmp + res, tmp = "";     else tmp += str[i]; } if(tmp.size()) res = tmp + res; return res;    }};

剑指 Offer II 041. 滑动窗口的平均值

class MovingAverage {public:    /** Initialize your data structure here. */    MovingAverage(int size) { len = size;    } double next(int val) { que.push(val); sum += val; // 如果此时的队列长度大于窗口长度 弹出出口元素 if(que.size() > len){     sum -= que.front();     que.pop(); } return sum/que.size();    }private:    queue<double> que;    int len = 0;    double sum = 0;};/** * Your MovingAverage object will be instantiated and called as such: * MovingAverage* obj = new MovingAverage(size); * double param_1 = obj->next(val); */

单调栈 这部分的练习后面会继续补充一篇新的博客

滑动窗口的最大值

构建最小

class Solution {public:    vector<int> maxInWindows(const vector<int>& num, unsigned int size) { MyQueue que; vector<int> result; if(size == 0 || size > num.size())     return result; //先将前k个元素放进队列 for(int i = 0 ; i < size; i++){     que.push(num[i]); } // 记录前k的元素的最大值 result.push_back(que.front()); for(int i= size ; i < num.size(); ++i){     que.pop(num[i - size]);     que.push(num[i]);     result.push_back(que.front()); } return result;    }private:    //维护一个单调队列,从大到小    class MyQueue{    public: deque<int> que; // 只有当队列出口元素和value相等,才弹出 void pop(int value){     if(!que.empty() && value == que.front())  que.pop_front(); } // 如果value大于入口元素，则将队列后端的数字删除，压入这个数字 // 保持队列从大到小 void push(int value){     while(!que.empty() && value > que.back()){  que.pop_back();     }     que.push_back(value); }  int front(){     return que.front(); }    };};