來看看棧和隊列不為人知的一面
我想棧和隊列的原理大家應該很熟悉了，隊列是先進先出，棧是先進后出。
如圖所示：
那么我這里在列出四個關于棧的問題，大家可以思考一下。以下是以C++為例，相信使用其他編程語言的同學也對應思考一下，自己使用的編程語言里棧和隊列是什么樣的。
- C++中stack 是容器么?
- 我們使用的stack是屬于那個版本的STL?
- 我們使用的STL中stack是如何實現的?
- stack 提供迭代器來遍歷stack空間么?
相信這四個問題并不那么好回答， 因為一些同學使用數據結構會停留在非常表面上的應用，稍稍往深一問，就會有好像懂，好像也不懂的感覺。
有的同學可能僅僅知道有棧和隊列這么個數據結構，卻不知道底層實現，也不清楚所使用棧和隊列和STL是什么關系。
所以這里我在給大家掃一遍基礎知識，
首先大家要知道 棧和隊列是STL(C++標準庫)里面的兩個數據結構。
C++標準庫是有多個版本的，要知道我們使用的STL是哪個版本，才能知道對應的棧和隊列的實現原理。
那么來介紹一下，三個最為普遍的STL版本：
- HP STL 其他版本的C++ STL，一般是以HP STL為藍本實現出來的，HP STL是C++ STL的第一個實現版本，而且開放源代碼。
- P.J.Plauger STL 由P.J.Plauger參照HP STL實現出來的，被Visual C++編譯器所采用，不是開源的。
- SGI STL 由Silicon Graphics Computer Systems公司參照HP STL實現，被Linux的C++編譯器GCC所采用，SGI STL是開源軟件，源碼可讀性甚高。
接下來介紹的棧和隊列也是SGI STL里面的數據結構， 知道了使用版本，才知道對應的底層實現。
來說一說棧，棧先進后出，如圖所示：
棧提供push 和 pop 等等接口，所有元素必須符合先進后出規則，所以棧不提供走訪功能，也不提供迭代器(iterator)。不像是set 或者map 提供迭代器iterator來遍歷所有元素。
棧是以底層容器完成其所有的工作，對外提供統一的接口，底層容器是可插拔的(也就是說我們可以控制使用哪種容器來實現棧的功能)。
所以STL中棧往往不被歸類為容器，而被歸類為container adapter(容器適配器)。
那么問題來了，STL 中棧是用什么容器實現的?
從下圖中可以看出，棧的內部結構，棧的底層實現可以是vector，deque，list 都是可以的， 主要就是數組和鏈表的底層實現。
我們常用的SGI STL，如果沒有指定底層實現的話，默認是以deque為缺省情況下棧的低層結構。
deque是一個雙向隊列，只要封住一段，只開通另一端就可以實現棧的邏輯了。
SGI STL中 隊列底層實現缺省情況下一樣使用deque實現的。
我們也可以指定vector為棧的底層實現，初始化語句如下：
- std::stack<int, std::vector<int> > third; // 使用vector為底層容器的棧
剛剛講過棧的特性，對應的隊列的情況是一樣的。
隊列中先進先出的數據結構，同樣不允許有遍歷行為，不提供迭代器, SGI STL中隊列一樣是以deque為缺省情況下的底部結構。
也可以指定list 為起底層實現，初始化queue的語句如下：
- std::queue<int, std::list<int>> third; // 定義以list為底層容器的隊列
所以STL 隊列也不被歸類為容器，而被歸類為container adapter( 容器適配器)。
我這里講的都是C++ 語言中情況， 使用其他語言的同學也要思考棧與隊列的底層實現問題， 不要對數據結構的使用淺嘗輒止，而要深挖起內部原理，才能夯實基礎。
