手撕408|數(shù)據(jù)結(jié)構(gòu)之棧 (4)

手撕408系列之?dāng)?shù)據(jù)結(jié)構(gòu)棧，冷月出品必是精品，大家好，我是學(xué)長(zhǎng)冷月。

當(dāng)我們學(xué)習(xí)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)時(shí)，一定要從數(shù)據(jù)結(jié)構(gòu)的三要素出發(fā)。邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。棧的運(yùn)算就不多說(shuō)了，無(wú)非就是增刪改查、初始化、判空等。

邏輯結(jié)構(gòu)

棧是一個(gè)先入后出（First In Last Out）的數(shù)據(jù)結(jié)構(gòu)，也就是說(shuō)棧只能在一端進(jìn)行插入或者刪除操作。那么我們就可以對(duì)棧下一個(gè)定義：棧是一個(gè)元素只能先入后出的線性表（受限制的線性表）。

棧是一個(gè)受限制的線性表，那為什么我們要對(duì)它受限制呢？其實(shí)棧中的操作，使用數(shù)組或者鏈表其實(shí)都可以實(shí)現(xiàn)。但是特定的數(shù)據(jù)結(jié)構(gòu)作用于特定的場(chǎng)景，數(shù)組或者鏈表暴露給用戶的接口很多，我們?cè)谟行﹫?chǎng)景不需要給用戶太多的接口，而當(dāng)我們用到一種先入后出的場(chǎng)景時(shí)，棧就排上了用場(chǎng)。

我們可以看下面這張圖：

假設(shè)，上面這個(gè)是一個(gè)裝盤(pán)子的桶，一號(hào)盤(pán)子在最下面，二號(hào)盤(pán)子在中間，三好盤(pán)子上最上面。如果要放入四號(hào)盤(pán)子，那么只能放在三號(hào)盤(pán)子的上面；如果要取盤(pán)子也只能先取三號(hào)盤(pán)子。相信大家能看懂這個(gè)例子，棧的思想也就是和這個(gè)裝盤(pán)子的過(guò)程有相似之處。

最后在補(bǔ)充兩個(gè)概念：

棧頂指針(top)：允許插入或刪除的那一端

棧底指針(buttom)：固定的，不允許插入或刪除的那一端

物理結(jié)構(gòu)

棧的本質(zhì)既然也是線性表，那么它的物理結(jié)構(gòu)肯定既有順序?qū)崿F(xiàn)也有鏈?zhǔn)綄?shí)現(xiàn)。

順序?qū)崿F(xiàn)也叫做順序棧，其底層實(shí)現(xiàn)為數(shù)組。結(jié)構(gòu)體的定義如下圖所示：

熟悉數(shù)組的同學(xué)可以看出，這個(gè)結(jié)構(gòu)體其實(shí)就是對(duì)數(shù)組加了一個(gè)棧頂指針。

其中，真題對(duì)于順序棧的考察較多，我們要注意以下幾個(gè)概念，用s來(lái)代表一個(gè)棧的變量：

棧頂指針：s.top

初始化時(shí)：s.top = -1

棧頂元素：s.data[s.top]

進(jìn)棧操作

IF 棧不滿  ; s.top ++ ; s.data[s.top] = data;

出棧操作

IF 棧非空  ; data = s.data[s.top]  ; s.top --

?？?/p>

s.top == -1

棧滿

s.top == MaxSize -1

當(dāng)前棧長(zhǎng)

s.top + 1

鏈?zhǔn)?/span>實(shí)現(xiàn)也叫做鏈棧，其結(jié)構(gòu)如下圖所示：

熟悉鏈表的同學(xué)應(yīng)該已經(jīng)看出，鏈棧類似于沒(méi)有頭結(jié)點(diǎn)的一個(gè)單鏈表。用Lhead代表?xiàng)ｍ斨羔樦赶蚴坠?jié)點(diǎn)，也就是棧頂元素。使用鏈棧的優(yōu)點(diǎn)就是方便棧的元素動(dòng)態(tài)的增加，不會(huì)出現(xiàn)棧滿的情況。其余的操作就和單鏈表非常類似，冷月就不多講了。

課后練習(xí)

1、對(duì)于順序表，訪問(wèn)第i個(gè)位置的元素和在第i個(gè)位置插入一個(gè)元素的時(shí)間復(fù)雜度為（）。

A.O(n),O(n)

B.O(n),O(1)

C.O(1),O(n)

D.O(1),O(1)

2、鏈表不具有的特點(diǎn)是        [福州大學(xué)1998  2 分]

A．插入、刪除不需要移動(dòng)元素 

B．可隨機(jī)訪問(wèn)任一元素   

C．不必事先估計(jì)存儲(chǔ)空間  

D．所需空間與線性長(zhǎng)度成正比

答案明天公布，明天別忘了來(lái)做題！

請(qǐng)幫冷月點(diǎn)一下旁邊的在看，再點(diǎn)一個(gè)贊,一鍵三連支持一下！您的每一次點(diǎn)擊都是對(duì)冷月莫大的鼓勵(lì)，謝謝?。?/strong>