夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组

查看资料信息、公开预览和下载状态。

共 11 页PDF · 1.3MB
下载

文档在线预览

公开展示前 6 页
100%
1
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第1页预览
2
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第2页预览
3
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第3页预览
4
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第4页预览
5
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第5页预览
6
《3.1.1_栈的基本概念_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第三章栈、队列和数组》第6页预览

本文档共 11 页 剩余 5 页未展示,请下载后查阅

下载

文档文本内容

王道考研——数据结构
WWW.CSKAOYAN.COM
第三章 栈和队列本节内容
栈
(Stack)
基本概念
王道考研/CSKAOYAN.COM知识总览
注:数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构)
存储结构不同,运
算的实现方式不同
王道考研/CSKAOYAN.COM穿越:线性表的课件
“逻辑结构”
“运算”
注:数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构)
存储结构不同,运
算的实现方式不同
王道考研/CSKAOYAN.COM栈的定义
线性表是具有相同数据类型的n(n≥0)个数据元素的有限 序列,其中n为表长,当n = 0时线
性表是一个空表。若用L命名线性表,则其一般表示为
L = (a , a , … , a , a , … , a )
1 2 i i+1 n
栈(Stack)是只允许在一端进行插入或删除操作的线性表
a a a a a
1 2 3 4 5
王道考研/CSKAOYAN.COM栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表
王道考研/CSKAOYAN.COM栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表
逻辑结构:与普通线性表相同
数据的运算:插入、删除操作有区别
重要术语:栈顶、栈底、空栈
空栈
进栈顺序:
a1 à a2 à a3 à a4 à a5
栈顶:允许插入
和删除的一端 栈顶元素
a5
出栈顺序:
a4
a5 à a4 à a3 à a2 à a1
a3
特点:后进先出
a2
栈底:不允许插
Last In First Out (LIFO)
入和删除的一端 栈底元素
a1
王道考研/CSKAOYAN.COM穿越:线性表的基本操作
InitList(&L):初始化表。构造一个空的线性表L,分配内存空间。
创、销
DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占用的内存空间。
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
增、删
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。 改、查(“改”
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 之前也要“查”)
其他常用操作:
Length(L):求表长。返回线性表L的长度,即L中数据元素的个数。
PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表,则返回true,否则返回false。
王道考研/CSKAOYAN.COM栈的基本操作
InitStack(&S):初始化栈。构造一个空栈 S,分配内存空间。
创、销
DestroyStack(&S):销毁栈。销毁并释放栈 S 所占用的内存空间。
删除栈 Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶。
增、删
顶元素 Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。
不删除 GetTop(S, &x):读栈顶元素。若栈 S 非空,则用 x 返回栈顶元素 查:栈的使用场景中大
栈顶元 多只访问栈顶元素
素
其他常用操作:
StackEmpty(S):判断一个栈 S 是否为空。若S为空,则返回true,否则返回false。
王道考研/CSKAOYAN.COM栈的常考题型
进栈顺序:
a à b à c à d à e
有哪些合法的出栈顺序?
!
n个不同元素进栈,出栈元素不同排列的个数为 𝐶 % 。
$%
"#!
上述公式称为卡特兰(Catalan)数,可采用数学归纳法证
明(不要求掌握)。
1 10 ∗ 9 ∗ 8 ∗ 7 ∗ 6
'
𝐶 = = 42
!&
5 + 1 6 ∗ 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1
王道考研/CSKAOYAN.COM知识回顾与重要考点
王道考研/CSKAOYAN.COM