C++中的stack容器详解

C++中的stack容器详解

1.stack概述

stack是C++标准模板库(STL)中的容器适配器，它提供后进先出(LIFO)的数据结构功能。stack不是独立的容器，而是基于其他容器(如deque、list)实现的适配器。

2. 基本特性

• 后进先出(LIFO)：最后压入的元素最先弹出
• 容器适配器：基于其他序列容器实现
• 限制访问：只允许访问栈顶元素
• 高效操作：push和pop操作都是O(1)O(1)O(1)时间复杂度
• 默认实现：默认使用deque作为底层容器

3. 头文件与声明

#include<stack>usingnamespacestd;stack<int>s1;// 默认基于deque的整型栈stack<string,list<string>>s2;// 基于list的字符串栈stack<double>s3(s1);// 拷贝构造

4. 构造函数与初始化

4.1 默认构造

stack<int>nums;// 创建空栈

4.2 基于其他容器构造

deque<int>dq={1,2,3};stack<int>s(dq);// 使用deque初始化栈

4.3 指定底层容器类型

stack<string,vector<string>>words;// 使用vector作为底层容器

5. 容量操作

5.1empty()

if(s.empty()){cout<<"栈为空";}

5.2size()

cout<<"栈大小: "<<s.size();

6. 元素访问

6.1top()

if(!s.empty()){cout<<"栈顶元素: "<<s.top();}

7. 修改操作

7.1push()

s.push(10);// 压入元素到栈顶s.push(20);s.push(30);

7.2emplace()

s.emplace(40);// 在栈顶构造元素(避免拷贝)

7.3pop()

if(!s.empty()){s.pop();// 移除栈顶元素(不返回)}

7.4swap()(C++11)

stack<int>s2;s.swap(s2);// 交换两个栈的内容

8. 完整示例

#include<iostream>#include<stack>#include<vector>usingnamespacestd;intmain(){// 创建基于vector的栈stack<int,vector<int>>s;// 压入元素s.push(10);s.push(20);s.emplace(30);// 等同于push但效率更高// 查看栈信息cout<<"栈大小: "<<s.size()<<endl;cout<<"栈顶元素: "<<s.top()<<endl;// 弹出元素cout<<"\n弹出元素: ";while(!s.empty()){cout<<s.top()<<" ";s.pop();}cout<<endl;// 检查栈是否为空cout<<"栈是否为空: "<<(s.empty()?"是":"否")<<endl;// 使用其他容器初始化栈vector<int>v={1,2,3,4,5};stack<int,vector<int>>s2(v);cout<<"\n新栈内容: ";while(!s2.empty()){cout<<s2.top()<<" ";s2.pop();}cout<<endl;return0;}

9. 底层容器选择

stack可以基于以下几种容器实现：

1. deque(默认)：综合性能好，两端操作高效
2. list：在任何位置插入删除都高效，但内存不连续
3. vector：内存连续，但只在末尾操作高效

// 基于不同容器的栈声明stack<int>s1;// 默认基于dequestack<int,list<int>>s2;// 基于liststack<int,vector<int>>s3;// 基于vector

10. 实际应用示例

10.1 括号匹配检查

boolisBalanced(conststring&expr){stack<char>s;for(charc:expr){if(c=='('||c=='['||c=='{'){s.push(c);}else{if(s.empty())returnfalse;chartop=s.top();s.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')||(c=='}'&&top!='{')){returnfalse;}}}returns.empty();}

10.2 表达式求值(后缀表达式)

intevaluatePostfix(conststring&exp){stack<int>s;for(charc:exp){if(isdigit(c)){s.push(c-'0');}else{intval1=s.top();s.pop();intval2=s.top();s.pop();switch(c){case'+':s.push(val2+val1);break;case'-':s.push(val2-val1);break;case'*':s.push(val2*val1);break;case'/':s.push(val2/val1);break;}}}returns.top();}

11. 性能考虑

1. 时间复杂度：

   • push():O(1)O(1)O(1)
   • pop():O(1)O(1)O(1)
   • top():O(1)O(1)O(1)
   • empty():O(1)O(1)O(1)
   • size():O(1)O(1)O(1)(某些实现可能是O(n)O(n)O(n))

2. 空间复杂度：取决于底层容器实现

3. 底层容器选择影响：

   • vector可能导致内存重新分配
   • list有额外指针开销
   • deque通常是平衡的选择

12. 注意事项

1. 调用top()或pop()前必须检查栈是否为空
2. stack不提供迭代器，无法遍历栈内元素
3. 不同底层容器实现的stack可能有细微的性能差异
4. C++11开始支持emplace()和swap()操作

13.stack与其他容器比较