本文的所有代碼均由C++編寫

引用及參考資料：

• 王道數(shù)據(jù)結(jié)構(gòu)
• 大話數(shù)據(jù)結(jié)構(gòu)
• 超硬核十萬字！全網(wǎng)最全 數(shù)據(jù)結(jié)構(gòu) 代碼，隨便秒殺老師/面試官，我說的_hebtu666-CSDN博客

5 棧

5.1 引入

在前面學(xué)習(xí)線性表的時候，我們給出了線性表的定義：

線性表是具有相同數(shù)據(jù)類型的n個數(shù)據(jù)元素的有限序列。其中n為表長，當(dāng)n=0的時候線性表是一個空表。若用L命名線性表，即：$L=(a_1,a_2,a_3\dots .,a_n)$。

實際上，棧（Stack）是一類特殊的線性表，它只允許在一端進(jìn)行插入或刪除操作。棧在一些其他科目中也被叫做堆棧。這樣從數(shù)學(xué)角度來看仿佛很抽象，能不能有一個形象地比喻呢？

這里我們引入的是《大話數(shù)據(jù)結(jié)構(gòu)》中的例子。

假設(shè)現(xiàn)在有一把手槍，從結(jié)構(gòu)上看，一顆子彈打出去后，另一顆子彈就會上膛，但是如果上膛的是一顆壞掉的子彈，那手槍能夠換下一顆嗎？如果在不自己手動拆出彈夾更換的情況下是做不到的。

這里引入的第二個例子是王道數(shù)據(jù)結(jié)構(gòu)視頻的例子。

當(dāng)在不抱起所有盤子且不移動其他盤子的情況下，如果我們要拿起一個盤子或者放一個盤子，只能在最上面下手吧。同樣的，如果我們要吃一支烤串，在不咬爛肉的情況下想要吃到第二個肉，必須先吃第一個再吃第二個吧。

由上面的例子可以總結(jié)出，棧實際上是一個先進(jìn)后出的結(jié)構(gòu)，且只能在一端進(jìn)行操作。

5.2 重要術(shù)語說明

如果棧內(nèi)沒有任何一個元素，我們稱其為空棧。

我們把允許插入和刪除的那一端叫做棧頂，另一端叫做棧底，不含任何數(shù)據(jù)元素的棧叫做空棧。由此我們可以發(fā)現(xiàn)，第一個進(jìn)去的元素在最底下，所以，棧又稱為后進(jìn)先出(Last In First Out)的線性表。我們也把棧的結(jié)構(gòu)叫做LIFO結(jié)構(gòu)。

棧的插入操作我們也叫進(jìn)棧，也稱壓棧或入棧。類似子彈入彈夾。

棧的刪除操作我們也叫出棧，也稱彈棧。如同彈夾中子彈出夾。

5.3 進(jìn)棧出棧變化形式

有些人受到固定思維，意味棧中最先進(jìn)棧的元素一定是最后出棧的，其實不一定。比如123依次入棧，那會有很多種結(jié)果。

• 第一種：1、2 、3進(jìn)，再1 、2 、3出。
• 第二種：1進(jìn)1出2進(jìn)2出3進(jìn)3出。
• 第三種：1進(jìn)2進(jìn)2出1出3進(jìn)3出。
• 第四種：1進(jìn)1出2進(jìn)3進(jìn)3出2出。
• 第五種：1進(jìn)2進(jìn)2出3進(jìn)3出1出。

從這里我們可以看出，三個元素就有5種變化，那么當(dāng)元素數(shù)目變多時，變化就有可能更多。在考研或者其他面試中，最喜歡的就是考查棧的合法出棧順序，所以這里一定要搞清楚。

5.4 棧的抽象數(shù)據(jù)類型

前面說過，棧是一種特殊的線性表，所以線性表中有的操作棧都有。需要注意的是，前面我們在談?wù)摶静僮鞯拿Q寫法時說過名稱一定要能讓人看懂。在嚴(yán)蔚敏一版的教材中，我們采用如下抽象數(shù)據(jù)結(jié)構(gòu)。

ADT 棧(stack) Data同線性表。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系。 OperationInitStack(*S):初始化操作，建立一個空棧s。DestroyStack(*S):若棧存在，則銷毀它。ClearStack(*S):將棧清空。StackEmpty(S):若棧為空，返回true，否咋返回false。GetTop(S,*e):若棧存在且非空，用e返回s的棧頂元素。Push(*S,e):若棧S存在，插入新元素e則棧S中并成為棧頂元素。Pop(*S,e):刪除棧S中棧頂元素，并用e返回其值。StackLength(S):返回棧S的元素個數(shù)。 endADT

5.5 順序棧

5.5.1 順序棧的定義

#define MaxSize 10 //定義棧中元素的最大個數(shù) typedef struct{ElemType data[MaxSize]; //靜態(tài)數(shù)組存放棧中元素int top; //棧頂指針 }SqStack;

在棧的定義中，我們用了top來指明棧頂元素在數(shù)組中的位置，top就如同老師用的游標(biāo)卡尺中的游標(biāo)一般，其可以來回移動，但是游標(biāo)不能超過尺，即棧頂指針不能超過定義的數(shù)組容量。一般來說，如果空棧，意味著棧中沒有元素，此時我們的top = -1。

在這里要科普一些關(guān)于棧頂指針和棧的一些知識。

棧頂指針也叫堆棧指針，一般堆棧的棧底不能動，所以數(shù)據(jù)入棧前要先修改堆棧指針，使它指向新的空余空間然后再把數(shù)據(jù)存進(jìn)去，出棧的時候相反。

堆棧指針，隨時跟蹤棧頂?shù)刂?#xff0c;按"先進(jìn)后出"的原則存取數(shù)據(jù)。

計算機(jī)中的堆棧主要用來保存臨時數(shù)據(jù)，局部變量和中斷/調(diào)用子程序程序的返回地址。

ARM處理器中通常將寄存器R13作為堆棧指針（SP）。ARM處理器針對不同的模式，共有 6 個堆棧指針（SP），其中用戶模式和系統(tǒng)模式共用一個SP，每種異常模式都有各自專用的R13寄存器（SP）。它們通常指向各模式所對應(yīng)的專用堆棧，也就是ARM處理器允許用戶程序有六個不同的堆棧空間。這些堆棧指針分別為R13、R13_svc、R13_abt、R13_und、R13_irq、R13_fiq。

5.5.2 初始化以及判空

如果要對棧進(jìn)行初始化，根據(jù)上面說過top=-1為空棧的情況，我們可以寫出如下所示的初始化代碼：

void InitStack(SqStack &S) {S.top = -1; }

根據(jù)初始化的特點，如果我們想要判斷棧是否為空，只需：

bool StackEmpty(SqStack S) {if(S.top==-1)return true;elsereturn false; }

5.5.3 進(jìn)棧操作

對于進(jìn)棧操作push，我們可以：

bool Push(SqStack &S,ElemType x) {if(S.top == MaxSize-1) //棧滿，報錯return false;S.data[++S.top] = x; //移動堆棧指針，并且給堆棧指針指向的棧頂元素賦值return true; }

5.5.4 出棧操作

對于出棧操作pop，我們可以：

bool Pop(SqStack &S,ElemType &x) {if(S.top==-1)return false;x = S.data[S.top--]; //先返回元素給x，再移動堆棧指針return true; }

這里要注意的是，我們并沒有把出棧元素的數(shù)據(jù)清空，所以雖然出棧，但是只是邏輯上被刪除了，實際上數(shù)據(jù)還殘留在內(nèi)存中。

5.5.5 讀棧操作

對于讀棧，一般我們都是讀棧頂元素。如下所示：

bool GetTop(SqStack S,ElemType &x) {if(S.top == -1)return false;x = S.data[S.top];return true; }

5.5.6 關(guān)于棧頂指針的指向問題

有時候，棧頂指針會在初始化的時候不是指向-1而是指向0，而當(dāng)棧滿的時候不是指向棧頂元素而是指向棧頂元素的下一位，此時上面的判空、初始化、讀棧、進(jìn)棧操作和出棧操作中代碼都會有些小小的不一樣，需要大家注意，這在考試中可能會出現(xiàn)。

5.5.7 共享棧

顧名思義，共享棧就是兩個棧共用一個棧空間。

在順序棧的設(shè)計過程中，我們可以發(fā)現(xiàn)其用的是靜態(tài)數(shù)組來分配的棧空間，這就導(dǎo)致可能棧空間內(nèi)存不足，如果要使用動態(tài)數(shù)組的方式去分配內(nèi)存，這么做很麻煩。

但是兩個棧就不一樣了，我們可以把兩個棧用一個很大的數(shù)組放著，其中這個數(shù)組是兩個棧的共享棧空間。如果你用的多，我用的少，那我就多給你一點空間，這樣很容易協(xié)調(diào)空間的分配。

兩個棧的空間放置如下，我們可以看成是兩個棧頂面對面放置。

兩個棧的棧指針移動時如下所示：

共享棧代碼如下：

//定義共享棧 #define MaxSize 10 typedef struct {ElemType data[MaxSize];int top0;int top1; }shstack;//初始化共享棧 void InitStack(ShStack &S) {S.top0 = -1;S.top1 = MaxSize; }

如果棧滿了，其條件是兩指針對應(yīng)的棧誰再進(jìn)棧一次都會重合。

top0 +1 == top1

5.6 鏈棧

5.6.1 概述

我們把棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)叫做鏈棧。

相對于鏈棧來說，我們需要考慮第一個問題：

我們要把棧頂放在鏈表的頭部還是尾部。

對于鏈表來說，鏈表不管是帶頭結(jié)點還是不帶頭結(jié)點，都帶有一個頭指針，如果棧頂不處于鏈表頭部的話，那么我們就要再聲明一個指針作為棧頂指針，這顯然很麻煩。既然這樣，我們不如把棧頂指針和頭指針合二為一即可。需要注意的是，合二為一的前提是棧頂實際上就是第一個結(jié)點，如果你帶頭結(jié)點，那么第一個結(jié)點就不能放元素了，這不太符合棧的定義了，所以在鏈棧中，我們一般不會再用到學(xué)習(xí)單鏈表所用到的頭結(jié)點了。

對于鏈棧，就不存在順序棧那樣空間不足的問題了，除非是內(nèi)存不足。

5.6.2 鏈棧的定義

鏈棧中的定義在不同的書上有不同的方式，如果你想記錄棧的長度，那么我推薦你使用下面的方式：

//結(jié)點定義 typedef struct StackNode {int data;StackNode* next; }StackNode,*LinkStackptr;//鏈棧定義 typedef struct LinkStack {LinkStackptr top;//指針int Length; }LinkStack

5.6.3 鏈棧的初始化

對于鏈棧初始化，就是把傳入的鏈棧指向空，并且設(shè)置棧長為0。

//初始化 bool LinkStackInit(LinkStack &S) {S.top = NULL;S.Length = 0;return true; }

5.6.4 鏈棧的進(jìn)棧

對于鏈棧的進(jìn)棧，考慮帶頭結(jié)點的情況，我們可以發(fā)現(xiàn)實際上就是指定只能在頭結(jié)點后插，這樣的話，根據(jù)之前在單鏈表學(xué)過的后插操作，可以自行寫出代碼，這里不再贅述。

但是如果是不帶頭結(jié)點，那么我們可以如下所示：

//進(jìn)棧 bool push(LinkStack &S, int e) { //生成新節(jié)點并且把添加值加入StackNode *newnode = new StackNode;newnode->data = e;//開始添加結(jié)點，變換指針順序newnode->next = S.top;S.top = newnode;//添加完成,計入表長S.Length++;return true; }

5.6.5 鏈表的出棧

對于不包含頭結(jié)點鏈表的出棧，無非就是對棧頂指針后的結(jié)點刪除，需要注意的是當(dāng)棧中結(jié)點剩余0和1的時候，我們需要設(shè)置額外情況。

//彈棧 bool pop(LinkStack& S, int& e) {if (S.Length == 0) {return false;}//生成指針用于記錄刪除結(jié)點所在地址StackNode *p = new StackNode;//返回刪除結(jié)點中的值e = S.top->data;//將指針移向棧頂p = S.top;//棧頂位置改變S.top = S.top->next;//釋放原棧頂delete(p);//表長改變S.Length--;return false; }

5.6.6 輸出鏈棧

輸出鏈棧也很容易，只需指定一根指針從棧頂掃向棧底即可。掃的時候依次輸出每個結(jié)點中的數(shù)據(jù)。

bool CoutStack(LinkStack S) {StackNode* p = S.top;cout << "由棧頂?shù)綏５?#xff1a;" ;while (p) {cout << p->data << endl;p = p->next;}cout << endl;return true; }

5.6.7 輸出棧頂元素

//輸出棧頂元素 bool GetTop(LinkStack& S, int e) {if (S.Length == 0)return false;e = S.top->data;return true; }

5.7 鏈棧和順序棧的對比

對比順序棧和鏈棧，它們的時間復(fù)雜度一樣，均為O(1)。對于空間性能，順序棧的空間是死的，是固定的；而對于鏈棧，雖然空間沒有限制，但是也可能面臨內(nèi)存不足的問題。

總結(jié)

以上是生活随笔為你收集整理的数据结构杂谈（五）——栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。