C++中的stack容器操作大全_C/C++

1.stack概述

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

2. 基本特性

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

3. 头文件与声明

#include <stack>
using namespace std;
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>
using namespace std;
int main() {
    // 创建基于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;
    return 0;
}

9. 底层容器选择

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

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

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

10. 实际应用示例

10.1 括号匹配检查

bool isbalanced(const string& expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            if (s.empty()) return false;
            char top = s.top();
            s.pop();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return s.empty();
}

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

int evaluatepostfix(const string& exp) {
    stack<int> s;
    for (char c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int val1 = s.top(); s.pop();
            int val2 = 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;
            }
        }
    }
    return s.top();
}

11. 性能考虑

时间复杂度：
- 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))
空间复杂度：取决于底层容器实现
底层容器选择影响：
- vector可能导致内存重新分配
- list有额外指针开销
- deque通常是平衡的选择

12. 注意事项

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

13.stack与其他容器比较

特性	stack	vector	deque
访问方式	仅栈顶	随机访问	随机访问
插入/删除位置	仅顶端	主要末尾	两端
迭代器支持	不支持	支持	支持
内存布局	依赖底层容器	连续	分段连续

到此这篇关于c++中的stack容器操作大全的文章就介绍到这了,更多相关c++ stack容器内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

C++中的stack容器操作大全