簡(jiǎn)介：
隊(duì)列是一種特殊的線(xiàn)性表舆吮，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作红淡，而在表的后端（rear）進(jìn)行插入操作，和棧一樣猪半，隊(duì)列是一種操作受限制的線(xiàn)性表兔朦。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭磨确。隊(duì)列中沒(méi)有元素時(shí)沽甥，稱(chēng)為空隊(duì)列。
隊(duì)列的數(shù)據(jù)元素又稱(chēng)為隊(duì)列元素乏奥。在隊(duì)列中插入一個(gè)隊(duì)列元素稱(chēng)為入隊(duì)摆舟，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱(chēng)為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入邓了，在另一端刪除恨诱，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱(chēng)為先進(jìn)先出（FIFO—first in first out）線(xiàn)性表骗炉。
順序隊(duì)列
建立順序隊(duì)列結(jié)構(gòu)必須為其靜態(tài)分配或動(dòng)態(tài)申請(qǐng)一片連續(xù)的存儲(chǔ)空間照宝，并設(shè)置兩個(gè)指針進(jìn)行管理。一個(gè)是隊(duì)頭指針front句葵，它指向隊(duì)頭元素硫豆；另一個(gè)是隊(duì)尾指針rear龙巨，它指向下一個(gè)入隊(duì)元素的存儲(chǔ)位置，如圖所示
每次在隊(duì)尾插入一個(gè)元素是熊响，rear增1旨别；每次在隊(duì)頭刪除一個(gè)元素時(shí)，front增1汗茄。隨著插入和刪除操作的進(jìn)行秸弛，隊(duì)列元素的個(gè)數(shù)不斷變化，隊(duì)列所占的存儲(chǔ)空間也在為隊(duì)列結(jié)構(gòu)所分配的連續(xù)空間中移動(dòng)洪碳。當(dāng)front=rear時(shí)递览，隊(duì)列中沒(méi)有任何元素，稱(chēng)為空隊(duì)列瞳腌。當(dāng)rear增加到指向分配的連續(xù)空間之外時(shí)绞铃，隊(duì)列無(wú)法再插入新元素，但這時(shí)往往還有大量可用空間未被占用嫂侍，這些空間是已經(jīng)出隊(duì)的隊(duì)列元素曾經(jīng)占用過(guò)得存儲(chǔ)單元儿捧。
順序隊(duì)列中的溢出現(xiàn)象：
（1） "下溢"現(xiàn)象：當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象挑宠》贫埽“下溢”是正常現(xiàn)象各淀，常用作程序控制轉(zhuǎn)移的條件懒鉴。
（2）"真上溢"現(xiàn)象：當(dāng)隊(duì)列滿(mǎn)時(shí)，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象碎浇×倨祝“真上溢”是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免奴璃。
（3）"假上溢"現(xiàn)象：由于入隊(duì)和出隊(duì)操作中吴裤，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無(wú)法重新利用溺健。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)麦牺，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱(chēng)為"假上溢"現(xiàn)象鞭缭。
循環(huán)隊(duì)列
在實(shí)際使用隊(duì)列時(shí)剖膳，為了使隊(duì)列空間能重復(fù)使用，往往對(duì)隊(duì)列的使用方法稍加改進(jìn)：無(wú)論插入或刪除岭辣，一旦rear指針增1或front指針增1 時(shí)超出了所分配的隊(duì)列空間吱晒，就讓它指向這片連續(xù)空間的起始位置。自己真從MaxSize-1增1變到0沦童，可用取余運(yùn)算rear%MaxSize和front%MaxSize來(lái)實(shí)現(xiàn)仑濒。這實(shí)際上是把隊(duì)列空間想象成一個(gè)環(huán)形空間叹话，環(huán)形空間中的存儲(chǔ)單元循環(huán)使用，用這種方法管理的隊(duì)列也就稱(chēng)為循環(huán)隊(duì)列墩瞳。除了一些簡(jiǎn)單應(yīng)用之外驼壶，真正實(shí)用的隊(duì)列是循環(huán)隊(duì)列。[2]
在循環(huán)隊(duì)列中喉酌，當(dāng)隊(duì)列為空時(shí)热凹，有front=rear，而當(dāng)所有隊(duì)列空間全占滿(mǎn)時(shí)泪电，也有front=rear般妙。為了區(qū)別這兩種情況，規(guī)定循環(huán)隊(duì)列最多只能有MaxSize-1個(gè)隊(duì)列元素相速，當(dāng)循環(huán)隊(duì)列中只剩下一個(gè)空存儲(chǔ)單元時(shí)碟渺，隊(duì)列就已經(jīng)滿(mǎn)了。因此突诬，隊(duì)列判空的條件時(shí)front=rear苫拍，而隊(duì)列判滿(mǎn)的條件時(shí)front=（rear+1）%MaxSize。
