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的迭代器设计就比较复杂,如下图所示: