第2章 棧、隊列與哈希

棧與隊列是在程序設(shè)計中被廣泛使用的兩種重要的線性數(shù)據(jù)結(jié)構(gòu)，都是在一個特定范圍的存儲單元中存儲的數(shù)據(jù)，這些數(shù)據(jù)都可以重新被取出使用，與線性表相比，它們的插入和刪除操作受到更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。不同的是，棧就像一個很窄的桶，先存進去的數(shù)據(jù)只能最后被取出來，屬于LIFO（Last In First Out，后進先出）結(jié)構(gòu)，它遵循進出順序逆序，即先進后出，后進先出，棧結(jié)構(gòu)如圖2-1所示。隊列像日常排隊買東西的人的“隊列”，先排隊的人先買，后排隊的人后買，是FIFO（First In First Out，先進先出）的，它保持進出順序一致，即先進先出，后進后出，隊列結(jié)構(gòu)如圖2-2所示。

圖2-1 棧結(jié)構(gòu)示意圖

圖2-2 隊列結(jié)構(gòu)示意圖

需要注意的是，有時在數(shù)據(jù)結(jié)構(gòu)中還有可能出現(xiàn)按照大小排隊或按照一定條件排隊的數(shù)據(jù)隊列，這時的隊列屬于特殊隊列，就不一定按照“先進先出”的原則讀取數(shù)據(jù)了。