什么是隊列

隊列，和棧一樣，也是一種對數據的"存"和"取"有嚴格要求的線性存儲結構。

與棧結構不同的是，隊列的兩端都"開口"，要求數據只能從一端進，從另一端出，如圖 1 所示：

圖 1 隊列存儲結構

通常，稱進數據的一端為 "隊尾"，出數據的一端為 "隊頭"，數據元素進隊列的過程稱為 "入隊"，出隊列的過程稱為 "出隊"。

不僅如此，隊列中數據的進出要遵循 "先進先出" 的原則，即最先進隊列的數據元素，同樣要最先出隊列。拿圖 1 中的隊列來說，從數據在隊列中的存儲狀態可以分析出，元素 1 最先進隊，其次是元素 2，最后是元素 3。此時如果將元素 3 出隊，根據隊列 "先進先出" 的特點，元素 1 要先出隊列，元素 2 再出隊列，最后才輪到元素 3 出隊列。

棧和隊列不要混淆，棧結構是一端封口，特點是"先進后出";而隊列的兩端全是開口，特點是"先進先出"。

因此，數據從表的一端進，從另一端出，且遵循 "先進先出" 原則的線性存儲結構就是隊列。

隊列的實現

隊列存儲結構的實現有以下兩種方式：

• 順序隊列：在順序表的基礎上實現的隊列結構;

• 鏈隊列：在鏈表的基礎上實現的隊列結構;

兩者的區別僅是順序表和鏈表的區別，即在實際的物理空間中，數據集中存儲的隊列是順序隊列，分散存儲的隊列是鏈隊列。

隊列的實際應用

實際生活中，隊列的應用隨處可見，比如排隊買 XXX、醫院的掛號系統等，采用的都是隊列的結構。

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

明白了什么是隊列，接下來開始系統地學習順序隊列和鏈隊列。