栈
栈是一个带有限制的表，它的插入和删除都只能在一个位置上进行，即只能在表的末端进行，这个末端叫栈顶（top）
栈模型
栈也叫LIFO（后进先出）表。正如其名，栈的特点就是在最后入栈的元素反而最早出栈。对于栈，我们基本上就只有两种操作，一种是进栈（push），一种是出栈（pop），前者就是插入元素，后者就是删除栈顶的元素。对于一个栈，我们能操作的只有栈顶。
如上图所示，目前只能操作"5"这个元素，要么在它后面push，要么把它pop。
栈的实现
栈只是一个ADT，具体实现还是要靠实现表的方法。其中list和vector都可以实现它
list实现栈
使用单链表就可以实现栈的操作，我们可以通过在表的前端插入来实现push操作，通过删除表前端元素来实现pop操作。
#include <iostream>
#include <list>
// 自定义栈类
class MyStack {
private:
std::list<int> data; // 使用list来存储栈元素
public:
// 入栈操作
void push(int value) {
data.push_back(value);
}
// 出栈操作
void pop() {
if (!empty()) {
data.pop_back();
}
}
// 获取栈顶元素
int top() {
if (!empty()) {
return data.back();
}
// 这里可以根据实际需求抛出异常或返回一个特定值表示栈为空
return -1;
}
// 判断栈是否为空
bool empty() {
return data.empty();
}
};
int main() {
MyStack stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "栈顶元素: " << stack.top() << std::endl;
stack.pop();
std::cout << "出栈后栈顶元素: " << stack.top() << std::endl;
return 0;
}
上述代码自定义了一个MyStack栈结构，内部使用的是list数据类型来存储栈中的元素。定义了四种操作，分别是入栈，出栈，获取栈顶元素，判断是否为空栈。下面的main函数中对上面定义的结构进行了测试。
vector实现栈
用vector实现栈很明显是一个更明智的操作，因为我们在前面讲到过，list用链表存储元素的缺点就是随机读取性能很弱，而vector采用在内存中连续存储的方式，而且自带的push_back和pop_back方法，实现栈来说更简单。
#include <iostream>
#include <vector>
class Stack {
private:
std::vector<int> data; // 使用vector存储栈元素
public:
// 入栈操作
void push(int value) {
data.push_back(value);
}
// 出栈操作
void pop() {
if (!empty()) {
data.pop_back();
}
}
// 获取栈顶元素
int top() {
if (!empty()) {
return data.back();
}
// 可根据实际情况处理栈为空的情况，这里简单返回-1
return -1;
}
// 判断栈是否为空
bool empty() {
return data.empty();
}
};
int main() {
Stack stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "栈顶元素: " << stack.top() << std::endl;
stack.pop();
std::cout << "出栈后栈顶元素: " << stack.top() << std::endl;
return 0;
}
同样也是实现四个基本功能，入栈、出栈、获取栈顶元素和判断是否为空。
栈的应用
下面用一个题目来讲解一下栈的应用（洛谷-P1981）
这个题目要求输入一个计算式，只包含数字和"＋""*"两种符号，最后输出结果。
这道题毫无疑问得用栈的知识，先把输入的数字压入栈，然后根据它后面的符号再对栈顶进行对应的操作，如果是"*"号，就对栈顶和输入的数字做相乘处理，再把结果压入栈，如果是"+"号就直接压入栈，最后栈中的数字全都是相加处理，直接全部相加得到结果。
分析输入，我们可以发现除掉第一个数字，后面的形式全部都是一个符号加一个数字，那么我们可以选择先将第一个数字压入栈，再循环输入后面的内容，进行对应的操作
cin >> first_num;
first_num %= 10000;
stk.push_back(first_num);
while (cin >> sig >> num) {
if (sig == '*') {
first_num = stk.back() * (num % 10000) % 10000;
stk.pop_back();
stk.push_back(first_num);
}
else if (sig == '+') {
stk.push_back(num % 10000);
}
}
接着就是把栈中的所有数字依次出栈相加得到结果了，循环判断条件就是数组不是空时。
int sum = 0;
while (!stk.empty()) {
sum += stk.back();
sum %= 10000;
stk.pop_back();
}
cout << sum << endl;
完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
vector<int> stk;
int main() {
int first_num, num;
char sig;
cin >> first_num;
first_num %= 10000;
stk.push_back(first_num);
while (cin >> sig >> num) {
if (sig == '*') {
first_num = stk.back() * (num % 10000) % 10000;
stk.pop_back();
stk.push_back(first_num);
}
else if (sig == '+') {
stk.push_back(num % 10000);
}
}
int sum = 0;
while (!stk.empty()) {
sum += stk.back();
sum %= 10000;
stk.pop_back();
}
cout << sum << endl;
return 0;
}
那么以上是我们用vector模拟栈，其实c++中的STL库中有栈（stack）这个数据结构，我们可以像引用vector一样直接导入引用它，下面我们一起来看看如何导入并引用栈吧
STL中的stack栈
以下是C++ STL库中栈（stack）的常见用法：
- 包含头文件 首先需要包含
stack头文件：
#include <stack>
- 创建栈对象 可以创建一个存储特定类型元素的栈，例如存储
int类型元素的栈：
std::stack<int> myStack;
- 基本操作
- 入栈（push）：将元素添加到栈顶。
myStack.push(10);
myStack.push(20);
- 出栈（pop）：移除栈顶元素。
myStack.pop();
- 获取栈顶元素（top）：获取栈顶元素的值，但不移除它。
int topElement = myStack.top();
- 判断栈是否为空（empty）：检查栈是否为空，返回
true表示空，false表示非空。
if (myStack.empty()) {
std::cout << "栈为空" << std::endl; }
else {
std::cout << "栈不为空" << std::endl; }
- 获取栈的大小（size）：返回栈中元素的数量。
std::cout << "栈的大小为：" << myStack.size() << std::endl;
以下是一个完整的示例，演示了栈的基本操作：
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(5);
myStack.push(15);
myStack.push(25);
std::cout << "栈顶元素：" << myStack.top() << std::endl;
myStack.pop();
std::cout << "出栈后栈顶元素：" << myStack.top() << std::endl;
std::cout << "栈是否为空：" << (myStack.empty()? "是" : "否") << std::endl;
std::cout << "栈的大小：" << myStack.size() << std::endl;
return 0;
}
感兴趣的话可以试着用stack做一下上面的那个题目。