第2章 栈、队列与哈希

栈与队列是在程序设计中被广泛使用的两种重要的线性数据结构，都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用，与线性表相比，它们的插入和删除操作受到更多的约束和限定，故又称为限定性的线性表结构。不同的是，栈就像一个很窄的桶，先存进去的数据只能最后被取出来，属于LIFO（Last In First Out，后进先出）结构，它遵循进出顺序逆序，即先进后出，后进先出，栈结构如图2-1所示。队列像日常排队买东西的人的“队列”，先排队的人先买，后排队的人后买，是FIFO（First In First Out，先进先出）的，它保持进出顺序一致，即先进先出，后进后出，队列结构如图2-2所示。

图2-1 栈结构示意图

图2-2 队列结构示意图

需要注意的是，有时在数据结构中还有可能出现按照大小排队或按照一定条件排队的数据队列，这时的队列属于特殊队列，就不一定按照“先进先出”的原则读取数据了。