循环队列中人队算法的研究

《循环队列中人队算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机与现代化2005年第4期JISUANJIYUXIJ"iDJ蝴UA总第116期文章编号：1006．2475(2005)04．0009—02循环队列中人队算法的研究高永平，周书民(东华理工学院，江西抚州344000)摘要：讨论了数据结构中循环队列入队算法的设计思想并提出了解决队列满时的可行方法，解决了数据结构教材中没有解决的问题。关键词：循环队列；入队；队列满；算法中图分类号：TP301．6文献标识码：AAn触90I-i如【Ilic风search佃110wToEnterCircuklrQ眦吣GA

2、OY抽乎piJ】g，ZHOUShu—J1】in(EastC11imhlsdmteof7I&hn0】o日，Fu出ou344000，Cllim)Abs喇：T11ispaperdiscllssestlledesi鲥ngideaaboutthedatahowtoerller出ed工cl】larqueue，删desapracdcal印proachtodealwit

3、ltheprobIeInwhenthedrc山rqueueisfhⅡ，aIldresolvesⅡlequesti帆remai玎iI唱iIldat

4、asmlctIlresbDoks．Keywords：circ山rqIleue；enterir蜷thequeue；queueisfbⅡ；如ritll]【Ilicint矗ont；／／队头指针，指向队头元素O引言intrear；／／队尾指针，指向队尾元素的下一个位置}沁ue；《数据结构》课程是计算机程序设计的重要理论和顺序栈类似，在队列的顺序存贮结构中除了用基础，它不仅是计算机学科的核心课程，而且已成为一组连续存储单元依次存储从队头到队尾的数据元其他理工专业的热门选修课。该课程主要介绍各种素外，还需附加

5、两个变量，一个称为队头指针，指示队基本数据结构及相应的算法，使学生能够掌握如何把头元素的位置；一个称为队尾指针，指示队尾元素的现实世界的客观问题转换为在计算机内的表示形式。位置。为了充分利用好存储队列的空间，一个巧妙的队列被广泛地应用在各种软件系统中，用队列的先进办法是，将顺序队列(如图1所示)设想为首尾相连的先出的性质实现对计算机资源管理和过程模拟，在环状空间而成为循环队列(如图2所示)。《数据结构》中栈、队列的应用随处可见，例如二叉树望：竺§的访问、图的访问、快速排序、归并排序、二叉排序树5的

6、查找、二分查找等等，所以理解和掌握好队列的有4坦’塑关算法非常重要。32堂1提出问题l0在讲解队列时，我们知道队列是限定仅能在表头图l顺序队列图2循环队列进行删除，表尾进行插入的线性表。顺序队列的类型通过少用一个存储单元的方法来解决循环队列定义为：中队列为空和队列满的情况，当符合Q．rear=Q．硒nt#d出ne盹援SL巫100／／最大队列长度条件时队列空，而当符合Q．鼢t=Q．rear+1条件时眈)edefstmct{队列满。对于循环队列的入队算法，所有的数据结构QEle咖*base；／／初始化

7、时动态分配存储空间的基址收稿日期：20呻cr7．12基金项目：2004年东华理工学院硕博基金资助项目(D}渤436)。作者简介：高永平(1974．)，男，江西吉安人，东华理工学院讲师，硕士，研究方向：算法与分布式数据库技术；周书民(19r71．)，男，副教授，博士，研究方向：计算机网络与嵌入式系统。10计算机与现代化2005年第4期教材中对于入队出现队满时都只是简单地提示“队列‰t的值并且队尾指针的值Q．rear等于零时队列满，满”信息，也没有其他的任何文字说明和分析，好像循如图4所示。环队列在队

8、列满时没有方法可以解决。以下为各教55旦!骂尸NcREMENT旦!骂材以及各指导书上的原算法：5444statusI'm(Iueue(sqQ∞ue＆Q，Qeler晰e)33322{／／插入元素e为Q的新的队尾元素．缸(Q．Iear+1)％MAxS皿==Q．岛m)ret啪ER-1业唑1业骘：坚。皿ooRoR；／／队列满图3队列满图4队列满图5队列满状态Q．base[Q．艘]=e；状态一状态二二空间增加后Q．rear=(Q．Ⅻ+1)％MA)i：S磁；在这种情况下的队列满时，只需要修改队尾指Ret岫ok

9、：针的值以及循环队列允许存储的最大元素个数的值，}而队头指针以及队列中的数据元素都不需要变动。如果这样的话，那么循环队列在处理实际问题时即在申请增加原队列的存储空间后，将队尾指针Q．就缺乏灵活性了，只能处理固定大小的数据。我们知rear赋值为申请增加存储空间前的队列最大存储元道，循环队列实际上只是将顺序队列设想为首尾相连素个数，接着将队列的允许存储的最大元素个数Ⅱ姒的环状空间而已，既然还是顺序队列，那么理所当然变为申请之后的存储空间大小，申请存储空间增加后地可以处理当存储空间不够的