队列的存储与操作

1、成绩评阅人重庆邮电大学课程设计实验报告班级：1301416姓名：陈昊学号：2014214156指导老师：夏晨洋课程名称：数据结构实验时间：2015年10月26日-2015年11月2日实验地点：数字图书馆负一楼 B132实验四 队列的存储与操作一、实验目的1理解队列是限定只能在队头进行删除操作在队尾进行插入操作的线性表；2理解队列的存储结构特点，掌握队列的存储分配要点；3掌握队列的基本操作及实现，深刻领会队列操作的先进先出特征，并能正确 分析其时间复杂度，知道队列性能优于普通线性表，以及队列的常用情形。、主要数据结构描述class CirQueuepublicCirQueue( ); CirQu

2、eue( );void EnQueue(T x);T DeQueue( );T GetQueue( ); bool Empty( ); private :/ 构造函数，置空队/ 析构函数/ 将元素 x 入队/ 将队头元素出队/ 取队头元素(并不删除)/ 判断队列是否为空T dataQueueSize; int front, rear;/ 存放队列元素的数组/ 队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置;在循环队列这个数据结构中， 需要一个构造函数， 来创建一个空的队列； 需要一个析构 函数来删除队列；需要一个EnQueue ()函数来插入一个数据；需要一个DeQueue ()

3、函数来将队头的元素出队；需要一个DeQueue ()函数来输出队头的值；需要一个布尔型的函数来判断队列是否为空。三、算法的基本思想描述1. 构造函数：令头指针和尾指针均为零。2. 析构函数：空的析构函数。3. 入队函数：函数的形参为将存入队列的数据的值。因为判空和判满都需要用到 rear=front，所以在判满的操作中，对rea叶1取模，在循环的意义下进行判断。 如果( rear+1)%QueueSize=front ，那么队满。如果没有队满，那么就在循环 +1下标的位置存入当前数据。4. 出队操作：这里的出队不是删除相应的数据， 而是将队头指针 +1。首先判断队 是否为空，如果不为空就将队头

4、指针在循环意义上 +1。5. 取队头元素：将队头元素的值取出。6. 判空：如果 rear=front 则为空，否则不为空。 因为不涉及循环，所以所有函数的时间复杂度都为 O(1)。四、运行的结果截图五、实验体会和收获经过本次试验。我对循环队列有了更深的理解。了解了队列先进先出的特点 知道了如何运用队列解决相应的问题。六、程序清单。CirQueue.h/CirQueue. htifndef CIR3UEUE_HSdefuie CIR3UEUE_Hconst int （ieueSize=100 :定文存储臥,列元素的数组的最犬长度7走丈複扳类G i rQmeuetemplate < cl a

5、ss T>class Cirueuefpublic:CirQueue ():7 CirQueue(): void Enqueue (T x).T DeQumo ()；T GetQueuE(): bool Eupty(): private;T datafueueSise: irit frontk tear;；"构隆函養空耻"析构函数"将元轰K入耻"将弘头元素出弘"取弘头元熹（并不删腺）"判断弘列是苦为空"存放臥列元素的教组"臥头和以尾指针*分别指向PA头元秦的前一个位贵和队尾元素的位适AendifCirQueu

6、e.cppzzl/CirQu&ue. cpp#i_ncluid& CirQueue. h.17t&mplate <class T>-Ci-rQueueT: :Cii52uetie () fronts ear=0:<eliss T>-CirQueue<P ： ： "CirQueue()出|声明tempi at e <cl-as TFvoid CirQueue<T>: :EnQueme(T x)l£ C(rear+1) % QueueSizs =f ron+) -threw "上镒"；

7、rear=(rear+l) % QueueSize . "臥尾揩聊在徊if意义下加1 dart a re ar :/玄臥屋劲麻入元耒田声明t&mplatt <class T>-T CirQu&ue<T>:DeQueue()if (rear=trorrt) throw F游"；front- (front+l) % Q-ueueSize："臥头:指計在儒幵意义"TtClreturn data front:"读取并返回岀阮前的疏头元暂 注意队头指针teiplaize -Cclass T)-|T CirQueue

8、: ieQueue()Iint i.;if (rea.r=front) 'throv "下镒i'li= (fcont+1)鮒"注意不要給臥头指针赋值 xctu匚m da-tai:+1声明|tenplate <class r>Sbaol CirQueue<T>!:Empty() ：if ront=rear)veturri 1:elsereturn 0 :CirQueueMa in. cpp"弓I用输入输出療引； 成员函颇交件/创崖模版类的实创zzl /./C i ru eMain, cpp#include <:iostr

9、eajn>using najnespace st d :事incLude "匚1rQuene.cpp"-dvcid jitain ()iCirQueue<int >a:if (a-Empty ( ) cout«"循坏臥列空川寸1D撫行入臥損作:«edidl:t rya, EnQueue(lO) :/A FA ®作cat ch (char# uirong)ccut C<wonj;cout<C读取駄头元春!*«endl:c(xit«a. Get Queue ( ) «endl:&

10、quot;读臥头元秦cout«*®t 15#l行 AUS " «etnril:t rya* EnQu eub (:cat ch (chart wrong)COUt <<WOTLg；MLitV"读取臥头元春：«endl.c amt <a. QetQueue ( ) Cendl: couKCiil行出队操作！"泌1： "出队撓作 a. Dequeue ().ccnit«"读取臥头元蓑："羽(11; coni «a* Get Queue ( ) <<e

11、ndl:else cout« "ffi环队列不空 17 «endl.六、链队列链队列与顺序队列大致相同，只是用链表来表示而已。链队列的队头指针 指向头结点，队尾指针指向终端节点。基本数据结构：class LinkQueuepublic :Lin kQueue();Lin kQueue();void EnQueue(T x);T DeQueue();T GetQueue();bool Empty(); private :Node<T> *fron t, *rear;/构造函数，初始化一个空的链队列/析构函数，释放链队列中各结点的存储空间/将元素x入队/将

12、队头元素岀队/取链队列的队头元素/判断链队列是否为空/队头和队尾指针，分别指向头结点和终端结点 ；思想与顺序队列一致。需要注意的是对节点的增加和删除。在EnQueue() 中，将新申请的节点接在rear后，再让rear=新节点。在DeQueue ()中, 要暂存队头元素，用来返回，再摘链。运行结果和程序：操兀队矢出队 空看茁看晉 队查1Q对查10执查15入元£执队S/Link*3ueue. h-.#ifndef LINKQUTUE,H#define LIWKQOEUE_Htemplate <class T>tstruct NodeT data;RodHT;"此翅

13、ST也可臥省晞1template <class T>.-.class LinkQueuepublic:LinkQueust );"枸誉函埶！初怡化一个空的謎队列"LinkQueue ():"析构函数.痒啟筋弘列中各结直的存诸空闾void EnQueueCT玄)：“将元奏梵丸殴T Dequeue():"将陆头元素出陆I Get Queue (); "取駆疏列的皿头元靑tool Empty ():"和断槌毗列是百为空private:Nade<T> *front *rear；"弘头和RA屋指tH分别指向头结

14、卓和饕端结点-1 /L iriltQtietife. cpp Sirclude "LiTLhQu沖学 h"teijilate <cls£3 T>HLinl:Queue<T >: Linkueue () IK&ds <T> 也： s=ylSW Kod*<T>: s->next二NULL;front=rTar=s:)+1声明t cuplate <class T>3 L inltQiieiie<T >: : TinteQu-eue ()I while(f r ont)IRode O *

15、p ； p=£ r oiftzneqs t ; d&lei*? front ; £ron,t=p ,+ eaitplate class Tvoid Link Queue < 11: : ErQueue (T x)INode<T> +s：Erue mr Ucde<T>:s->da.t 3fx ;申请一!数拒坯为慕的结点罕s->nex+=NULL;rear- ZE:"将结点言插入到队屋rearms;土|声朋t emplate <class T>71 linkQu&ue<T>:;DeQue

16、ue 0Node <T> #p: int x:y7曹存甌头元養"捋弘头元素所在结直摘禅"判断出瓯前臥列隹度是否泊1if (rear=front) -thror *"FSE* : p=front->neKt:x=p->dala:f r ont->rext =p->next,if (p->neKtNULL) r&ar=f ront: delete p:return x;回声明template <class T>El I LinkQutue<T>: GetQueue C).f (front 匚ea

17、r)return £ron,t->neKt->data;田|声明templat e <class T>-bool LirJueu£<T>i: Rjnp'ty ()Iif(frent=rear)t亡turn 1.elsereturn 0;"引用输入输出萤"引入成員函議文件/创崖模版宾的实例LI /L inkQ ujeuieMain. cpp#inc lude <io2treajn> usiriff naxespaca std;fl include vL:inkQueue epp"-vcid

18、ntain 0Link Queue<int > 發：对W执行入臥换乍15"：/<A PA 作rf (a. Enpt/() cont«"PAS ,t rya, EnQsu日(1 : cat ch (chai* wrona)cout << vreng；:cout«" B看甌头元養J «endl:Q0Lrt"-CptQuen&( )<Vendl： "读0丄头元枣cout<C 16执行ARAS作："«endl. t rya, EnQuetie (15):catchtchar* wrong)cont << Rif