课堂学习
栈（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 调度员的烦恼