1.栈
栈简单来说就是图1一样的东西,每一层放一个数据。添加数据后像图2一样。栈的特点为先进后出。就是先进去的后出来,后进去的先出来。经常用于前缀表达式计算和后缀表达式计算。
![](https://i-blog.csdnimg.cn/direct/0febcba8f3314df19aa0f652e3c09223.png)
![](https://i-blog.csdnimg.cn/direct/0bf83a2218094e8ba9a35093b7e3762e.png)
2.模拟栈
要模拟栈需要先在全局定义数组和函数:
int stack[1001]; // int数组模拟栈
int TOP = 0; // 栈顶指针初始化
如果想要是别的类型的栈,把数组的数据类型和push(int x)的参数改一下就好了。
1.1.入栈( push )
定义入栈( 即在栈顶添加元素 )函数:
void push(int x)
{
TOP++;
stack[TOP] = x;
}
1.2.出栈( pop )
定义出栈( 即删除栈顶元素 )函数:
void pop()
{
TOP--;
}
1.3.获取栈顶元素( top )
定义获取栈顶元素函数:
int top()
{
return st[TOP]; // 返回栈顶元素
}
3.直接使用栈( stack )
可以使用stack头文件直接调用函数,且功能更多。
3.1.导入头文件并创建栈
在代码最前面输入
#include <stack>
在main函数中输入stack <数据类型> 栈名;就能定义一个栈。
3.2.栈的操作
3.2.1.入栈( push )
入栈( 在栈顶添加元素 )函数为push()。有参函数。
push(x);
x为一个数据( 类型要和栈的类型一样 )。
3.2.2.出栈( pop )
出栈( 删除栈顶元素 )函数为pop()。无参函数。
pop();
3.2.3.获取栈顶元素( top )
获取栈顶元素函数为top()。无参函数。
top();
3.2.4.获取栈中元素个数( size )
获取栈中元素个数函数为size()。无参函数。
size();
3.2.5.判断栈是否为空( empty )
判断栈是否为空函数为empty()。无参函数。空返回1,不空返回0。
empty();
4.例
使用stack库进行后缀表达式运算。
#include <iostream> // 头文件
#include <stack>
#include <string>
#include <cmath>
using namespace std; // 命名空间
int main() // 主函数
{
stack<string> s; // 定义栈
string a; // 定义字符串
getline(cin, a); // 带空格输入
for (int i = a.length() - 1; i >= 0; i--)
{
int sum = 0, idx = 0;
while (a[i] >= '0' && a[i] <= '9')
{
// 多位数处理
sum = sum + (a[i] - '0') * pow(10, idx);
idx++;
i--;
}
if (sum != 0)
{
s.push(sum);
continue;
}
// 符号处理
int num1 = s.top();
s.pop();
int num2 = s.top();
s.pop();
if (a[i] == '+') // 加
{
s.push(num1 + num2);
}
else if (a[i] == '-') // 减
{
s.push(num1 - num2);
}
else if (a[i] == '*') // 乘
{
s.push(num1 * num2);
}
else if (a[i] == '/') // 除
{
if (num2 != 0)
{
s.push(num1 / num2);
}
else
{
s.push("wrong");
}
}
}
cout << s.top(); // 输出结果
return 0; // 结束程序
}