资源描述：
《队列的定义、表示、实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.1栈（Stack）3.2队列（Queue)第三章栈和队列1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式13.2队列只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。1.定义一、概念：例如：队列Q=(a1,a2,a3,…，an)在队尾插入元素称为入队；在队首删除元素称为出队。队头元素队尾元素允许插入的一端为队尾，允许删除的一端为队头。2与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，
2、具体实现依顺序队或链队的不同而不同。3.存储结构：4.运算规则：5.实现方式：2.逻辑结构：3二、队列的抽象数据类型定义ADTQueue{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定a1端为队列头，an端为队列尾。基本操作：}ADTStack4（1）初始化队列InitQueue(&Q)（2）入队EnQueue(&Q,e)（3）出队DeQueue(&Q,&e)（4）获取队头元素内容GetHead(Q,&e)（5）判断队列是否为空QueueEmpty(Q)基本
5、操作:建队列、判断队列是否为空、入队、出队、读队头元素值，等等。5链队列类型定义：typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;结点类型定义：typedefstructQNode{QElemTypedata;//元素structQNode*next;//指向下一结点的指针}Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构三、队列的表示和实现1.单链队列//-----队列的链式存储结构-----6a1∧an…Q.frontQ.rearQ.frontQ.rear∧空
6、队列为了操作方便，添加一个头结点，令头指针指向头结点。Q.front==Q.rear7StatusInitQueue(LinkQueue&Q){//构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;returnOK;}//-----基本操作的算法描述-----建队操作——构造空队列Q8Q(队尾)(队首)fronta1a2a3^rearp链队会满吗？一般不会，因为删除时有free动作。除非内存不足！入队（尾
7、部插入）：rear->next=S;rear=S;出队（头部删除）：p=front->next;front->next=p->next;free(p);Se^链队列的入队和出队操作9StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}10StatusDeQueue(LinkQu
8、eue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;//一定要考虑free(p);returnOK;}11队列的顺序存储结构如下图所示：附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置约定：初始化建空队列时，令front=rear=0；2.顺序队列12（2）
9、空队列的特征？约定：front=rear问题：（1）怎样实现入队和出队操作？核心语句如下：入队(尾部插入)：Q[rear]=e;rear++;出队(头部删除)：e=Q[front];front++;（3）队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。如图：13解决假溢出的途径———采用循环队列在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空位置，这就叫“假溢出”。讨论：什么叫“假溢出”？如何解决？将存储队列元素的一维数组首尾相接，形成一个环状。14a3a2a10123N-1rearfr
