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={<a-12a;>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 >| ai-1, ai∈D, i=2,.,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack •栈的抽象数据类型定义 10/20/2023