目錄

一、棧（先進后出、后進先出的線性表）

1、棧的概念及結構

2、棧的底層結構分析

二、代碼實現

1、定義一個棧

2、棧的初始化

3、入棧

3、增容

4、出棧

5、取棧頂

6、銷毀棧

---

一、棧（先進后出、后進先出的線性表）

1、棧的概念及結構

棧：一種特殊的線性表，只允許在固定的一端進行插入和刪除數據的操作。進行數據插入、刪除的一端為棧頂，不可進行操作的一端則是棧底。對于任意一個數據結構，我們都要分析一下它的邏輯結構和物理結構，既然是線性表，那么說明邏輯結構一定是線性的

邏輯結構：是線性的

物理結構：也是線性的

對于棧的操作主要有如下兩個：

一個是壓棧，另一個則是出棧。其中壓棧是棧的插入操作（也叫做進棧、入棧）；出棧則是棧的刪除操作，出數據也在棧頂。

2、棧的底層結構分析

既然我們已經對棧這一個數據結構的概念有了初步的了解，那么現在，我們來深入探討一下，棧的底層結構是什么？既然他是線性的，那么他是數組還是鏈表呢？

我們從這里分析：

我們可以從上圖看到鏈表的結構，由于棧只能從棧頂操作數據，假設棧的底層是鏈表，如果鏈表的尾部為棧頂的話，每一次訪問棧頂都要去遍歷一次鏈表，那么無疑使時間復雜度增加到了O(N)，相反，如果鏈表的頭部為棧頂，對數據進行插入刪除時的時間復雜度就會好很多，為O(1)。

我們來畫個圖看看數組，從數組中插入刪除數據，可以把數組的尾當做棧頂插入刪除數據，時間復雜度認為O(1)，既然這樣，鏈表和數組作為棧的底層結構，入棧和出棧的時間復雜度都為O(1)，那么，我們來換個維度來考慮：

以上是使用鏈表和數組結構寫的棧的構造代碼，我們可以看出，左圖中的結構使用了鏈表，每向棧中插入一個數據，空間不僅僅會增加int類型的4字節，還會增加指針8字節的大小，相比于數組結構，鏈表結構對空間的使用會更大，所以，我們還是更推薦用數組作為棧的底層結構。

二、代碼實現

下面，我們來實現一下棧的代碼：

1、定義一個棧

我們要定義一下棧的結構，由于棧的底層是數組，又要開辟空間，我們就定義一個動態的數組好了:

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;

2、棧的初始化

下面，我們來定義一個初始化方法：

void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

3、入棧

當要向數組插入數據首先要看棧中是否為空，若不為空，插入數據后ps->top要++，指向棧頂

3、增容

注意：這里又出現一個問題，當ps->top==ps->capacity時，說明空間已經不夠了，如果要繼續插入數據，我們需要進行一個增容操作：

這里，ps->capacity=newcapacity

void StackPush(ST* ps,STDatatype x)
{assert(ps);//這里做一個斷言操作，防止對空指針解引用if(ps->top == ps->capacity){int newcapacity = ps->capacity==0?4:2*ps->capacity;(STDataType*)tmp = (STDataType*)realloc(ps->arr,newcapacity*sizeof(STDataType));if(tmp == NULL){perror("realloc fail!");exit(1);    }ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

4、出棧

出棧操作：

每當遇到數據結構中的出數據操作時，我們都要考慮其是否有數據可以為我們所用，所以寫出棧操作之前，我們首先要判斷棧是否為空，這里，我們可以定義一個方法：

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;//判斷top（即有效數據個數是否為零，如果為零，則返回ture）
}

其次，假設，ps->top，不為零，則出棧操作直接可以寫成--ps->top；

void Stackpop(ST* ps)
{assert(ps);if(!StackEmpty(ps)){--ps->top;    }
}

5、取棧頂

下一個操作是：取棧頂操作，與出棧頂（有效的數據個數會減少）操作不同，去棧頂操作不會刪除數據，而只是將棧頂的數據復制一下并使用。

STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps);return ps->arr[ps->top-1];
}

6、銷毀棧

接下來，我們看一下對于棧的銷毀操作：

void StackDestroy(ST* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;//這里有一點ps->top = ps->capacity = 0;
}

這里有一個小tips：將ps->arr = NULL，這里可能有同學會有疑問，為什么寫出棧操作時，只需要--ps->top，不需要將數據free，這是因為，在數組中，arr表示數組首元素的地址，如果你將ps->arr free掉，那么整個數組的數據都會被銷毀，而鏈表的每一個空間都是獨立存在的，假設你將上一個結點的空間銷毀了，不會影響下一個結點，數組則不然。

以下是測試代碼：

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"void test01()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);/*StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);*//*while (!StackEmpty(&st)){int top = StackTop(&st);printf("%d ", top);StackPop(&st);}*/int size = StackSize(&st);printf("size:%d", size);StackDestroy(&st);
}int main()
{test01();return 0;
}