《数据结构课件ppt第三章1.ppt》由会员分享，可在线阅读，更多相关《数据结构课件ppt第三章1.ppt（22页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,栈和队列是操作受限的线性表，它们的基本操作是线性表操作的子集。栈是限定仅在表尾进行插入或删除操作的线性表。表尾端成为栈顶，表头端成为栈底。栈的修改是按后进先出的原则进行，栈又称为后进先出的线性表。,栈和队列的示意图,栈只能在栈顶进行插入删除等操作，按照后进先出的原则。,a1,a2,an,.,栈顶,栈底,进栈,出栈,a1,a2,a3,an,.,出队列,入队列,队头,队尾,队列：队尾进行插入操作，队头进行删除操作。,线性表 栈 队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Dele
2、te(Q,1)1in,栈和队列是两种常用的数据类型,栈、队列与线性表的插入、删除操作对比,3.1 栈的类型定义,3.3 栈的应用举例,3.2 栈的表示与实现,3.4 队列的类型定义,3.5 队列类型的实现,3.1 栈的类型定义,ADT Stack 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：,ADT Stack,InitStack(&S),DestroyStack(&S),ClearStack(&S),StackEmpty(s),StackLength(S),GetTop(
3、S,&e),Push(&S,e),Pop(&S,&e),StackTravers(S,visit(),InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。,StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则FALE。,StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。,GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。,a1,a2,an,ClearStack(&S)
4、初始条件：栈 S 已存在。操作结果：将 S 清为空栈。,Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新 的栈顶元素。,a1,a2,an,e,Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1,栈的存储方法,顺序栈：利用一组地址连续的 存储单元依次存放自栈底到栈 顶的数据元素，同时附设指针 top指示栈顶元素在顺序栈中的 位置。链栈：头指针指向栈顶元素，每个结点的指针域指向前一个结点。,顺 序 栈,top:栈顶指针，始终指向栈顶元素的下一个位置。base：栈底指针，始终指向栈底的位置，b
5、aseNULL，栈不存在。base=top，栈空。,base,top,base,top,A,B,C,D,E,F,链栈,注意:链栈中指针的方向,top,a1,an,an-1,链栈是动态分配元素存储空间，元素的插入删除操作都是在表的同一端进行，头指针就是栈顶指针。,栈顶,栈底,3.2 栈的表示和实现,栈的定义栈的几个基本操作的实现Status InitStack(SqStack&S)Status Push(SqStack&S,SElemType e)Status Pop(SqStack&S,SElemType&e),/-栈的顺序存储表示-#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct SElemType*base;/构造栈之前和销毁栈之后，base值为NULL SElemType*top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单位 SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,Status InitStack(SqStack,Status Push(SqStack,a,b,a,b,c,s.base,s.top,s.base,s.top,s.base,s.top,A,B,C,s.base,s.top,e,
