C++ STL stack

1. stack 基本概念

stack 是一种后进先出(LIFO)的容器适配器，它是基于其他容器（默认是deque）实现的。

1.1 特点

  • 只能访问栈顶元素
  • 只能在栈顶进行插入和删除操作
  • 不支持随机访问
  • 不支持迭代器

2. 基本操作

2.1 声明和初始化

1
2
3
4
5
6
// 常见的初始化方式
stack<int> st;                     // 默认构造函数
stack<int, vector<int>> st2;       // 指定底层容器为vector
stack<int> st3(st);                // 拷贝构造函数
stack<int> st4(10, 2);             // 构造函数参数为初始容量和值
stack<list> st5(st);              // 不同类型元素的栈

2.2 常用成员函数(操作)

  • push(): 将元素压入栈顶
  • pop(): 弹出栈顶元素
  • top(): 访问栈顶元素
  • empty(): 判断栈是否为空
  • size(): 返回栈中元素个数
  • swap(): 交换两个栈的内容
  • emplace(): 构造元素并压入栈顶
  • clear(): 清空栈

3. 实际应用示例

3.1 栈的基本操作

1
2
3
4
5
6
7
8
stack<int> st;
st.push(1);              // 压入元素
st.push(2);
st.push(3);

cout << st.top() << endl;  // 访问栈顶元素
st.pop();                  // 弹出栈顶元素
cout << st.size() << endl; // 获取元素个数

3.2 常见应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 括号匹配检查
bool isMatch(string s) {
    stack<char> st;
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if(st.empty()) return false;
            if(c == ')' && st.top() != '(') return false;
            if(c == ']' && st.top() != '[') return false;
            if(c == '}' && st.top() != '{') return false;
            st.pop();
        }
    }
    return st.empty();
}

4. 注意事项

4.1 使用注意点

  1. 在空栈上调用pop()或top()会导致未定义行为
  2. stack不支持迭代器操作
  3. 不能直接访问除栈顶外的其他元素
  4. pop()函数不返回值

4.2 安全使用建议

1
2
3
4
5
6
stack<int> st;
// 安全的弹出操作
if (!st.empty()) {
    int top_element = st.top();  // 先获取栈顶元素
    st.pop();                    // 再弹出
}

5. 性能分析

  • 压入元素(push): O(1)
  • 弹出元素(pop): O(1)
  • 访问栈顶(top): O(1)
  • 检查大小(size): O(1)

6. 常见面试题

6.1 典型问题

  1. 括号匹配问题
  2. 表达式求值
  3. 函数调用栈
  4. 后缀表达式求值
  5. 单调栈应用

6.2 单调栈示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 找出数组中每个元素的下一个更大元素
#include <bits/stdc++.h>
using namespace std;

// 使用单调栈找出数组中每个元素的下一个更大元素
vector<int> nt(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);  // 初始化结果数组，默认值为-1
    stack<int> st;  // 存储元素下标的栈
    
    // 从左向右遍历数组
    for(int i = 0; i < n; i++) {
        // 当栈不为空，且当前元素大于栈顶元素所对应的数组值时
        while(!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];  // 更新结果
            st.pop();  // 弹出栈顶
        }
        st.push(i);  // 将当前下标入栈
    }
    return result;
}

int main() {
    vector<int> nums = {2, 1, 2, 4, 3};    // 简化测试用例
    
    cout << "输入数组：";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    vector<int> result = nt(nums);
    cout << "下一个更大元素：";
    for(int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

7.数组模拟stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针,初始栈内无元素，tt为-1

for(int i = 0; i <= 5; ++i) {
	//入栈 
	s[++tt] = i;
}
// 出栈
int top_element = s[tt--]; 

//入栈操作示意
//  0  1  2  3  4  5  
//                tt
//出栈后示意
//  0  1  2  3  4 
//              tt

8. 进阶主题

  • 栈的底层实现原理
  • 不同底层容器的性能对比
  • 栈在系统中的应用（如：函数调用栈）
  • 栈的内存模型

评论区仅供交流，有问题请 联系我 反馈。