STL-stack/queue/deque（容器适配器）

 

目录

​编辑

STL-stack

150. 逆波兰表达式求值

stack

queue

std::stack

deque

性能测试

结构

---

STL-stack

栈的压入、弹出序列_牛客题霸_牛客网输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假。题目来自【牛客题霸】https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;int pushi=0,popi=0;while(pushi<pushV.size()){st.push(pushV[pushi]);pushi++;while(!st.empty()&&st.top()==popV[popi]){st.pop();popi++;}}return st.empty();}

双层while循环

150. 逆波兰表达式求值

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

 int evalRPN(vector<string>& tokens) {stack<int> st;for(auto str:tokens){if(str=="+"||str=="-"||str=="*"||str=="/"){int right=st.top();st.pop();int left=st.top();st.pop();switch(str[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;}}else{st.push(stoi(str));}}return st.top();}

stack

template<class T,class Container>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& top(){return _con.back();}
private:Container _con;
};

stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty())
{cout << st.top() << " ";st.pop();
}

queue

template<class T,class Container>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& front(){return _con.front();}T& back(){return _con.back();}
private:Container _con;
};

不能用vector，vector不支持头删（效率太低）。只能支持list

总结：

stl中的stack和queue是通过容器适配器转换出来的，不是原生实现的->提高代码的复用性。

class template

<stack>

std::stack

template <class T, class Container = deque<T> > class stack;

class Container = deque<T>双端队列。

deque

支持任意位置插入和随机访问。

性能测试

void test_deque()
{deque<int> d;vector<int> v;const int n = 10000;srand(time(0));for (size_t i = 0; i < n; ++i){int x = rand();d.push_back(x);v.push_back(x);}size_t begin1 = clock();sort(d.begin(), d.end());size_t end1 = clock();size_t begin2 = clock();sort(v.begin(), v.end());size_t end2 = clock();cout << end1 - begin1 << endl;cout << end2 - begin2 << endl;
}

结构

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维 数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落 在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：