什么是隊(duì)列

隊(duì)列，和棧一樣，也是一種對(duì)數(shù)據(jù)的"存"和"取"有嚴(yán)格要求的線性存儲(chǔ)結(jié)構(gòu)。

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

圖 1 隊(duì)列存儲(chǔ)結(jié)構(gòu)

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

不僅如此，隊(duì)列中數(shù)據(jù)的進(jìn)出要遵循 "先進(jìn)先出" 的原則，即最先進(jìn)隊(duì)列的數(shù)據(jù)元素，同樣要最先出隊(duì)列。拿圖 1 中的隊(duì)列來說，從數(shù)據(jù)在隊(duì)列中的存儲(chǔ)狀態(tài)可以分析出，元素 1 最先進(jìn)隊(duì)，其次是元素 2，最后是元素 3。此時(shí)如果將元素 3 出隊(duì)，根據(jù)隊(duì)列 "先進(jìn)先出" 的特點(diǎn)，元素 1 要先出隊(duì)列，元素 2 再出隊(duì)列，最后才輪到元素 3 出隊(duì)列。

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

因此，數(shù)據(jù)從表的一端進(jìn)，從另一端出，且遵循 "先進(jìn)先出" 原則的線性存儲(chǔ)結(jié)構(gòu)就是隊(duì)列。

隊(duì)列的實(shí)現(xiàn)

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

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

• 鏈隊(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)用隨處可見，比如排隊(duì)買 XXX、醫(yī)院的掛號(hào)系統(tǒng)等，采用的都是隊(duì)列的結(jié)構(gòu)。

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

明白了什么是隊(duì)列，接下來開始系統(tǒng)地學(xué)習(xí)順序隊(duì)列和鏈隊(duì)列。