第三章栈和队列 栈和队列是两种特殊的线性表，是操作受限的线 性表，称限定性DS §3.1栈(stack) ★栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表， 表尾一栈顶，表头一栈底，不含元素的空表称空栈 特点：先进后出(FLO)或后进先出(LFO) 进栈 出栈 顶 An 栈s=(al,a2,.…,an a2 栈底 a1
第三章 栈和队列 栈和队列是两种特殊的线性表，是操作受限的线 性表，称限定性DS §3.1 栈（stack） 栈的定义和特点 ❖定义：限定仅在表尾进行插入或删除操作的线性表， 表尾—栈顶，表头—栈底，不含元素的空表称空栈 ❖特点：先进后出（FILO）或后进先出（LIFO） an a1 a2……... 栈底 栈 顶 进栈 ... 出栈 栈s=(a1,a2,……,an)
饯的类型定义 ADT Stack{ 数据对象 D={a|a:∈ElemSet,.i=l,2,.,n,n≥0} 数据关系： RI={<ai-1,ai>ai-,aED,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
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())
★栈的表示和实现 顺序栈 ●实现： 一维数组S[M我满 栈空 top top 5 F top top 4 top E top 4 3 top D top 3 3 2 top c top 2 top top B A top top=0 栈空 出栈 栈顶指针top,指向实际栈顶 设数组维数为M 后的空位置，初值为0 top=O,栈空，此时出栈，则下溢(underflow) top=M,栈满，此时入栈，则上溢(overflow)
栈的表示和实现 ❖顺序栈 ⚫实现：一维数组s[M] top=0 1 2 3 4 5 0 栈空 栈顶指针top,指向实际栈顶 后的空位置，初值为0 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) top top top top top 1 2 3 4 5 A 0 B C D E top F top top top top top 栈空
栈的顺序存储表示： #define STACK INIT SIZE 100: #define STACKINCREMENT 10: Typedef struct{ SElemType *base; SElemType *top; int stacksize; SqStack; ●初始化算法 ●取栈项元素算法
⚫初始化算法 ⚫取栈项元素算法 栈的顺序存储表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; Typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack;