数据结构-栈与队列解读.ppt

  1. 1、本文档共53页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
按顺序方式存储的队列,数据元素存储在一系列连续的存储单元中,其结构与顺序表相同。 因此顺序存储的队列也可用一维数组来实现,front和rear指针则转变为队头和队尾元素在数组中的下标。 队列顺序存储 队列顺序存储 顺序存储的队列中,每次出队列的元素必定是队头元素,因此如果采取与普通顺序表同样的操作方式,则每次出队操作必然将整个队列向前移动,这使得效率大大降低。 因此在顺序存储的队列中,出队和入队操作都不移动元素而是移动指针。 若front和rear指针分别为队头和队尾元素在数组中的下标,则 入队操作: rear=rear+1,再将新元素赋值到rear所指位置 出队操作: 先将下标为front的元素读出,再front+1 这两种操作,移动指针和赋值的顺序相反,不利于编程。 为方便起见,这里规定队头指针front指向队头元素的前一个位置,队尾指针rear指向队尾元素所在位置。这样,入队和出队操作的执行步骤都是首先执行指针移动,再进行元素读写。 对空队列而言,可假定front和rear的值为-1 假溢出 A B C front rear front rear (a) A?B?C入队 (b) A?B出队, D?E入队 (c)队列假溢出 队列假溢出示意图 C D E front rear 随着元素不断入队列、出队列,rear和front指针会不断向后移动(如图(b)所示),最终会指向数组的最大下标位置(如图(c)所示)。由于rear和front指针只能单方向移动,这时元素无法入队列,但是队列中仍有大量空闲位置。这种情况称为假溢出。 循环队列 解决队列假溢出的办法是将存放队列元素的数组首尾相接,形成循环队列。 循环队列的基本操作方式为: 入队列 先执行rear=(rear+1)%M,再将新元素在rear指示位置加入; 出队列 先执行front=(front+1)%M,再将下标为front的元素取出。 为了将队空和对满的条件加以区分,一般不使用front指针所指的位置。 队空条件为front=rear 队满条件为(rear+1)%M=front 3 0 1 2 4 5 6 7 front rear A B C D 3 0 1 2 4 5 6 7 front rear 3 0 1 2 4 5 6 7 front rear A B C D F G E (a)循环队列空 (b)非空循环队列 (c)循环队列满 循环队列示意图 循环队列描述如下: struct SqQueue{ ElemType *data; // 存放元素的数组 int length; // 数组空间总长度 int front; // 队头指针 int rear; // 队尾指针 }; struct SqQueue q; // 定义队列q front和rear指针取值均为所指数组单元的下标。 由于队头指针所指单元总是空的,length比实际能存储的元素多一。 常用算法 (1)循环队列初始化 初始化过程建立数组空间并将队头、队尾指针设定到0号单元。 void InitQueue(SqQueue Q, int sz ) { Q.length = sz+1; Q.front = Q.rear = 0; Q.data = ( ElemType *)malloc(Q.length*sizeof (ElemType)); } 这里sz为队列最大长度,数组长度length比sz大一。 (2)入队操作 若队列不满,则在队尾插入元素x作为新的队尾。 void EnQueue(SqQueue Q , ElemType x) { if((Q.rear+1)%Q.length==Q.front) printf(“队列已满“); else { Q.rear = (Q.rear+1)%Q.length; Q.data[Q.rear]=x; } } ?(3)出队操作 若队列不空,则删除队头元素并用e取回该元素的值。 void DeQueue(SqQueue Q, ElemType e) { if(Q.rear==Q.front) printf(“队列已空“); else { Q.front = (Q.front +1)% Q.length; e = Q.data[Q.front]; } } (4)取队头元素 若队列不空,则用e取回队头元素的值。 void GetHead(SqQueu

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档