A3阶段 第一课 栈

2025年6月7日

学习时长

约1.5小时

难度

A3阶段/CSP-J

标签

数据结构

讲师

王骏峣

数据结构

·算法 + 数据结构 = 程序
算法：解决问题的步骤，如枚举、贪心、二分……
数据结构：计算机存储、组织数据发方式

核心概念： 栈是只能在一端插入或删除的特殊线性表


如果A比B更早进入栈，那A一定比B后退出栈（LIFO）


能操作的一端叫栈顶，另一端叫栈底

栈的有关操作

入栈：向栈顶加入新元素
出栈：删掉栈顶元素


用数组模拟栈

创建数组栈

数组栈的创建
int sta[N]; //开辟数组栈，N是栈最大的大小
int top=0; //使用变量记录栈顶位置

操作数组栈

数组栈的操作，注意：错误码按照自己的习惯更改
//入栈
if(top == N - 1) //栈已满
{
  return 0x3f3f3f01; //返回错误码
}
else{
  sta[++top] = x; //入栈
}
//出栈
if(top == 0) //空栈
{
  return 0x3f3f3f02; //返回错误码
}
else{
  --top;//出栈
}
//询问栈顶元素
if(top == 0) //空栈
{
  return 0x3f3f3f03; //返回错误码
}
else{
  return sta[top];//返回栈顶元素
}

STL中的栈容器（stack）

特点：简单易用，好记


stack的操作

代码 说明
STL stack操作
#include<stack>;
导入头文件
STL stack操作
stack<int> s;
创建一个存储int类型数据的栈
STL stack操作
s.push(a);
将a入栈
STL stack操作
s.pop();
将栈顶出栈
STL stack操作
int t = s.top();
将t赋值为s的栈顶元素
STL stack操作
int si = s.size();
将si赋值为s的大小（元素个数）
STL stack操作
bool isempty = s.empty();
将isempty赋值为s的是否为空（bool）

例题

第一题 栈

前往

题目考察栈的操作

第二题 验证栈序列

前往

题目考察出栈序列合法性判断的实现

第三题 平衡括号

前往

本题是对栈LIFO特性的应用

第四题 平衡括号2

前往

本题是上题的加强

第五题 GITARA

前往

本题考察栈的综合运用

学习要点总结

  1. 栈是一种基础的数据结构，单端操作，是一种具有LIFO特性的线性表
  2. 出栈与入栈是栈的基本操作
  3. STL stack容器提供打包好的栈
  4. 要学会综合运用LIFO特性解决问题
  5. 数组可以实现栈，但不常用
  6. 如果没有O2优化，数组模拟栈比STL Stack容器的速度更快