0202828 第三章栈和队列
10/20/2023
10/20/2023 栈和队列是两种特殊的线性表，是操作受限 的线性表，称限定性DS。 线性表 栈 队列 Insert(L,i,x) Insert(S,n+1,x） Insert(Q,n+l,x） Isisn+1 Delete(L,i) Delete(S,n) Delete(Q,1) 1<i<n 通常称，栈和队列是限定插入和删除 只能在表的端点进行的线性表
通常称，栈和队列是限定插入和删除 只能在表的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 栈和队列是两种特殊的线性表，是操作受限 的线性表，称限定性DS。 10/20/2023
10/20/2023 3.1栈的类型定义 3.2栈类型的实现 3.3栈的应用举例 3.4队列的类型定义 3.5队列类型的实现 练习
3.3 栈的应用举例 3.1 栈的类型定义 3.2 栈类型的实现 3.4 队列的类型定义 3.5 队列类型的实现 练习 10/20/2023
10/20/2023 3.1栈的类型定义 ·栈的定义和特点 ·定义：限定仅在表尾进行插入或删除操作的线 性表，表尾一栈顶，表头一栈底，不含 元素的空表称空栈。 •特点：先进后出 (FIL0)或后进先出(LIF0) 进栈 出栈 栈顶一 an 栈s=(al,a2,.,an) a2 栈底 a1
• 栈的定义和特点 •定义：限定仅在表尾进行插入或删除操作的线 性表，表尾—栈顶，表头—栈底，不含 元素的空表称空栈。 •特点：先进后出（FILO）或后进先出（LIFO） an a1 a2 . . 栈底 栈顶 . 进栈 . 出栈 栈s=(a1,a2,.,an) 3.1 栈的类型定义 10/20/2023
10/20/2023 •栈的抽象数据类型定义 ADT Stack{ 数据对象： D={a|a,∈ElemSet,.i=l,2,n,n≥0} 数据关系： R1={la-1,a,D,i=2,n} 约定a端为栈顶，a端为栈底。 基本操作： ADT Stack
ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,.,n, n≥0 } 数据关系： R1＝{ | ai-1, ai∈D, i=2,.,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack •栈的抽象数据类型定义 10/20/2023
10/20/2023 InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,&e) StackTravers(S,visitO)
InitStack(&S) DestroyStack(&S) ClearStack(&S) StackEmpty(s) StackLength(S) GetTop(S, &e) Push(&S, e) Pop(&S, &e) StackTravers(S, visit()) 10/20/2023
10/20/2023 InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁
InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 10/20/2023
10/20/2023 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈， 则返回TRUE,否则FALE
StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈， 则返回 TRUE，否则 FALE。 10/20/2023
10/20/2023 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个 数，即栈的长度
StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个 数，即栈的长度。 10/20/2023
10/20/2023 GetTop(S,&e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 a a2
GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 a1 a2 a . . n 10/20/2023