当前位置：首页 > news >正文

第7次课栈A

news 来源：原创 2025/7/29 1:35:26

课堂学习

栈（stack）

是一种遵循先入后出逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

如图 5-1 所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

栈是 OI 中常用的一种线性数据结构。请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。

栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

栈的常用操作

栈的常用操作如下所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push()、pop()、peek() 命名为例。

通常情况下，我们可以直接使用编程语言内置的栈类。然而，某些语言可能没有专门提供栈类，这时我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

栈的操作是可以出栈、入栈交替进行的所以出栈序列并不一定是倒序
注意：已经出栈的数据不要重复入栈
注意：并不是所有的出栈序列都可以被操作出来

/* 初始化栈 */
stack<int> stack;/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);/* 访问栈顶元素 */
int top = stack.top();/* 元素出栈 */
stack.pop(); // 无返回值/* 获取栈的长度 */
int size = stack.size();/* 判断是否为空 */
bool empty = stack.empty();

练一练

总结：

栈的概念

数据的操作只从一端完成，如存、取等；
数据存放遵循，先进后出，后进先出的原则；

栈的操作

入栈、出栈；
栈顶元素、栈底元素、空栈、满栈：
判断出栈顺序

栈的实现

为了深入了解栈的运行机制，我们来尝试自己实现一个栈类。

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。换句话说，我们可以“屏蔽”数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

入栈

出栈

取栈顶元素

清空栈

#include<bits/stdc++.h>
using namespace std;
int a[6], top;
//入栈函数
void push(int x) { if (top<5) {top++;a[top]=x;}return;
}
//出栈函数
void pop() { if (top>0) {//a[top]=0; 可以省略top--;}return;
}
//显示栈顶元素
int getTop() { return a[top];
}
//清空栈
void clear() { top=0;return;
}
int main() {return 0;
}

课堂训练

4145 栈的操作

描述

输入5个整数，将这5个整数进行入栈，接下来做三次出栈操作，按照出栈顺序输出出栈元素，以上操作完成后输出此时的栈顶元素。

输入描述

输入5个整数，用空格隔开。

输出描述

输出2行，第1行输出出栈元素，按照出栈顺序输出，用空格隔开。第2行输出完成出栈操作后的栈顶元素。

样例输入 1

4 9 12 6 7

样例输出 1

7 6 12
9

提示

数据范围与提示

1≤整数≤1000

#include<bits/stdc++.h>
using namespace std;
int a[6], top;
void push(int x) { //入栈函数if (top<5) {top++;a[top]=x;}return;
}
void pop() { //出栈函数if (top>0) {top--;}return;
}
int getTop() { //显示栈顶元素return a[top];
}
void clear() { //清空栈top=0;return;
}
int main() {int num=0;//入栈for (int i=1;i<=5;i++) {cin>>num;push(num);}//出栈并输出出栈元素for (int i=1;i<=3;i++) {cout<<getTop()<<" ";pop();}//输出栈顶元素cout<<endl<<getTop();return 0;
}

2858 小鱼的数字游戏

描述

小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字a1、a2、a3…an-1、an ，反着念出来。如：1、2、3，反着念为：3、2、1。这对小鱼的那点记忆力来说实在是太难了，所以请你帮小鱼编程解决这个问题。

输入描述

第一行输入一个整数n(1<n<10)。
第二行输入n个数字，以空格间隔。

输出描述

一行内倒序输出n个数字，以空格间隔。

样例输入 1

7
3 65 23 5 34 1 30

样例输出 1

30 1 34 5 23 65 3

#include<bits/stdc++.h>
using namespace std;
int s[101];
int top=0;
//入栈
void push(int x) {if (top<100) {top++;s[top]=x;}return;
}
//出栈
void pop() {if (top>0) {top--;}return;
}
//显示栈顶
int getTop() {return s[top];
}int main() {int n = 0, num = 0;cin>>n;//输入并入栈for (int i = 0; i < n; i++) {cin >> num;push(num); //入栈}//输出并出栈while (top > 0) { //判断栈不为空cout << getTop() << " "; //输出栈顶pop(); //出栈}return 0;
}

2857 小括号问题

描述

假设表达式中只允许包含一种括号：圆括号，需要成对出现。即(( ))或(( )( ))等为正确的格式，(( )或 ( ))或(((均为不正确的格式。
给定一串括号输入（换行作为结束符），检测格式是否正确，若正确输出YES；错误输出NO。
（括号数量≤100）

输入描述

无

输出描述

无

样例输入 1

(())

样例输出 1

YES

#include<bits/stdc++.h>
using namespace std;
char s[101], a[101];
int top=0;
//入栈
void push(char x) {if (top<200) {top++;s[top]=x;}return;
}
//出栈
void pop() {if (top>0) {top--;}return;
}
//显示栈顶
char getTop() {return s[top];
}
int main() {cin >> a;//获取字符串int len=strlen(a);for (int i=0; i<len; i++) {//左括号入栈if (a[i]=='('){push(a[i]);} else if (getTop()=='(') {pop();} else {cout << "NO";return 0;	}}//栈空时if (top==0) {cout << "YES";//栈非空时} else {cout << "NO";}return 0;
}

2859 括号匹配问题

描述

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，但需要成对出现。即()或 [([ ][ ])]等为正确的格式，[ ( ] )或 ( [ ( ) )或( ( ) ] )均为不正确的格式。
给定一串括号输入（换行作为结束符），检测格式是否正确，若正确输出YES；错误输出NO。
（括号数量≤100）

输入描述

无

输出描述

无

样例输入 1

([]())

样例输出 1

YES

#include<bits/stdc++.h>
using namespace std;
char s[101], a[101];
int top=0;
//入栈
void push(char x) {if (top<200) {top++;s[top]=x;}return;
}
//出栈
void pop() {if (top>0) {top--;}return;
} 
//显示栈顶
char getTop() {return s[top];
} 
int main() {cin >> a;//获取字符串int len=strlen(a);for (int i=0; i<len; i++) {//左括号入栈if (a[i]=='['||a[i]=='('){push(a[i]);//右括号对比} else if (a[i]==')' && getTop()=='(') {pop();} else if (a[i]==']' && getTop()=='[') {pop();//既匹配不了栈顶也无法入栈} else {cout << "NO";return 0;}}//栈空时if (top==0) {cout << "YES";//栈非空时} else {cout << "NO";}return 0;
}

课后作业

2879 字母的读写
2880 中括号问题
5296 括号成加对数量
1680 调度员的烦恼

课堂学习

栈（stack）

栈的常用操作

练一练

总结：

栈的概念

栈的操作

栈的实现

入栈

出栈

取栈顶元素

清空栈

课堂训练

4145 栈的操作

2858 小鱼的数字游戏

2857 小括号问题

2859 括号匹配问题

课后作业

相关文章：