- 1、本文档共54页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数字电子技术第3章_栈与队列
从被调函数返回调用函数的一般步骤: (1) 若栈为空,则执行正常返回。 ⑵ 从栈顶弹出一个工作记录。 ⑶ 将“工作记录”中的参数值、局部变量值赋给相应的变量;读取返回地址。 ⑷ 将函数值赋给相应的变量。 (5) 转移到返回地址。 1 队列的基本概念 队列(Queue):也是运算受限的线性表。是一种先进先出(First In First Out ,简称FIFO)的线性表。只允许在表的一端进行插入,而在另一端进行删除。 队首(front) :允许进行删除的一端称为队首。 队尾(rear) :允许进行插入的一端称为队尾。 例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。 3.3 队 列 3.3.1 队列及其基本概念 队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后,a1是队首元素,an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ,即队列的修改是依先进先出的原则进行的,如图3-5所示。 a1 , a2 , … , an 出队 入队 队尾 队首 图3-5 队列示意图 2 队列的抽象数据类型定义 ADT Queue{ 数据对象:D ={ ai|ai∈ElemSet, i=1, 2, …, n, n = 0 } 数据关系:R = {ai-1, ai | ai-1, ai∈D, i=2,3,…,n } 约定a1端为队首,an端为队尾。 基本操作: Create():创建一个空队列; EmptyQue():若队列为空,则返回true ,否则返回flase ; ?? InsertQue(x) :向队尾插入元素x; DeleteQue(x) :删除队首元素x; } ADT Queue 3.3.2 队列的顺序表示和实现 利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素,称为顺序队列。 对于队列,和顺序栈相类似,也有动态和静态之分。本部分介绍的是静态顺序队列,其类型定义如下: #define MAX_QUEUE_SIZE 100 typedef struct queue { ElemType Queue_array[MAX_QUEUE_SIZE] ; int front ; int rear ; }SqQueue; 3.3.2.1 队列的顺序存储结构 设立一个队首指针front ,一个队尾指针rear ,分别指向队首和队尾元素。 ◆ 初始化:front=rear=0。 ◆ 入队:将新元素插入rear所指的位置,然后rear加1。 ◆ 出队:删去front所指的元素,然后加1并返回被删元素。 ◆ 队列为空:front=rear。 ◆ 队满:rear=MAX_QUEUE_SIZE-1或front=rear。 在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。因为在入队和出队操作中,头、尾指针只增加不减小,致使被删除元素的空间永远无法重新利用。因此,尽管队列中实际元素个数可能远远小于数组大小,但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。如图3-6所示是数组大小为5的顺序队列中队首、队尾指针和队列中元素的变化情况。 (a) 空队列 Q.front Q.rear 入队3个元素 a3 a2 a1 Q.front Q.rear (c) 出队3个元素 Q.front Q.rear (d) 入队2个元素 a5 a4 Q.front Q.rear 图3-6 队列示意图 3.3.2.2 循环队列 为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)。 在循环队列中进行出队、入队操作时,队首、队尾指针仍要加1,朝前移动。只不过当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时,其加1操作的结果是指向向量的下界0。 这种循环意义下的加1操作可以描述为: if (i+1==MAX_QUEUE_SIZE) i=0; else i++ ; 其中: i代表队首指针(front)或队尾指针(rear) 用模运算可简化为:i=(i+1)%MAX_QUEUE_SIZE ; 显然,为循环队列所分配的空间可以被充分利用,除非向量空间真的被队列元素全部占用,否则不会上溢。因此,真正实用的顺序队列是循环队列。 例:设有循环队列QU
文档评论(0)