数据结构 第三章-栈和队列.ppt

1、3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示与实现 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列 - 队列的链式表示与实现 3.4.3 循环队列 - 队列的顺序表示与实现,第三章 栈和队列,栈(stack):仅在表尾进行插入和删除操作的线性表。 或后进先出(LIFO)的线性表。 或先进后出(FILO)的线性表。 栈顶(top): 线性表的表尾端。 栈底(bottom): 线性表的表头。,3.1 栈,例： 假定有五个元素a,b,c,d,e依次进栈，进栈过程中允许出栈 ，则栈的不可能的输出序列是_。 A e d c b a B d e c b a C

2、d c e a b D a b c d e,3.1.1 栈的抽象数据类型,ADT Stack 数据对象：D = ai | aiElemset, i=1,2,n, n0 数据关系：R1 = ai-1,ai|ai-1,ai D, i=2,3,n 约定an为栈顶, a1为栈底。 基本操作： InitStack( StackTraverse(S,visit () ADT Stack,3.1.2 栈的表示与实现,栈的顺序表示-用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 #define STACK_INIT_SIZE 100/存储空间初始分配量 #define STACKINCREMENT

3、10/存储空间分配增量 typedef struct SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; /当前已分配的存储空间，以元素为单位 SqStack;,顺序栈示意图,栈顶指针和栈中元素之间的关系,顺序栈的基本操作算法描述（初始化）,Status InitStack(SqStack / InitStack,Status GetTop( SqStack s, SElemType / GetTop,顺序栈的基本操作算法描述（取栈顶元素）,Status Push( SqStack /

4、Push,顺序栈的基本操作算法描述（入栈）,Status Pop( SqStack / Pop,顺序栈的基本操作算法描述（出栈）,试分析算法实现的功能：,void Sample1( Stack ,3.4 队列,队列（Queue）: 先进先出(First In First Out) (缩写为FIFO）的线性表。 仅在队尾进行插入和队头进行删除操作的线性表。 队头（front）: 线性表的表头端，即可删除端。 队尾（rear）: 线性表的表尾端，即可插入端。,队头,队尾,.,a1,a2,a3,an-1,an,队列的抽象数据类型,ADT Queue 数据对象：D = ai | aiElemset,

5、i=1,2,n, n0 数据关系：R1=ai-1,ai|ai-1,ai D, i=2,3,n 约定an为队尾, a1为队头。 基本操作： InitQueue( QueueTraverse(Q ,visit () ADT Queue,3.4.2 链队列 - 队列的链式表示与实现,typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针 LinkQueue;,data,*next,front,

6、rear,链队列示意图,(a)空队列,(b)元素“x”入队列,(c)元素“y”入队列,(d)元素“x”出队列,链队列的操作实现-构造空的队列,Status InitQueue(LinkQueue / InitQueue,链队列的操作实现- 销毁队列,Status DestroyQueue(LinkQueue / DestroyQueue,链队列的操作实现-入队,Status EnQueue(LinkQueue / EnQueue,链队列的操作实现-出队,Status DeQueue(LinkQueue / DeQueue,3.4.3 循环队列 -队列的顺序表示与实现,/-（循环）队列的动态分配

7、顺序存储结构 - #define MAXQSIZE 100 typedef struct QElemType *base; / 存储空间基地址 int front; / 队头指针 int rear; / 队尾指针 SqQueue;,采用顺序存储结构 约定: 1)初始空队列：Q.front = Q.rear=0 ; 2)插入新的元素时, Q.rear+; 3)删除队头元素时, Q.front+;,循环队列的头尾指针,将顺序队列臆造为一个环状的空间,称之为循环队列（Circular Queue）。,求队列长度：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE. 判断对列为满：(

8、Q.rear+1)%MAXQSIZE=Q.front. 判断队列为空：Q.rear=Q.front.,循环队列-队列的顺序存储结构实现(初始化),Status InitQueue(SqQueue / InitQueue,队列的顺序存储结构实现(求队列长度),int QueueLength(SqQueue Q) /返回Q的元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE; ,循环队列-队列的顺序存储结构实现(入队),Status EnQueue(SqQueue / EnQueue,循环队列-队列的顺序存储结构实现(出队),Status DeQueue(SqQueue / DeQueue,本章小结,掌握栈和队列这两种抽象数据类型的特点。 熟练掌握栈类型的顺序表示与实现，即顺序栈的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。 熟练掌握循环队