塔里木大学：《数据结构》课程教学课件（PPT讲稿）第三章 栈和队列

通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表栈队列线性表Insert(L, i, x)Insert(S, n+1, x)Insert(Q, n+1, x)1≤i<n+1Delete(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 栈和队列是两种常用的数据类型

第三章栈和队列栈3.1 3.2栈的应用举例队列3.4M

第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.4 队列

学习提要：1.掌握栈和队列这两种抽象数据类型的特点并能在相应的应用问题中正确选用它们2.熟练掌握栈类型的两种实现方法，即两种存诸结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法重难点内容：顺序栈的相关操作、循环队列的判空判满

学习提要： 1.掌握栈和队列这两种抽象数据类型的特点， 并能在相应的应用问题中正确选用它们。 2.熟练掌握栈类型的两种实现方法，即两种存 储结构表示时的基本操作实现算法，特别应 注意栈满和栈空的条件以及它们的描述方法。 3.熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。 重难点内容： 顺序栈的相关操作、循环队列的判空判满

s3.1栈（stack）栈的类型定义3.1.1栈的表示和实现3.1.2U

§3.1 栈（stack） 3.1.1 栈的类型定义 3.1.2 栈的表示和实现

3.1.1栈的类型定义★栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾一栈顶，表头一栈底，不含元素的空表称空栈进栈出栈栈顶an...栈s=(al,a2,......,an).a2栈底al特点：先进后出（FILO）或后进先出CLIFO)

栈的定义和特点 ❖定义：限定仅在表尾进行插入或删除操 作的线性表，表尾—栈顶，表头—栈底， 不含元素的空表称空栈。 an a1 a2. 栈底 栈 顶 进栈 . 出栈 栈s=(a1,a2,.,an) ❖特点：先进后出（FILO）或后进先出 （LIFO） 3.1.1 栈的类型定义

栈的类型定义ADT Stack 数据对象：D= { a; |a, EElemSet, i=1,2,..,n, n≥0 )数据关系：R1 = { |ai-1, a, ED, 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  栈的类型定义

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())

栈的表示和实现3.1.2★顺序栈类似于线性表的顺序映象实现指向表尾的指针可以作为栈顶指针栈的顺序存储表示/ / -----100:#define STACK INIT SIZE10;#define STACKINCREMENTtypedef struct SElemTypee *base;SElemType *top,int stacksize: SqStack;

顺序栈 3.1.2 栈的表示和实现 类似于线性表的顺序映象实现， 指向表尾的指针可以作为栈顶指针。 //- 栈的顺序存储表示- #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;

实现：一维数组s[M]栈空栈满topOF5AE4?DtopC2topBtopBAtopOtopAOtasebasebase出栈进栈空栈设数组维数为M栈底指针base始终top=base栈空，此时出栈，则指向栈底位置：栈顶下溢（underflow）指针top，其初值指向top=M,栈满，此时入栈，则上栈底，始终在栈顶元素的下一个位置溢(overflow)

实现：一维数组s[M] 1 top 2 3 4 5 0 进栈 A 栈满 B C D E F 设数组维数为M top=base,栈空，此时出栈，则 下溢（underflow) top=M,栈满，此时入栈，则上 溢（overflow) top top top top top 1 2 3 4 5 0 空栈 top base base top 出栈 top top 栈空 base 栈底指针base,始终 指向栈底位置；栈顶 指针top,其初值指向 栈底，始终在栈顶元 素的下一个位置 1 2 3 4 5 A 0 B top

Status InitStack (SqStack &S)构造一个空栈SS.base=(SElemType*)malloc(STACK INIT_SIZE*sizeof(SElemType))if（!S.base)exit（OVERFLOW)；//存储分配失败S.top = S.base;S.stacksize = STACK INIT SIZEreturn OK:

Status InitStack (SqStack &S) {// 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }