数据结构第3章复习：栈：是后进先出的线性表。栈顶指针：top栈底指针：base栈采用顺序存储结构----
顺序栈。低高地址topbase空栈入栈出栈a1a3topa2a4toptoptopa4a4t
op3.4队列1.抽象数据类型队列的定义队列是一种先进先出的线性表。它只允许在表的一端进行
插入，而在另一端删除元素。在队列中，允许插入的一端叫队尾，往队尾插入一个元素的操作叫入队允许删除的一端则称为队头，在队头端删除一个
元素的操作叫出队。
排队打印队列想一想
：生活中有哪些例子类似于队列？计算机中有哪些问题应用队列？a1
a2a3a4…….an队头队尾出队入队队列的抽象数据类型的定义：ADTQueue{
数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
|ai-1,ai∈D,i=2,...,n}约定a1端为队列头
，an端为队列尾。基本操作：InitQueue(&Q)DestroyQueue(&Q)Qu
eueLength(Q)QueueEmpty(Q)GetHead(Q,&e)ClearQueue(&Q)
EnQueue(&Q,e)DeQueue(&Q,&e)QueueT
ravers(Q,visit())
2.队
列的顺序表示与实现---循环队列队列有两种存储表示：链队列和循环队列。在队列的顺序存储结构中，除了用一组地
址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。
约定：初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，“尾指针增1”，每当删除队列头元素时，“
头指针增1”。因此，在非空队列中，头指针始终指向队列的头元素，而尾指针始终指向队列尾元素的下一个位置。
假设：队列分配的最大空间为6。012345Q.frontQ
.rearJ1012345Q.frontQ.rear空队列Q.rearJ1J2J3
012345J3012345Q.frontQ.rear
J3J4J5J6012345Q.frontQ.rear假溢出为解决假溢出现象，可采用循环队列
Q.rearJ7Q.rearJ8Q.rear注意：循环队列，队空时，front=rear，队满时，front=rea
r，因此只凭front=rear是无法判别队列是“空”还是“满”。
可以有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素的空间，约定以“
队列头指针在队列尾指针的下一位置上”作为队列呈“满”状态标志。#defineMAXQSIZE100//最大队列长度
typedefstruct{QElemTypebase;//动态分配存储空间intf
ront;//头指针，若队列不空，
//指向队列头元素intrear;//尾指针，若队列不空，指向
//队列尾元素的下一个位置}SqQueue;
StatusInitQueue(SqQueue&
Q){//构造一个空队列QQ.base=(ElemType)malloc
(MAXQSIZEsizeof(ElemType));if(!Q.base)exit(OVERFLOW);
//存储分配失败Q.front=Q.rear=0;
returnOK;}StatusEnQueue(SqQueue&Q,ElemTypee){//插
入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)r
eturnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)
%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue&Q,ElemType
&e){//若队列不空，则删除Q的队头元素，用e返回其值if(Q.front==Q.rear)r
eturnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%
MAXQSIZE;returnOK;}
StatusGetHead(SqQueueQ,ElemType&e){//若队列不空，则用
e返回Q的队头元素。if(Q.front==Q.rear)returnERROR;e=Q.ba
se[Q.front];returnOK;}3.队列的链式表示与实现＿＿链队列链队列：用链表表示
的队列简称为链队列，一个链队列需要两个分别指示队头和队尾的指针。链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需
修改尾指针或头指针。
a1∧an…Q.f
rontQ.rearQ.frontQ.rear∧空队列//-----队列的链式存储表示-----ty
pedefstructQNode{//结点类型QElemTypedata;structQ
Nodenext;}QNode,QueuePtr;typedefstruct{//链队列类型
QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}
LinkQueue;LinkQueueQ；
|
|
