日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

我想棧和隊(duì)列的原理大家應(yīng)該很熟悉了，隊(duì)列是先進(jìn)先出，棧是先進(jìn)后出。

網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)的關(guān)注點(diǎn)不是能為您做些什么網(wǎng)站，而是怎么做網(wǎng)站，有沒(méi)有做好網(wǎng)站，給創(chuàng)新互聯(lián)建站一個(gè)展示的機(jī)會(huì)來(lái)證明自己，這并不會(huì)花費(fèi)您太多時(shí)間，或許會(huì)給您帶來(lái)新的靈感和驚喜。面向用戶(hù)友好，注重用戶(hù)體驗(yàn)，一切以用戶(hù)為中心。

如圖所示：

那么我這里在列出四個(gè)關(guān)于棧的問(wèn)題，大家可以思考一下。以下是以C++為例，相信使用其他編程語(yǔ)言的同學(xué)也對(duì)應(yīng)思考一下，自己使用的編程語(yǔ)言里棧和隊(duì)列是什么樣的。

1. C++中stack 是容器么?
2. 我們使用的stack是屬于那個(gè)版本的STL?
3. 我們使用的STL中stack是如何實(shí)現(xiàn)的?
4. stack 提供迭代器來(lái)遍歷stack空間么?

相信這四個(gè)問(wèn)題并不那么好回答， 因?yàn)橐恍┩瑢W(xué)使用數(shù)據(jù)結(jié)構(gòu)會(huì)停留在非常表面上的應(yīng)用，稍稍往深一問(wèn)，就會(huì)有好像懂，好像也不懂的感覺(jué)。

有的同學(xué)可能僅僅知道有棧和隊(duì)列這么個(gè)數(shù)據(jù)結(jié)構(gòu)，卻不知道底層實(shí)現(xiàn)，也不清楚所使用棧和隊(duì)列和STL是什么關(guān)系。

所以這里我在給大家掃一遍基礎(chǔ)知識(shí)，

首先大家要知道 棧和隊(duì)列是STL(C++標(biāo)準(zhǔn)庫(kù))里面的兩個(gè)數(shù)據(jù)結(jié)構(gòu)。

C++標(biāo)準(zhǔn)庫(kù)是有多個(gè)版本的，要知道我們使用的STL是哪個(gè)版本，才能知道對(duì)應(yīng)的棧和隊(duì)列的實(shí)現(xiàn)原理。

那么來(lái)介紹一下，三個(gè)最為普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL為藍(lán)本實(shí)現(xiàn)出來(lái)的，HP STL是C++ STL的第一個(gè)實(shí)現(xiàn)版本，而且開(kāi)放源代碼。
2. P.J.Plauger STL 由P.J.Plauger參照HP STL實(shí)現(xiàn)出來(lái)的，被Visual C++編譯器所采用，不是開(kāi)源的。
3. SGI STL 由Silicon Graphics Computer Systems公司參照HP STL實(shí)現(xiàn)，被Linux的C++編譯器GCC所采用，SGI STL是開(kāi)源軟件，源碼可讀性甚高。

接下來(lái)介紹的棧和隊(duì)列也是SGI STL里面的數(shù)據(jù)結(jié)構(gòu)， 知道了使用版本，才知道對(duì)應(yīng)的底層實(shí)現(xiàn)。

來(lái)說(shuō)一說(shuō)棧，棧先進(jìn)后出，如圖所示：

棧提供push 和 pop 等等接口，所有元素必須符合先進(jìn)后出規(guī)則，所以棧不提供走訪功能，也不提供迭代器(iterator)。不像是set 或者map 提供迭代器iterator來(lái)遍歷所有元素。

棧是以底層容器完成其所有的工作，對(duì)外提供統(tǒng)一的接口，底層容器是可插拔的(也就是說(shuō)我們可以控制使用哪種容器來(lái)實(shí)現(xiàn)棧的功能)。

所以STL中棧往往不被歸類(lèi)為容器，而被歸類(lèi)為container adapter(容器適配器)。

那么問(wèn)題來(lái)了，STL 中棧是用什么容器實(shí)現(xiàn)的?

從下圖中可以看出，棧的內(nèi)部結(jié)構(gòu)，棧的底層實(shí)現(xiàn)可以是vector，deque，list 都是可以的， 主要就是數(shù)組和鏈表的底層實(shí)現(xiàn)。

我們常用的SGI STL，如果沒(méi)有指定底層實(shí)現(xiàn)的話，默認(rèn)是以deque為缺省情況下棧的低層結(jié)構(gòu)。

deque是一個(gè)雙向隊(duì)列，只要封住一段，只開(kāi)通另一端就可以實(shí)現(xiàn)棧的邏輯了。

SGI STL中 隊(duì)列底層實(shí)現(xiàn)缺省情況下一樣使用deque實(shí)現(xiàn)的。

我們也可以指定vector為棧的底層實(shí)現(xiàn)，初始化語(yǔ)句如下：

 
 
 
 
  
  
  
  
std::stack > third;  // 使用vector為底層容器的棧 
 
 
 

剛剛講過(guò)棧的特性，對(duì)應(yīng)的隊(duì)列的情況是一樣的。

隊(duì)列中先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，同樣不允許有遍歷行為，不提供迭代器, SGI STL中隊(duì)列一樣是以deque為缺省情況下的底部結(jié)構(gòu)。

也可以指定list 為起底層實(shí)現(xiàn)，初始化queue的語(yǔ)句如下：

 
 
 
 
  
  
  
  
std::queue> third; // 定義以list為底層容器的隊(duì)列 
 
 
 

所以STL 隊(duì)列也不被歸類(lèi)為容器，而被歸類(lèi)為container adapter( 容器適配器)。

我這里講的都是C++ 語(yǔ)言中情況， 使用其他語(yǔ)言的同學(xué)也要思考棧與隊(duì)列的底層實(shí)現(xiàn)問(wèn)題， 不要對(duì)數(shù)據(jù)結(jié)構(gòu)的使用淺嘗輒止，而要深挖起內(nèi)部原理，才能夯實(shí)基礎(chǔ)。

當(dāng)前題目：來(lái)看看棧和隊(duì)列不為人知的一面
轉(zhuǎn)載源于：http://www.dlmjj.cn/article/dpiisce.html