【C++】stack

目录

• • 1. 简介：什么是 Stack？
  • 2. 核心接口与基本使用
  • • 使用示例
  • 3. 经典算法实战
  • • 3.1 最小栈 (Min Stack）
    • 3.2 栈的弹出压入序列
    • 3.3 逆波兰表达式求值 (后缀表达式)
  • 4. 为什么 Stack 默认使用 Deque？
  • 附录：Stack 的模拟实现 (封装)

1. 简介：什么是 Stack？

Stack（栈）是一种专门用在具有后进先出（LIFO）操作的上下文环境中的容器适配器，其删除与插入元素的提取操作只能从容器的一端（栈顶）进行。

需要明确的是，Stack 在 STL 中被归类为容器适配器，而非标准容器。所谓适配器模式，即是将一个特定类的接口转换成客户希望的另一个接口。Stack 封装了底层容器（如 deque、vector 或 list），通过提供一组特定的成员函数来限制元素的访问方式。

2. 核心接口与基本使用

标准容器 vector、deque、list 均符合 Stack 的底层需求（支持 empty、back、push_back、pop_back）。默认情况下，使用 deque 作为底层容器。

使用示例

#include <iostream>
#include <stack>
using namespace std;

void test_stack() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);

while (!s.empty()) {
cout << s.top() << " "; // 依次输出: 4 3 2 1
s.pop();
}
cout << endl;
}

3. 经典算法实战

Stack 的后进先出特性在算法中应用极其广泛，常用于括号匹配、逆序输出、单调栈等场景。以下列举几道高频算法题：

3.1 最小栈 (Min Stack）

最小栈 (Min Stack)

**思路：**设计两个栈，一个普通栈用于存取元素，一个辅助栈（_min）用于同步保存当前栈内的最小值。

class MinStack {
public:
void push(int x) {
_elem.push(x);
if(_min.empty() || x <= _min.top()) {
_min.push(x);
}
}
void pop() {
if(_min.top() == _elem.top()) {
_min.pop();
}
_elem.pop();
}
int top() { return _elem.top(); }
int getMin() { return _min.top(); }
private:
std::stack<int> _elem;
std::stack<int> _min;
};

3.2 栈的弹出压入序列

栈的弹出压入序列

**思路：**借用一个辅助栈，模拟入栈与出栈的过程。遍历入栈序列，将其压入辅助栈。每次压栈后，循环判断栈顶元素是否与出栈序列的当前元素匹配，若匹配则一直出栈。

class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
if (pushV.size() != popV.size()) return false;
int outIdx = 0, inIdx = 0;
stack<int> s;

while (outIdx < popV.size()) {
while (s.empty() || s.top() != popV[outIdx]) {
if (inIdx == pushV.size()) return false;
s.push(pushV[inIdx++]);
}
s.pop();
outIdx++;
}
return true;
}
};

3.3 逆波兰表达式求值 (后缀表达式)

逆波兰表达式求值 (后缀表达式)

**思路：**遇到数字则压栈，遇到操作符则连续弹出两个栈顶元素进行计算，将计算结果再重新压入栈中。最终栈内剩下的唯一元素即为结果。

class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (size_t i = 0; i < tokens.size(); ++i) {
string& str = tokens[i];
if (!(str == "+" || str == "-" || str == "*" || str == "/")) {
s.push(atoi(str.c_str()));
} else {
int right = s.top(); s.pop();
int left = s.top(); s.pop();
switch (str[0]) {
case '+': s.push(left + right); break;
case '-': s.push(left – right); break;
case '*': s.push(left * right); break;
case '/': s.push(left / right); break;
}
}
}
return s.top();
};

4. 为什么 Stack 默认使用 Deque？

虽然 vector 和 list 都能用来实现栈，但 STL 中 stack 默认选择了 deque（双端队列）作为底层容器。

什么是 Deque？ Deque 是一种双开口的“连续”空间的数据结构，可以在头尾两端进行插入和删除，时间复杂度为 O(1)。它并非真正的连续空间，而是由一段段连续的小空间拼接而成（动态二维数组），依靠复杂的中控器和迭代器维护“整体连续”的假象。

默认选择 Deque 的原因：

• 规避缺点： deque 的致命缺陷是不适合遍历（迭代器频繁跨越边界导致效率极低）。但 stack 不需要遍历，完美避开了此缺陷。
• 放大优点： stack 只需要在一端进行固定操作。在元素增长扩容时，deque 不需要像 vector 那样搬移大量数据，效率更高；同时，相比于 list，deque 的空间利用率也更高，不需要存储额外的指针字段。

附录：Stack 的模拟实现 (封装)

利用容器适配器的理念，我们可以使用泛型编程思想，提供一个模板参数 Container，让用户可以自由选择底层使用的容器（默认为 vector 或 deque）。以下是代码实现：

#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>

namespace bit
{
// 模板参数：T是元素类型，Container是底层容器，默认采用 vector
template<class T, class Container = std::vector<T>>
class stack
{
public:
// 压栈：调用底层容器的 push_back
void push(const T& x)
{
_con.push_back(x);
}

// 出栈：调用底层容器的 pop_back
void pop()
{
_con.pop_back();
}

// 取栈顶：返回底层容器的尾部元素
const T& top()
{
return _con.back();
}

// 判空
bool empty()
{
return _con.empty();
}

// 获取大小
size_t size()
{
return _con.size();
}

private:
Container _con; // 底层容器对象
};
}

// 测试函数
void test_stack()
{
// 测试：显式指定底层容器
// bit::stack<int, std::list<int>> s;

// 测试：使用默认容器
bit::stack<int> s;

s.push(1);
s.push(2);
s.push(3);
s.push(4);

while (!s.empty())
{
std::cout << s.top() << " ";
s.pop();
}
std::cout << std::endl;
}