数据结构栈和队列精品文稿.ppt

《数据结构栈和队列精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构栈和队列精品文稿.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构栈和队列第1页，本讲稿共54页3.1 栈栈3.1.1 栈的基本概念栈的基本概念1 栈的概念栈的概念 栈栈(Stack)：是限制在表的一端进行插入和删除操作是限制在表的一端进行插入和删除操作的线性表。又称为后进先出的线性表。又称为后进先出LIFO(Last In First Out)或先进后或先进后出出FILO(First In Last Out)线性线性表。表。栈顶栈顶(Top)：允许进行插入、删除操作的一端，又允许进行插入、删除操作的一端，又称为表尾。用栈顶指针称为表尾。用栈顶指针(top)来指示栈顶元素来指示栈顶元素。栈底栈底(Bottom)：是固定端，又称为表头。是固定端，又称为

2、表头。空栈空栈：当表中没有元素时称为空栈。当表中没有元素时称为空栈。第2页，本讲稿共54页 设栈设栈S=(a1，a2，an)，则，则a1称为栈称为栈底元素，底元素，an为栈顶元素，如图为栈顶元素，如图3-1所示。所示。栈中元素按栈中元素按a1，a2，an的次序进栈，的次序进栈，退栈的第一个元素应为栈顶元素。即栈的退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。修改是按后进先出的原则进行的。图图3-1 顺序顺序栈示意图栈示意图a1a2aianbottomtop进栈（进栈（push）出栈出栈(pop)2 栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack数据对象：数据对象

3、：D=ai|aiElemSet,i=1,2,n，n0 数据关系：数据关系：R=|ai-1，aiD,i=2,3,n 基本操作：初始化、进栈、出栈、取栈顶元素等基本操作：初始化、进栈、出栈、取栈顶元素等 ADT Stack第3页，本讲稿共54页 栈的顺序存储结构简称为顺序栈，和线性表相类似，栈的顺序存储结构简称为顺序栈，和线性表相类似，用用一维数组一维数组来来存储栈存储栈。根据数组是否可以根据需要增大，。根据数组是否可以根据需要增大，又可分为又可分为静态顺序栈静态顺序栈和和动态顺序栈动态顺序栈。静态顺序栈静态顺序栈实现简单，但不能根据需要增大栈的实现简单，但不能根据需要增大栈的存储空间；存储空间；

4、动态顺序栈动态顺序栈可以根据需要增大栈的存储空间，但可以根据需要增大栈的存储空间，但实现稍为复杂。实现稍为复杂。3.1.2 栈的顺序存储表示栈的顺序存储表示第4页，本讲稿共54页 采用采用动态动态一维数组一维数组来来存储栈存储栈。所谓动态，指的是栈的大。所谓动态，指的是栈的大小可以根据需要增加。小可以根据需要增加。用用bottom表示栈底指针，栈底固定不变的；栈顶表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用则随着进栈和退栈操作而变化。用top(称为栈顶指针称为栈顶指针)指示当前栈顶位置。指示当前栈顶位置。用用top=bottom作为栈空的标记作为栈空的标记，每次，每次top

5、指向栈顶指向栈顶数组中的下一个存储位置。数组中的下一个存储位置。结点进栈结点进栈：首先将数据元素保存到栈顶首先将数据元素保存到栈顶(top所指所指的当前位置的当前位置)，然后执行，然后执行top加加1，使，使top指向栈顶的下指向栈顶的下一个存储位置一个存储位置;3.1.2.1 栈的动态顺序存储表示栈的动态顺序存储表示第5页，本讲稿共54页 结点出栈结点出栈：首先执行：首先执行top减减1，使，使top指向栈顶元素指向栈顶元素的存储位置，然后将栈顶元素取出的存储位置，然后将栈顶元素取出。图图3-2是一个动态栈的变化示意图是一个动态栈的变化示意图。图图3-2 (动态动态)堆栈变化示意图堆栈变化示

6、意图空栈空栈bottomtop元素元素a进栈进栈bottomtopa元素元素b，c进栈进栈bottomtopabc元素元素c退栈退栈bottomtopabbottomtopabdef元素元素d，e，f进栈进栈第6页，本讲稿共54页基本操作的实现基本操作的实现1 栈的类型定义栈的类型定义#define STACK_SIZE 100 /*栈初始向量大小栈初始向量大小 */#define STACKINCREMENT 10 /*存储空间分配增量存储空间分配增量 */#typedef int ElemType;typedef struct sqstack ElemType *bottom;/*栈不存在

7、时值为栈不存在时值为NULL */ElemType *top;/*栈顶指针栈顶指针 */int stacksize;/*当前已分配空间，以元素为单位当前已分配空间，以元素为单位 */SqStack;第7页，本讲稿共54页2 栈的初始化栈的初始化Status Init_Stack(void)SqStack S;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType);if(!S.bottom)return ERROR;S.top=S.bottom;/*栈空时栈顶和栈底指针相同栈空时栈顶和栈底指针相同 */S.stacksize=STACK_SI

8、ZE;return OK;第8页，本讲稿共54页3 压栈压栈(元素进栈元素进栈)Status push(SqStack S,ElemType e)if (S.top-S.bottom=S.stacksize-1)S.bottom=(ElemType*)realloc(S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType);/*栈满，追加存储空间栈满，追加存储空间 */if(!S.bottom)return ERROR;S.top=S.bottom+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top=e;S.top+;

9、/*/*栈顶指针加栈顶指针加1，e成为新的栈顶成为新的栈顶*/*/return OK;第9页，本讲稿共54页4 弹栈弹栈(元素元素出栈出栈)Status pop(SqStack S,ElemType *e)/*弹出栈顶元素弹出栈顶元素*/if(S.top=S.bottom)return ERROR;/*栈空，返回失败标志栈空，返回失败标志 */S.top-;e=*S.top;return OK;第10页，本讲稿共54页 采用采用静态静态一维数组一维数组来来存储栈存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，栈底固定不变的；栈顶则随着

10、进栈和退栈操作而栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量变化，用一个整型变量top(称为栈顶指针称为栈顶指针)来指示当前来指示当前栈顶位置。栈顶位置。用用top=0表示栈空的初始状态表示栈空的初始状态，每次，每次top指向栈顶指向栈顶在数组中的存储位置在数组中的存储位置。结点进栈结点进栈：首先执行首先执行top加加1，使，使top指向新的栈顶指向新的栈顶位置位置，然后将数据元素保存到栈顶然后将数据元素保存到栈顶(top所指的当前位所指的当前位置置)。3.1.2.2 栈的静态顺序存储表示栈的静态顺序存储表示(简略简略)第11页，本讲稿共54页 结点出栈结点出栈：首先首先把把

11、top指向的栈顶元素取出指向的栈顶元素取出，然后然后执行执行top减减1，使，使top指向新的栈顶位置指向新的栈顶位置。若栈的数组有若栈的数组有Maxsize个元素个元素，则，则top=Maxsize-1时栈满时栈满。图图3-3是一个大小为是一个大小为5的栈的变化示意图的栈的变化示意图。图图3-3 静态静态堆栈变化示意图堆栈变化示意图空栈空栈bottomtopTop=11个元素进栈个元素进栈bottomtopaTop=33个元素进栈个元素进栈bottomtopabcTop=4栈满栈满bottomtopabedTop=2元素元素c进栈进栈bottomtopab第12页，本讲稿共54页基本操作的实

12、现基本操作的实现1 栈的类型定义栈的类型定义#define MAX_STACK_SIZE 100 /*栈向量大小栈向量大小 */#typedef int ElemType;typedef struct sqstack ElemType stack_arrayMAX_STACK_SIZE;int top;SqStack;第13页，本讲稿共54页2 栈的初始化栈的初始化SqStack Init_Stack(void)SqStack S;S.bottom=S.top=0;return(S);第14页，本讲稿共54页3 压栈压栈(元素进栈元素进栈)Status push(SqStack S,ElemT

13、ype e)/*/*使数据元素使数据元素e进栈成为新的栈顶进栈成为新的栈顶 */*/if (S.top=MAX_STACK_SIZE-1)return ERROR;/*栈满，返回错误标志栈满，返回错误标志 */S.top+;/*/*栈顶指针加栈顶指针加1 */*/S.stack_arrayS.top=e ;/*/*e成为新的栈顶成为新的栈顶 */*/return OK;/*压栈成功压栈成功 */第15页，本讲稿共54页4 弹栈弹栈(元素元素出栈出栈)Status pop(SqStack S,ElemType *e)/*弹出栈顶元素弹出栈顶元素*/if(S.top=0)return ERROR;

14、/*栈空，返回错误标志栈空，返回错误标志 */*e=S.stack_arrayS.top;S.top-;return OK;第16页，本讲稿共54页 当栈满时做进栈运算必定产生空间溢出，简称当栈满时做进栈运算必定产生空间溢出，简称“上溢上溢”。上溢是一种出错状态，应设法避免。上溢是一种出错状态，应设法避免。当栈空时做退栈运算也将产生溢出，简称当栈空时做退栈运算也将产生溢出，简称“下溢下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。都是空栈，所以下溢常用来作为控制转移的条件。第17页，本讲稿共

15、54页1 栈的链式表示栈的链式表示 栈的栈的链式存储结构链式存储结构称为链栈，是运算受限的单链表。其称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针像单链表那样附加头结点，栈顶指针top就是链表的头指针。图就是链表的头指针。图3-4是栈的链式存储表示形式是栈的链式存储表示形式。3.1.3 栈的链式存储表示栈的链式存储表示(简略简略)空栈空栈top 非空栈非空栈top a4 a3 a1 a2图图图图3-4 3-4 链链链链栈存储形式栈存储形式链栈的链栈的结点类型说明如下：结

16、点类型说明如下：typedef struct Stack_Node ElemType data;struct Stack_Node *next;Stack_Node;第18页，本讲稿共54页2 链栈基本操作的实现链栈基本操作的实现(1)栈的初始化栈的初始化Stack_Node *Init_Link_Stack(void)Stack_Node *top;top=(Stack_Node *)malloc(sizeof(Stack_Node);top-next=NULL;return(top);第19页，本讲稿共54页(2)压栈压栈(元素进栈元素进栈)Status push(Stack_Node*t

17、op,ElemType e)Stack_Node *p;p=(Stack_Node *)malloc(sizeof(Stack_Node);if(!p)return ERROR;/*申请新结点失败，返回错误标志申请新结点失败，返回错误标志*/p-data=e;p-next=top-next ;top-next=p;/*钩链钩链 */return OK;第20页，本讲稿共54页(3)弹栈弹栈(元素元素出栈出栈)Status pop(Stack_Node *top,ElemType*e)/*/*将栈顶元素将栈顶元素出出栈栈 */*/Stack_Node *p;ElemType e;if (top-

18、next=NULL)return ERROR;/*栈空，返回错误标志栈空，返回错误标志 */p=top-next;e=p-data;/*/*取栈顶元素取栈顶元素 */*/top-next=p-next;/*/*修改栈顶指针修改栈顶指针 */*/free(p);return OK;第21页，本讲稿共54页3.2 栈的应用栈的应用 由于栈具有的由于栈具有的“后进先出后进先出”的固有特性，因此，栈成为的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例程序设计中常用的工具和数据结构。以下是几个栈应用的例子。子。第22页，本讲稿共54页3.2.1 数制转换数制转换十进制整数十进

19、制整数N向其它进制数向其它进制数d(二二、八八、十六十六)的转换是计算机实现的转换是计算机实现计算的基本问题。计算的基本问题。转换法则转换法则：该转换法则对应于一个简单算法原理该转换法则对应于一个简单算法原理:n=(n div d)*d+n mod d 其中：其中：div为整除运算为整除运算,mod为求余运算为求余运算例如例如 (1348)10=(2504)8，其运算过程如下：其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2第23页，本讲稿共54页 采用静态顺序栈方式实现采用静态顺序栈方式实现 void conversion(

20、int n,int d)/*将将十进制整数十进制整数N转换为转换为d(2或或8)进制数进制数*/SqStack S;int k,*e;S=Init_Stack();while (n0)k=n%d;push(S,k);n=n/d;/*求出所有的余求出所有的余数，数，进栈进栈 */while (S.top!=0)/*栈不空时出栈，输出栈不空时出栈，输出 */pop(S,e);printf(“%1d”,*e);第24页，本讲稿共54页3.2.2 括号匹配问题括号匹配问题 在文字处理软件或编译程序设计时，常常需要检查一个字符在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否

21、相匹配串或一个表达式中的括号是否相匹配?匹配思想匹配思想：从左至右扫描一个字符串从左至右扫描一个字符串(或表达式或表达式)，则，则每每个右括号将与最近遇到的那个左括号相匹配个右括号将与最近遇到的那个左括号相匹配。则可以在从。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号个右括号时，就将它与栈顶的左括号(如果存在如果存在)相匹配，同时从相匹配，同时从栈顶删除该左括号。栈顶删除该左括号。算法思想算法思想：设置一个栈，当读到左括号时，左括号进栈。当设置一个栈，当读到左括号时，左括号进栈。当读到

22、右括号时，则从栈中弹出一个元素，与读到的左括号进行匹读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回配，若匹配成功，继续读入；否则匹配失败，返回FLASE。第25页，本讲稿共54页算法描述算法描述#define TRUE 0#define FLASE -1SqStack S;S=Init_Stack();/*堆栈初始化堆栈初始化*/int Match_Brackets()char ch,x;scanf(“%c”,&ch);while(asc(ch)!=13)/*不等于回车不等于回车*/第26页，本讲稿共54页 if (ch=()|(ch=)p

23、ush(S,ch);else if (ch=)x=pop(S);if(x!=)printf(“括号不匹配括号不匹配”);return FLASE ;else if (ch=)x=pop(S);if(x!=()printf(“(括号不匹配括号不匹配”);return FLASE ;第27页，本讲稿共54页if (S.top!=0)printf(“括号数量不匹配！括号数量不匹配！”);return FLASE ;else return TRUE ;第28页，本讲稿共54页3.3栈与递归调用的实现栈与递归调用的实现(简简)栈的另一个重要应用是在程序设计语言中实现递归调用。栈的另一个重要应用是在程序设

24、计语言中实现递归调用。递归调用递归调用：一个函数一个函数(或过程或过程)直接或间接地调用自己本直接或间接地调用自己本身，简称身，简称递归递归(Recursive)。递归递归是程序设计中的一个强有力的工具。因为递归函数是程序设计中的一个强有力的工具。因为递归函数结构清晰，程序易读，正确性很容易得到证明。结构清晰，程序易读，正确性很容易得到证明。为了使递归调用不至于无终止地进行下去，实际上有为了使递归调用不至于无终止地进行下去，实际上有效的递归调用函数效的递归调用函数(或过程或过程)应包括两部分：应包括两部分：递推规则递推规则(方方法法)，终止条件终止条件。例如：求例如：求n!第29页，本讲稿共5

25、4页Fact(n)=1 当当n=0时时 终止条件终止条件n*fact(n-1)当当n0时时 递推规则递推规则 为保证递归调用正确执行，系统设立一个为保证递归调用正确执行，系统设立一个“递归工作栈递归工作栈”，作为整个递归调用过程期间使用的数据存储区。作为整个递归调用过程期间使用的数据存储区。每一层递归包含的信息如：每一层递归包含的信息如：参数参数、局部变量局部变量、上一层的返上一层的返回地址构成回地址构成一个一个“工作记录工作记录”。每进入一层递归，就产生一。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作

26、记录。一个工作记录。第30页，本讲稿共54页 从被调函数返回调用函数的一般步骤：从被调函数返回调用函数的一般步骤：(1)若栈为空，则执行正常返回。若栈为空，则执行正常返回。从栈顶弹出一个工作记录。从栈顶弹出一个工作记录。将将“工作记录工作记录”中的参数值、局部变量值赋给相中的参数值、局部变量值赋给相应的变量；读取返回地址。应的变量；读取返回地址。将函数值赋给相应的变量。将函数值赋给相应的变量。(5)转移到返回地址。转移到返回地址。第31页，本讲稿共54页1 队列的基本概念队列的基本概念 队列队列(Queue)：也是运算受限的线性表。是一种：也是运算受限的线性表。是一种先进先出先进先出(Firs

27、t In First Out，简称，简称FIFO)的线性表。只允许在表的一端进的线性表。只允许在表的一端进行插入，而在另一端进行删除。行插入，而在另一端进行删除。队首队首(front)：允许进行删除的一端称为队首。：允许进行删除的一端称为队首。队尾队尾(rear)：允许进行插入的一端称为队尾。：允许进行插入的一端称为队尾。例如：排队购物。操作系统中的作业排队。先进入队列的例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。成员总是先离开队列。3.4 队队 列列3.4.1 队列及其基本概念队列及其基本概念第32页，本讲稿共54页 队列中没有元素时称为空队列。在空队列中依次加入元

28、队列中没有元素时称为空队列。在空队列中依次加入元素素a1,a2,an之后，之后，a1是队首元素，是队首元素，an是队尾元素。显然退是队尾元素。显然退出队列的次序也只能是出队列的次序也只能是a1,a2,an ，即队列的修改是依，即队列的修改是依先进先出先进先出的原则进行的，如图的原则进行的，如图3-5所示。所示。a1,a2,an出队出队入队入队队尾队尾队首队首图图3-5 队列示意图队列示意图2 队列的抽象数据类型定义队列的抽象数据类型定义ADT Queue数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n=0 第33页，本讲稿共54页数据关系：数据关系：R=|ai-1,aiD,

29、i=2,3,n 约定约定a1端为队首，端为队首，an端为队尾。端为队尾。基本操作：基本操作：Create()：创建一个空队列：创建一个空队列；EmptyQue()：若队列为空：若队列为空，则返回则返回true，否则返回否则返回flase；InsertQue(x)：向队尾插入元素：向队尾插入元素x；DeleteQue(x)：删除队首元素：删除队首元素x；ADT Queue第34页，本讲稿共54页3 队列的顺序表示和实现队列的顺序表示和实现(简简)利用利用一组连续的存储单元一组连续的存储单元(一维数组一维数组)依次存放从队首到队依次存放从队首到队尾的各个元素，称为尾的各个元素，称为顺序队列顺序队列

30、。对于队列，和顺序栈相类似，也有动态和静态之分。本部分对于队列，和顺序栈相类似，也有动态和静态之分。本部分介绍的是介绍的是静态顺序队列静态顺序队列，其类型定义如下：，其类型定义如下：#define MAX_QUEUE_SIZE 100typedef struct queue ElemType Queue_arrayMAX_QUEUE_SIZE;int front;int rear;SqQueue;第35页，本讲稿共54页队列的顺序队列的顺序存储结构存储结构 设立一个设立一个队首指针队首指针front，一个，一个队尾指针队尾指针rear，分别指向，分别指向队首和队尾元素队首和队尾元素。初始化初始

31、化：front=rear=0。入队入队：将新元素插入将新元素插入rear所指的位置，然后所指的位置，然后rear加加1。出队出队：删去删去front所指的元素，然后加所指的元素，然后加1并返回被删并返回被删元素。元素。队列为空队列为空：front=rear。队满队满：rear=MAX_QUEUE_SIZE-1或或front=rear。第36页，本讲稿共54页 在非空队列里，队首指针始终指向队头元素，而队尾在非空队列里，队首指针始终指向队头元素，而队尾指针始终指向指针始终指向队尾元素的下一位置队尾元素的下一位置。顺序队列中存在顺序队列中存在“假溢出假溢出”现象。因为在入队和出队操现象。因为在入队

32、和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针巳超出向量空间的远远小于数组大小，但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为上界而不能做入队操作。该现象称为假溢出假溢出。如图。如图3-6所示所示是数组大小为是数组大小为5的顺序队列中队首的顺序队列中队首、队尾指针和队列中元队尾指针和队列中元素的变化情况。素的变化情况。因此因此,目前很少使用。目前很少使用。第37页，本讲稿共54页(a

33、)空队列空队列Q.frontQ.rear(b)入队入队3个元素个元素a3a2a1Q.frontQ.rear(c)出队出队3个元素个元素Q.frontQ.rear(d)入队入队2个元素个元素a5a4Q.frontQ.rear图图3-6 队列示意图队列示意图第38页，本讲稿共54页3.4.3 循环队列循环队列 为充分利用向量空间，克服上述为充分利用向量空间，克服上述“假溢出假溢出”现象的方现象的方法是：将为队列分配的法是：将为队列分配的向量空间看成为一个首尾相接的圆环向量空间看成为一个首尾相接的圆环，并称这种队列为并称这种队列为循环队列循环队列(Circular Queue)。在循环队列中进行出队

34、、入队操作时，队首、队尾指在循环队列中进行出队、入队操作时，队首、队尾指针仍要加针仍要加1，朝前移动。，朝前移动。只不过当队首、队尾指针指向向量上只不过当队首、队尾指针指向向量上界界(MAX_QUEUE_SIZE-1)时，其加时，其加1操作的结果是指向向量的下界操作的结果是指向向量的下界0。这种循环意义下的加这种循环意义下的加1操作可以描述为：操作可以描述为：if (i+1=MAX_QUEUE_SIZE)i=0;else i+;其中：其中：i代表队首指针代表队首指针(front)或队尾指针或队尾指针(rear)第39页，本讲稿共54页用模运算可简化为：用模运算可简化为：i=(i+1)%MAX_

35、QUEUE_SIZE;显然，为循环队列所分配的空间可以被充分利用，除显然，为循环队列所分配的空间可以被充分利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因非向量空间真的被队列元素全部占用，否则不会上溢。因此，此，真正实用的顺序队列是循环队列真正实用的顺序队列是循环队列。例：设例：设有循环队列有循环队列QU0，5，其初始状态是，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图，各种操作后队列的头、尾指针的状态变化情况如下图3-7所示。所示。123450(a)空队列空队列frontrear123450(b)d,e,b,g入入队队frontdebgrea

36、r123450(c)d,e出队出队bgfrontrear第40页，本讲稿共54页 入队时尾指针向前追赶头指针，出队时头指针向前追入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故赶尾指针，故队空和队满时头尾指针均相等队空和队满时头尾指针均相等。因此，。因此，无法通无法通过过front=rear来判断队列来判断队列“空空”还是还是“满满”。解决此问题的方法。解决此问题的方法是：约定入队前，测试尾指针在循环意义下加是：约定入队前，测试尾指针在循环意义下加1后是否等于头指后是否等于头指针，若相等则认为队满针，若相等则认为队满。即。即：rear所指的单元始终为空。所指的单元始终为空。12345

37、0(d)i,j,k入入队队bgfrontijkrear123450(e)b,g出队出队ijkrearfront123450(f)r,p,s,t入队入队ijkfrontrprear图图3-7 循环队列操作及指针变化情况循环队列操作及指针变化情况第41页，本讲稿共54页 循环队列为空循环队列为空：front=rear。循环队列满循环队列满：(rear+1)%MAX_QUEUE_SIZE=front。循环队列的基本操作循环队列的基本操作1 循环队列的初始化循环队列的初始化SqQueue Init_CirQueue(void)SqQueue Q;Q.front=Q.rear=0;return(Q);第

38、42页，本讲稿共54页2 入队操作入队操作Status Insert_CirQueue(SqQueue Q,ElemType e)/*/*将数据元素将数据元素e插入到循环队列插入到循环队列Q的队尾的队尾 */*/if (Q.rear+1)%MAX_QUEUE_SIZE=Q.front)return ERROR;/*队满，返回错误标志队满，返回错误标志 */Q.Queue_arrayQ.rear=e;/*/*元素元素e入队入队 */*/Q.rear=(Q.rear+1)%MAX_QUEUE_SIZE;/*队尾指针向前移动队尾指针向前移动 */return OK;/*入队成功入队成功 */第43页

39、，本讲稿共54页3 出队操作出队操作Status Delete_CirQueue(SqQueue Q,ElemType *x)/*/*将循环队列将循环队列Q的队首元素出队的队首元素出队 */*/if (Q.front=Q.rear)return ERROR;/*队空，返回错误标志队空，返回错误标志 */*x=Q.Queue_arrayQ.front;/*/*取队首元素取队首元素*/*/Q.front=(Q.front+1)%MAX_QUEUE_SIZE;/*队首指针向后移动队首指针向后移动 */return OK;第44页，本讲稿共54页1 队列的链式存储表示队列的链式存储表示 队列的链式存储

40、结构简称为链队列，它是限制队列的链式存储结构简称为链队列，它是限制仅在表仅在表头进行删除操作和表尾进行插入操作的单链表头进行删除操作和表尾进行插入操作的单链表。需要两类不同的结点需要两类不同的结点：数据元素数据元素结点结点，队列的队列的队首指针队首指针和队尾指针和队尾指针的结点的结点，如图，如图3-8所示。所示。3.4.2 队列的链式表示和实现队列的链式表示和实现数据元素结点类型定义：数据元素结点类型定义：typedef struct Qnode ElemType data;struct Qnode *next;QNode;数据元素结点数据元素结点data指针结点指针结点front rear图

41、图3-8 链队列结点示意图链队列结点示意图第45页，本讲稿共54页指针结点类型定义：指针结点类型定义：typedef struct link_queue QNode *front；/队头指针队头指针 Qnode *rear;/队尾指针队尾指针Link_Queue;2 链队运算及指针变化链队运算及指针变化 链队的操作实际上是单链表的操作，只不过是链队的操作实际上是单链表的操作，只不过是删除在删除在表头进行，插入在表尾进行表头进行，插入在表尾进行。插入、删除时分别修改不同的。插入、删除时分别修改不同的指针。链队运算及指针变化如图指针。链队运算及指针变化如图3-9所示。所示。第46页，本讲稿共54页

42、图图3-9 队列操作及指针变化队列操作及指针变化(a)空队列空队列front rear(b)x入队入队 x front rear(c)y再入队再入队 y front rear x(d)x出队出队 y xfront rear第47页，本讲稿共54页3 链队列的基本操作链队列的基本操作 链队列的初始化链队列的初始化LinkQueue*Init_LinkQueue(void)LinkQueue *Q;QNode *p;p=(QNode*)malloc(sizeof(QNode);/*开辟头结点开辟头结点*/p-next=NULL;Q=(LinkQueue *)malloc(sizeof(LinkQu

43、eue);/*开辟链队的指针结点开辟链队的指针结点 */Q.front=Q.rear=p;return(Q);第48页，本讲稿共54页 链队列的链队列的入队操作入队操作 在已知队列的队尾插入一个元素在已知队列的队尾插入一个元素e，即，即修改队尾修改队尾指针指针(Q.rear)。Status Insert_CirQueue(LinkQueue *Q,ElemType e)/*/*将数据元素将数据元素e插入到链队列插入到链队列Q的队尾的队尾 */*/p=(QNode*)malloc(sizeof(QNode);if(!p)return ERROR;/*申请新结点失败，返回错误标志申请新结点失败，返

44、回错误标志*/p-data=e;p-next=NULL;/*形成新结点形成新结点*/Q.rear-next=p;Q.rear=p;/*新结点插入到队尾新结点插入到队尾 */return OK;第49页，本讲稿共54页 链队列的出队操作链队列的出队操作Status Delete_LinkQueue(LinkQueue *Q,ElemType*x)QNode*p;if (Q.front=Q.rear)return ERROR;/*队空队空 */p=Q.front-next;/*/*取队首结点取队首结点 */*/*x=p-data;Q.front-next=p-next;/*修改队首指针修改队首指针

45、 */if (p=Q.rear)Q.rear=Q.front;/*当队列只有一个结点时应防止丢失队尾指针当队列只有一个结点时应防止丢失队尾指针 */free(p);return OK;第50页，本讲稿共54页 链队列的撤消链队列的撤消void Destroy_LinkQueue(LinkQueue *Q)/*将链队列将链队列Q的队首元素出队的队首元素出队 */while (Q.front!=NULL)Q.rear=Q.front-next;/*令尾指针指向队列的第一个结点令尾指针指向队列的第一个结点 */free(Q.front);/*每次释放一个结点每次释放一个结点 */*第一次是头结点，以

46、后是元素结点第一次是头结点，以后是元素结点 */Q.ront=Q.rear;第51页，本讲稿共54页习习 题题 三三1 设有一个栈，元素进栈的次序为设有一个栈，元素进栈的次序为a,b,c。问经过栈操作。问经过栈操作后可以得到哪些输出序列？后可以得到哪些输出序列？2 循环队列的优点是什么循环队列的优点是什么?如何判断它的空和满如何判断它的空和满?3 设有一个静态顺序队列，向量大小为设有一个静态顺序队列，向量大小为MAX，判断队列为空的，判断队列为空的条件是什么？队列满的条件是什么？条件是什么？队列满的条件是什么？4 设有一个静态循环队列，向量大小为设有一个静态循环队列，向量大小为MAX，判断队列

47、，判断队列为空的条件是什么？队列满的条件是什么？为空的条件是什么？队列满的条件是什么？5 利用栈的基本操作，利用栈的基本操作，写一个返回栈写一个返回栈S中结点个数的算中结点个数的算法法int StackSize(SeqStack S)，并说明，并说明S S为何不作为指针参数为何不作为指针参数的的算法算法?第52页，本讲稿共54页6 一个双向栈一个双向栈S是在同一向量空间内实现的两个栈是在同一向量空间内实现的两个栈，它，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)，入栈，入栈Push(S,i,x)，出栈，出

48、栈Pop(S,i,x)算法算法，其中，其中i为为0或或1，用以表示栈号。，用以表示栈号。7 设设Q0,6是一个静态顺序队列是一个静态顺序队列，初始状态为，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。变化情况，若不能入对，请指出其元素，并说明理由。a,b,c,d入队入队a,b,c出队出队i,j,k,l,m入队入队d,i出队出队n,o,p,q,r入队入队第53页，本讲稿共54页8 假设假设Q0,5是一个循环队列是一个循环队列，初始状态为，初始状态为front=rear=0，请，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。入对，请指出其元素，并说明理由。d,e,b,g,h入队入队d,e出队出队i,j,k,l,m入队入队b出队出队n,o,p,q,r入队入队 第54页，本讲稿共54页