棧可以用順序表實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)，濃縮為以下兩張圖：

看不懂沒有關(guān)系，我會(huì)把它拆開來一個(gè)一個(gè)講。

一、概念

1、棧的定義

棧是僅限在表尾進(jìn)行插入和刪除的線性表。

棧又被稱為后進(jìn)先出（LastInFirstOut）的線性表，簡(jiǎn)稱LIFO。

2、棧頂

棧是一個(gè)線性表，我們把允許插入和刪除的一端稱為棧頂。

3、棧底

和棧頂相對(duì)，另一端稱為棧底，實(shí)際上，棧底的元素我們不需要關(guān)心。

二、接口

1、可寫接口

1）數(shù)據(jù)入棧

棧的插入操作，叫做入棧，也可稱為進(jìn)棧、壓棧。如下圖所示，代表了三次入棧操作：

2）數(shù)據(jù)出棧

棧的刪除操作，叫做出棧，也可稱為彈棧。如下圖所示，代表了兩次出棧操作：

3）清空棧

一直出棧，直到棧為空，如下圖所示：

2、只讀接口

1）獲取棧頂數(shù)據(jù)

對(duì)于一個(gè)棧來說只能獲取棧頂數(shù)據(jù)，一般不支持獲取其它數(shù)據(jù)。

2）獲取棧元素個(gè)數(shù)

棧元素個(gè)數(shù)一般用一個(gè)額外變量存儲(chǔ)，入棧時(shí)加一，出棧時(shí)減一。這樣獲取棧元素的時(shí)候就不需要遍歷整個(gè)棧。通過O(1)O(1)O(1)的時(shí)間復(fù)雜度獲取棧元素個(gè)數(shù)。

3）棧的判空

當(dāng)棧元素個(gè)數(shù)為零時(shí)，就是一個(gè)空棧，空棧不允許出棧操作。

三、棧的順序表實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)定義

對(duì)于順序表，在C語言中表現(xiàn)為數(shù)組，在進(jìn)行棧的定義之前，我們需要考慮以下幾個(gè)點(diǎn)：

1）棧數(shù)據(jù)的存儲(chǔ)方式，以及棧數(shù)據(jù)的數(shù)據(jù)類型；

2）棧的大??；

3）棧頂指針；

我們可以定義一個(gè)棧的結(jié)構(gòu)體，C語言實(shí)現(xiàn)如下所示：

#define DataType int        // (1)
#define maxn 100005         // (2)

struct Stack {              // (3)
    DataType data[maxn];    // (4)
    int top;                // (5)
};

(1)用DataType這個(gè)宏定義來統(tǒng)一代表?xiàng)Ｖ袛?shù)據(jù)的類型，這里將它定義為整型，根據(jù)需要可以定義成其它類型，例如浮點(diǎn)型、字符型、結(jié)構(gòu)體等等；

(2)maxn代表我們定義的棧的最大元素個(gè)數(shù)；

(3)Stack就是我們接下來會(huì)用到的棧結(jié)構(gòu)體；

(4)DataTypedata[maxn]作為棧元素的存儲(chǔ)方式，數(shù)據(jù)類型為DataType，可以自行定制；

(5)top即棧頂指針，data[top-1]表示棧頂元素，top==0代表空棧；

2、入棧

1、動(dòng)畫演示

如圖所示，藍(lán)色元素為原本在棧中的元素，紅色元素為當(dāng)前需要入棧的元素，執(zhí)行完畢以后，棧頂指針加一。具體來看下代碼實(shí)現(xiàn)。

2、源碼詳解

入棧操作，算上函數(shù)參數(shù)列表，總共也才幾句話，代碼實(shí)現(xiàn)如下：

void StackPushStack(struct Stack *stk, DataType dt) { // (1)
    stk->data[ stk->top ] = dt;                       // (2)
    stk->top = stk->top + 1;                          // (3)
}

(1)stk是一個(gè)指向棧對(duì)象的指針，由于這個(gè)接口會(huì)修改棧對(duì)象的成員變量，所以這里必須傳指針，否則，就會(huì)導(dǎo)致函數(shù)執(zhí)行完畢，傳參對(duì)象沒有任何改變；

(2)將傳參的元素放入棧中；

(3)將棧頂指針自增1；

注意，這個(gè)接口在調(diào)用前，需要保證棧頂指針小于棧元素最大個(gè)數(shù)，即stk->top<maxn，

如果C語言寫的熟練，我們可以把(2)(2)(2)和(3)(3)(3)合成一句話，如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;                    
}

stk->top++表達(dá)式的值是自增前的值，并且自身進(jìn)行了一次自增。

3、出棧

1、動(dòng)畫演示

如圖所示，藍(lán)色元素為原本在棧中的元素，紅色元素為當(dāng)前需要出棧的元素，執(zhí)行完畢以后，棧頂?shù)闹羔槣p一。具體來看下代碼實(shí)現(xiàn)。

2、源碼詳解

出棧操作，只需要簡(jiǎn)單改變將棧頂減一即可，代碼實(shí)現(xiàn)如下：

void StackPopStack(struct Stack* stk) {
    --stk->top;
}

4、清空棧

1、動(dòng)畫演示

如圖所示，對(duì)于數(shù)組來說，清空棧的操作只需要將棧頂指針置為棧底，也就是數(shù)組下標(biāo)0即可，下次繼續(xù)入棧的時(shí)候會(huì)將之前的內(nèi)存重復(fù)利用。

2、源碼詳解

清空棧的操作只需要將棧頂指針直接指向棧底即可，對(duì)于順序表，也就是C語言中的數(shù)組來說，棧底就是下標(biāo)0的位置了，代碼實(shí)現(xiàn)如下：

void StackClear(struct Stack* stk) {
    stk->top = 0;
}

5、只讀接口

只讀接口包含：獲取棧頂元素、獲取棧大小、棧的判空，實(shí)現(xiàn)如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];      // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->top;                       // (2)
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);             // (3)
}

(1)數(shù)組中棧元素從0開始計(jì)數(shù)，所以實(shí)際獲取元素時(shí)，下標(biāo)為棧頂元素下標(biāo)減一；

(2)因?yàn)橹挥性谌霔５臅r(shí)候，棧頂指針才會(huì)加一，所以它正好代表了棧元素個(gè)數(shù)；

(3)當(dāng)棧元素個(gè)數(shù)為零時(shí)，棧為空。

6、棧的順序表實(shí)現(xiàn)源碼

棧的順序表實(shí)現(xiàn)的源碼如下：

/************************************* 棧的順序表實(shí)現(xiàn) *************************************/
#define DataType int
#define bool int
#define maxn 100010

struct Stack {
    DataType data[maxn];
    int top;
};

void StackClear(struct Stack* stk) {
    stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
    --stk->top;
}
DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
    return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}
/************************************* 棧的順序表實(shí)現(xiàn) *************************************/

四、棧的鏈表實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)定義

對(duì)于鏈表，在進(jìn)行棧的定義之前，我們需要考慮以下幾個(gè)點(diǎn)： 1）棧數(shù)據(jù)的存儲(chǔ)方式，以及棧數(shù)據(jù)的數(shù)據(jù)類型； 2）棧的大?。?3）棧頂指針；

我們可以定義一個(gè)棧的結(jié)構(gòu)體，C語言實(shí)現(xiàn)如下所示：

typedef int DataType;             // (1)
struct StackNode;                 // (2)
struct StackNode {                // (3)
    DataType data;
    struct StackNode *next;
};
struct Stack {                    
    struct StackNode *top;        // (4)
    int size;                     // (5)
};

(1)棧結(jié)點(diǎn)元素的數(shù)據(jù)域，這里定義為整型；

(2)structStackNode;是對(duì)鏈表結(jié)點(diǎn)的聲明；

(3)定義鏈表結(jié)點(diǎn)，其中DataTypedata代表數(shù)據(jù)域；structStackNode*next代表指針域；

(4)top作為棧頂指針，當(dāng)棧為空的時(shí)候，top==NULL；否則，永遠(yuǎn)指向棧頂；

(5)由于求鏈表長(zhǎng)度的算法時(shí)間復(fù)雜度是O(n)O(n)O(n)的，所以我們需要記錄一個(gè)size來代表現(xiàn)在棧中有多少元素。每次入棧時(shí)size自增，出棧時(shí)size自減。這樣在詢問棧的大小的時(shí)候，就可以通過O(1)O(1)O(1)的時(shí)間復(fù)雜度。

2、入棧

1、動(dòng)畫演示

如圖所示，head為棧頂，tail為棧底，vtx為當(dāng)前需要入棧的元素，即圖中的橙色結(jié)點(diǎn)。入棧操作完成后，棧頂元素變?yōu)関tx，即圖中綠色結(jié)點(diǎn)。

2、源碼詳解

入棧操作，其實(shí)就是類似頭插法，往鏈表頭部插入一個(gè)新的結(jié)點(diǎn)，代碼實(shí)現(xiàn)如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) ); // (1)
    insertNode->next = stk->top;     // (2)
    insertNode->data = dt;           // (3)
    stk->top = insertNode;           // (4)
    ++ stk->size;                    // (5)
}

1)利用malloc生成一個(gè)鏈表結(jié)點(diǎn)insertNode；

(2)將當(dāng)前棧頂作為insertNode的后繼結(jié)點(diǎn)；

(3)將insertNode的數(shù)據(jù)域設(shè)置為傳參dt；

(4)將insertNode作為新的棧頂；

(5)棧元素加一；

3、出棧

1、動(dòng)畫演示

如圖所示，head為棧頂，tail為棧底，temp為當(dāng)前需要出棧的元素，即圖中的橙色結(jié)點(diǎn)。出棧操作完成后，棧頂元素變?yōu)橹癶ead的后繼結(jié)點(diǎn)，即圖中綠色結(jié)點(diǎn)。

2、源碼詳解

出棧操作，由于鏈表頭結(jié)點(diǎn)就是棧頂，其實(shí)就是刪除這個(gè)鏈表的頭結(jié)點(diǎn)的過程。代碼實(shí)現(xiàn)如下：

void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;  // (1)
    stk->top = temp->next;              // (2)
    free(temp);                         // (3)
    --stk->size;                        // (4)    
}

(1)將棧頂指針保存到temp中；

(2)將棧頂指針的后繼結(jié)點(diǎn)作為新的棧頂；

(3)釋放之前棧頂指針對(duì)應(yīng)的內(nèi)存；

(4)棧元素減一；

4、清空棧

1、動(dòng)畫演示

清空?？梢岳斫鉃?，不斷的出棧，直到棧元素個(gè)數(shù)為零。

2、源碼詳解

對(duì)于鏈表而言，清空棧的操作需要?jiǎng)h除每個(gè)鏈表結(jié)點(diǎn)，代碼實(shí)現(xiàn)如下：

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {       // (1)
        StackPopStack(stk);           // (2)
    }
    stk->top = NULL;                  // (3)
}

(1)-(2)的每次操作其實(shí)就是一個(gè)出棧的過程，如果棧不為空；則進(jìn)行出棧操作，直到棧為空；

(2)然后將棧頂指針置為空，代表這是一個(gè)空棧了；

5、只讀接口

只讀接口包含：獲取棧頂元素、獲取棧大小、棧的判空，實(shí)現(xiàn)如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;                 // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->size;                      // (2)
}
int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

(1)stk->top作為棧頂指針，它的數(shù)據(jù)域data就是棧頂元素的值，返回即可；

(2)size記錄的是棧元素個(gè)數(shù)；

(3)當(dāng)棧元素個(gè)數(shù)為零時(shí)，棧為空。

6、棧的鏈表實(shí)現(xiàn)源碼

棧的鏈表實(shí)現(xiàn)源碼如下：

/************************************* 棧的鏈表實(shí)現(xiàn) *************************************/
typedef int DataType;
struct StackNode;
struct StackNode {
    DataType data;
    struct StackNode *next;
};
struct Stack {
    struct StackNode *top;
    int size;
};
void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
    insertNode->next = stk->top;
    insertNode->data = dt;
    stk->top = insertNode;
    ++ stk->size;
}
void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;
    stk->top = temp->next;
    --stk->size; 
    free(temp);
}
DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
    return stk->size;
}
int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}
void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {
        StackPopStack(stk);
    }
    stk->top = NULL; 
    stk->size = 0;
}
/************************************* 棧的鏈表實(shí)現(xiàn) *************************************/

五、兩種實(shí)現(xiàn)的優(yōu)缺點(diǎn)

1、順序表實(shí)現(xiàn)

在利用順序表實(shí)現(xiàn)棧時(shí)，入棧和出棧的常數(shù)時(shí)間復(fù)雜度低，且清空棧操作相比鏈表實(shí)現(xiàn)能做到O(1)O(1)O(1)，唯一的不足之處是：需要預(yù)先申請(qǐng)好空間，而且當(dāng)空間不夠時(shí)，需要進(jìn)行擴(kuò)容，擴(kuò)容方式本文未提及，可以參考腳本之家其他相關(guān)文章。

2、鏈表實(shí)現(xiàn)

在利用鏈表實(shí)現(xiàn)棧時(shí)，入棧和出棧的常數(shù)時(shí)間復(fù)雜度略高，主要是每插入一個(gè)棧元素都需要申請(qǐng)空間，每刪除一個(gè)棧元素都需要釋放空間，且清空棧操作是O(n)O(n)O(n)的，直接將棧頂指針置空會(huì)導(dǎo)致內(nèi)存泄漏。好處就是：不需要預(yù)先分配空間，且在內(nèi)存允許范圍內(nèi)，可以一直入棧，沒有順序表的限制。

關(guān)于「?！沟膬?nèi)容到這里就結(jié)束了。如果還有不懂的問題，可以想方設(shè)法找到作者的聯(lián)系方式，線上溝通交流,希望大家以后多多支持腳本之家！