栈(stack)
栈是一种运算受限的线性表。限定仅在表尾进行插入和删除的操作。
插入(push), 弹出(pop)。其特性就是先进后出,即先插入的元素最后才能弹出。大家可以把栈想象成一个弹夹,你只能在顶层一颗一颗装入子弹,先装的子弹在最底层,打出时也只能从上层一颗一颗打出。最后装入的一颗子弹最先打出。这便是先进后出的意思。在栈中,“弹夹”的最上层被叫做栈顶,一般用top来指示栈顶的位置。
我们可以先通过结构体自己定义一个栈,便于理解。
#include<iostream>
using namespace std;
struct Stack {
int data[10000];
int top = -1;
void push(int x) {//push函数定义
top++;
if (top < 10000) {
data[top] = x;
}
else {
top--;
cout << "stack overflow" << endl;
}
}
void pop() {//pop函数定义
if (top >= 0) {
top--;
}
}
int topval() {
if (top >= 0) {
return data[top];
}
}
};
int main()
{
Stack s;
for (int i =1; i <= 10; i++) {
s.push(i);
}
for (int i = 1; i <= 10; i++) {
cout << s.topval() << " ";
s.pop();
}
return 0;
}
定义完成后,我们给栈从1-10赋值,并进行输出,可以看到输出的结果为10-1的顺序。
这也再一次印证了其先进后出的特性。
STL中也有栈,且更加方便使用,使用前记得加上#include<stack>
头文件
创建一个栈的语法为stack<T> s
T 表示数据类型如int,char,float等等。
栈的基本操作
判断是否为空栈
使用empty()函数来判断栈是否为空
bool empty()如果栈为空返回true,否则返回false。
入栈
使用push()函数来完成入栈操作
例如:前面将1-10入栈的例子
stack<int> s;//创建一个栈
for(int i=1;i<=10;i++){
s.push(i);
}
出栈
使用pop()函数来完成出栈的操作
移除栈中最顶层元素
返回栈顶元素
使用top()函数返回栈顶元素
例如:上面输出逆序输出1-10的例子
for (int i = 1; i <= 10; i++) {
cout << s.top() << " ";
s.pop();
}
注意:要先取top(),再用pop()弹出栈顶元素
返回栈中元素数目
size()函数返回栈中的元素个数。
以上就是STL中栈的基本操作。
来一道例题熟悉一下这些操作。
题目:
火车出入站问题,火车按照1-n对应编号,输出n,接下来输入可能的出站顺序,写一个程序判断这种出站顺序是否合法,合法输出legal,反之输出illegal。
思路:类似于詹天佑发明的人字型铁路。
画图示意一下
好了画图模拟就完成了,第一次画图有点丑。所以2 4 3 1 5就是一个合法的出站组合。
明白了题意后,展示一下代码:
#include<iostream>
#include<vector>//STL中的另一个容器,不了解的我后续再写一个介绍一下
#include<stack>//使用栈时需要加的头文件,千万别忘记啦
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {//用动态数组存入用户给出的出站组合
cin >> a[i];
}
stack<int> s;//创建栈s
int cur = 1;
bool f = 1;
for (int i = 0; i < n; i++) {
while ((s.empty()||s.top() != a[i])&&cur<=n) {//一遍一遍按照给出的出站顺序,必须把每个火车找到并且放到栈顶才可以出站。
s.push(cur);
cur++;
}
if (s.empty() || s.top() != a[i]) {
f = 0;
break;
}
else {
s.pop();
}
}
if (f) {
cout << "legal" << endl;
}
else {
cout << "illegal" << endl;
}
return 0;
}
运行结果:
输入 5
2 4 3 1 5
可以看到之前演示的2 4 3 1 5的出站顺序确实是合法的,说明程序运行正常
如上图的例子,先把1放进栈再出栈,接着要使5出栈,就必须把2 3 4 5都放进栈,把5出栈,此时4为栈顶,没法将3出栈。所以该出站组合不合法。文章来源:https://www.toymoban.com/news/detail-412003.html
今天的STL的分享就到这里啦,第一次写这么长的文章,也不知道效果如何,希望看到这里的优秀的你,可以给我点个赞嘛!(这人居然还敢要赞(doge))难免有疏漏之处,有错误,欢迎指正,一定认真吸取学习经验。
今天 你code 了嘛?文章来源地址https://www.toymoban.com/news/detail-412003.html
到了这里,关于【C++】STL之栈(stack)介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!