?？梢杂庙樞虮韺崿F(xiàn)，也可以用鏈表實現(xiàn)，濃縮為以下兩張圖：

看不懂沒有關系，我會把它拆開來一個一個講。

一、概念

1、棧的定義

棧是僅限在表尾進行插入和刪除的線性表。

棧又被稱為后進先出（LastInFirstOut）的線性表，簡稱LIFO。

2、棧頂

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

3、棧底

和棧頂相對，另一端稱為棧底，實際上，棧底的元素我們不需要關心。

二、接口

1、可寫接口

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

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

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

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

3）清空棧

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

2、只讀接口

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

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

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

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

3）棧的判空

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

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

1、數(shù)據(jù)結構定義

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

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

2）棧的大小；

3）棧頂指針；

我們可以定義一個棧的結構體，C語言實現(xiàn)如下所示：

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

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

(1)用DataType這個宏定義來統(tǒng)一代表棧中數(shù)據(jù)的類型，這里將它定義為整型，根據(jù)需要可以定義成其它類型，例如浮點型、字符型、結構體等等；

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

(3)Stack就是我們接下來會用到的棧結構體；

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

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

2、入棧

1、動畫演示

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

2、源碼詳解

入棧操作，算上函數(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是一個指向棧對象的指針，由于這個接口會修改棧對象的成員變量，所以這里必須傳指針，否則，就會導致函數(shù)執(zhí)行完畢，傳參對象沒有任何改變；

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

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

注意，這個接口在調用前，需要保證棧頂指針小于棧元素最大個數(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++表達式的值是自增前的值，并且自身進行了一次自增。

3、出棧

1、動畫演示

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

2、源碼詳解

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

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

4、清空棧

1、動畫演示

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

2、源碼詳解

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

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

5、只讀接口

只讀接口包含：獲取棧頂元素、獲取棧大小、棧的判空，實現(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開始計數(shù)，所以實際獲取元素時，下標為棧頂元素下標減一；

(2)因為只有在入棧的時候，棧頂指針才會加一，所以它正好代表了棧元素個數(shù)；

(3)當棧元素個數(shù)為零時，棧為空。

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

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

/************************************* 棧的順序表實現(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);
}
/************************************* 棧的順序表實現(xiàn) *************************************/

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

1、數(shù)據(jù)結構定義

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

我們可以定義一個棧的結構體，C語言實現(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)棧結點元素的數(shù)據(jù)域，這里定義為整型；

(2)structStackNode;是對鏈表結點的聲明；

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

(4)top作為棧頂指針，當棧為空的時候，top==NULL；否則，永遠指向棧頂；

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

2、入棧

1、動畫演示

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

2、源碼詳解

入棧操作，其實就是類似頭插法，往鏈表頭部插入一個新的結點，代碼實現(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生成一個鏈表結點insertNode；

(2)將當前棧頂作為insertNode的后繼結點；

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

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

(5)棧元素加一；

3、出棧

1、動畫演示

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

2、源碼詳解

出棧操作，由于鏈表頭結點就是棧頂，其實就是刪除這個鏈表的頭結點的過程。代碼實現(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)將棧頂指針的后繼結點作為新的棧頂；

(3)釋放之前棧頂指針對應的內存；

(4)棧元素減一；

4、清空棧

1、動畫演示

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

2、源碼詳解

對于鏈表而言，清空棧的操作需要刪除每個鏈表結點，代碼實現(xiàn)如下：

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

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

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

5、只讀接口

只讀接口包含：獲取棧頂元素、獲取棧大小、棧的判空，實現(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記錄的是棧元素個數(shù)；

(3)當棧元素個數(shù)為零時，棧為空。

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

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

/************************************* 棧的鏈表實現(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;
}
/************************************* 棧的鏈表實現(xiàn) *************************************/

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

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

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

2、鏈表實現(xiàn)

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

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