什么是隊(duì)列？

隊(duì)列中的數(shù)據(jù)也呈線(xiàn)性排列。雖然與棧有些相似，但隊(duì)列中添加和刪除數(shù)據(jù)的操作分別是在兩端進(jìn)行的，就和隊(duì)列這個(gè)名字一樣，把它想象成排成一隊(duì)的人更容易理解。在隊(duì)列中，處理總是從第一名開(kāi)始往后進(jìn)行，而新來(lái)的人只能排在隊(duì)尾。

隊(duì)列是什么？

如上就是隊(duì)列的概念圖，現(xiàn)在隊(duì)列中只有數(shù)據(jù) Blue。往隊(duì)列中添加數(shù)據(jù)時(shí)，數(shù)據(jù)被加在最上面。

然后，隊(duì)列中添加了數(shù)據(jù) Green。往隊(duì)列中添加數(shù)據(jù)的操作叫作入隊(duì)。

緊接著，數(shù)據(jù) Red 也入隊(duì)了。

從隊(duì)列中取出（刪除）數(shù)據(jù)時(shí)，是從最下面，也就是最早入隊(duì)的數(shù)據(jù)開(kāi)始的，即 Blue。從隊(duì)列中刪除數(shù)據(jù)的操作叫作出隊(duì)。

如果再進(jìn)行一次出隊(duì)操作，取出的就是 Green 了。

像隊(duì)列這種最先進(jìn)去的數(shù)據(jù)最先被取來(lái)，即先進(jìn)先出的結(jié)構(gòu)，我們稱(chēng)為 First In First Out，簡(jiǎn)稱(chēng) FIFO。

與棧類(lèi)似，隊(duì)列中可以操作數(shù)據(jù)的位置也有一定的限制。在棧中，數(shù)據(jù)的添加和刪除都在同一端進(jìn)行，而在隊(duì)列中則分別是在兩端進(jìn)行的。隊(duì)列也不能直接訪(fǎng)問(wèn)位于中間的數(shù)據(jù)，必須通過(guò)出隊(duì)操作將目標(biāo)數(shù)據(jù)變成首位后才能訪(fǎng)問(wèn)。

與棧結(jié)構(gòu)不同的是，隊(duì)列的兩端都"開(kāi)口"，要求數(shù)據(jù)只能從一端進(jìn)，從另一端出，如圖所示：

通常，稱(chēng)進(jìn)數(shù)據(jù)的一端為 "隊(duì)尾"，出數(shù)據(jù)的一端為 "隊(duì)頭"，數(shù)據(jù)元素進(jìn)隊(duì)列的過(guò)程稱(chēng)為 "入隊(duì)"，出隊(duì)列的過(guò)程稱(chēng)為 "出隊(duì)"。

棧和隊(duì)列區(qū)別

棧和隊(duì)列不要混淆，棧結(jié)構(gòu)是一端封口，特點(diǎn)是"先進(jìn)后出"；而隊(duì)列的兩端全是開(kāi)口，特點(diǎn)是"先進(jìn)先出"。

隊(duì)列存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)有以下兩種方式：

（1）順序隊(duì)列：在順序表的基礎(chǔ)上實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)；

（2）鏈隊(duì)列：在鏈表的基礎(chǔ)上實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)；

兩者的區(qū)別僅是順序表和鏈表的區(qū)別，即在實(shí)際的物理空間中，數(shù)據(jù)集中存儲(chǔ)的隊(duì)列是順序隊(duì)列，分散存儲(chǔ)的隊(duì)列是鏈隊(duì)列。

隊(duì)列的實(shí)際應(yīng)用

在我們的實(shí)際生活中，隊(duì)列的應(yīng)用隨處可見(jiàn)，比如排隊(duì)買(mǎi)票電影票、在醫(yī)院的掛號(hào)系統(tǒng)等，采用的都是隊(duì)列的結(jié)構(gòu)。

拿排隊(duì)買(mǎi)票來(lái)說(shuō)，所有的人排成一隊(duì)，先到者排的就靠前，后到者只能從隊(duì)尾排隊(duì)等待，隊(duì)中的每個(gè)人都必須等到自己前面的所有人全部買(mǎi)票成功并從隊(duì)頭出隊(duì)后，才輪到自己買(mǎi)票。這就不是典型的隊(duì)列結(jié)構(gòu)嗎？

這么一說(shuō)，大家對(duì)于隊(duì)列是不是有個(gè)清晰地認(rèn)識(shí)呢？