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