目錄

1.棧

1.1棧的概念及結(jié)構(gòu)

2.棧的實現(xiàn)?

3.棧結(jié)構(gòu)對數(shù)據(jù)的處理方式?

3.1對棧進行初始化

?

3.2 從棧頂添加元素

3.3 打印棧元素

3.4移除棧頂元素

3.5獲取棧頂元素?

3.6獲取棧中的有效個數(shù)

3.7 判斷鏈表是否為空

3.9 銷毀?？臻g

4.結(jié)語及整個源碼

---

1.棧

1.1棧的概念及結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。

進行數(shù)據(jù)插入和刪除操作的一端 稱為棧頂，另一端稱為棧底。

棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。 ?

棧中的數(shù)據(jù)后面進的先出，也就是說不能夠任意訪問，添加和刪除數(shù)據(jù)只能在棧頂進行操作。

入棧過程圖解：

?

出棧過程圖解：

2.棧的實現(xiàn)?

棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的 代價比較小.不用去修改指針

使用數(shù)組實現(xiàn)圖解：

使用鏈表實現(xiàn)圖解：

?

實現(xiàn)棧最好的方式就是使用數(shù)組的方式來實現(xiàn)：

靜態(tài)數(shù)組定義棧的方式：

typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 棧頂
}Stack;

但是由于空間指定的問題，實際使用較小，所以最適合棧的實現(xiàn)方式就是：動態(tài)數(shù)組定義棧?

動態(tài)數(shù)組定義棧的方式：

?

typedef int STDataType;//直接定義動態(tài)版本的棧  棧頂表示就是要插入
typedef struct  Stack
{STDataType* arr;//定義指向?？臻g的指針int top;//棧頂int capcity;//定義容量}Stack;

3.棧結(jié)構(gòu)對數(shù)據(jù)的處理方式?

3.1對棧進行初始化

首先用戶創(chuàng)建一個棧變量過后，我們就要將這個棧首先初始化，方便后續(xù)用棧來管理數(shù)據(jù)。

在初始化動作中，指向?？臻g的指針應(yīng)該置空，后續(xù)開辟空間的時候再給定值。容量最初也是0，無可爭議。但是對于棧頂?shù)亩x要注意初始值的區(qū)別。

top棧頂后續(xù)會用于訪問棧頂元素也就是作為我們數(shù)組的下標(biāo)，如果初始為1，此時棧里面是沒有元素的，那么后續(xù)進入數(shù)據(jù)就要注意，棧的大小是top的大小。如果開始為0，棧的大小是top+1.當(dāng)然這里大家自己實現(xiàn)的時候自由選擇定義就好：

void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}

?

3.2 從棧頂添加元素

首先：先斷言一下我們傳入的結(jié)構(gòu)體指針，看是否存在這樣一個棧結(jié)構(gòu)，再開始后續(xù)操作。

第二：添加元素前我們就要考慮我們這個棧的空間還夠不夠，不夠就要進行擴容。這里由于開始的時候，指向棧空間的指針為空，所以realloc函數(shù)會直接開辟空間，所以就沒有malloc單獨申請空間了。

第三：將對應(yīng)的容量增加，top增加，將我們每個值賦值。

void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}

3.3 打印棧元素

使用遍歷的方法打印?？臻g中的每一個元素。

void  StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}

我們來測試一下剛才的入棧：?

3.4移除棧頂元素

也就是順序表中的尾部刪除

首先還是要斷言一下傳入的指針是否為空

第二，我們移除尾部元素，并不是把尾部元素置空，只是將top--,那么就訪問不到那個元素，后續(xù)增加元素就會覆蓋，容量也沒有必要減去了。其次，每次top--,那么就要判斷一下top減為或者已經(jīng)小于0了就不執(zhí)行了。

?

void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top減為0了就別在減去了pc->top--;
}

?

3.5獲取棧頂元素?

獲取棧頂元素，就是通過top作為下標(biāo)來訪問我們的尾部元素，注意如果top初始值為0，那么直接使用我們的top作為下標(biāo)即可，但是由于我們每次添加元素后都要++,所以要-1，如果是以1為top的初始值，那么此時的top需要-2.

STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}

?

3.6獲取棧中的有效個數(shù)

也就是我們top?

int StackSize(Stack* pc)
{assert(pc);return pc->top;
}

.

3.7 判斷鏈表是否為空

我們可以判斷此時的容量是否為空，因為就是top為0，但是棧依舊存在，只是無法訪問每個元素。

bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}

3.9 銷毀?？臻g

我們的空間是在堆區(qū)上申請來的，用完記得銷毀還給操作系統(tǒng)，不讓后續(xù)造成內(nèi)存泄漏。

void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}

4.結(jié)語及整個源碼

以上就是本期的所有內(nèi)容，知識含量蠻多，大家可以配合解釋和原碼運行理解。創(chuàng)作不易，大家如果覺得還可以的話，歡迎大家三連，有問題的地方歡迎大家指正，一起交流學(xué)習(xí)，一起成長，我是Nicn，正在c++方向前行的奮斗者，數(shù)據(jù)結(jié)構(gòu)內(nèi)容持續(xù)更新中，感謝大家的關(guān)注與喜歡。

附上源碼：

test.c

#include"stack.h"
int main()
{//創(chuàng)建棧Stack stack = { 0 };//初始化棧SInit(&stack);StackPush(&stack, 1);StackPush(&stack, 2);StackPush(&stack, 3);StackPush(&stack, 4);StackPrint(&stack);printf("\n");StackPop(&stack);StackPrint(&stack);printf("\n");/*printf("%d ", StackTop(&stack));*/printf("%d ", StackSize(&stack));return 0;
}

stack.c

#include"stack.h"void SInit(Stack* pc)
{pc->arr = NULL;pc->capcity = 0;pc->top = 0;
}void StackPush(Stack* pc, STDataType data)
{assert(pc);if (pc->top ==pc->capcity){STDataType* a = (STDataType*)realloc(pc->arr, (pc->capcity+2)*sizeof(STDataType) );if (a == NULL){perror("realloc");}pc->arr = a;pc->capcity+=2;}pc->arr[pc->top] = data;pc->top++;}void  StackPrint(Stack* pc){assert(pc);int i = 0;for (i = 0; i < pc->top; i++){printf("%d ", pc->arr[i]);}
}void StackPop(Stack* pc)
{assert(pc);assert(pc->top > 0);//top減為0了就別在減去了pc->top--;
}STDataType StackTop(Stack* pc)
{assert(pc);return pc->arr[pc->top-1];
}
bool StackEmpty(Stack* pc)
{assert(pc);return pc->capcity == 0;
}int StackSize(Stack* pc)
{assert(pc);return pc->top;
}void StackDestory(Stack* pc)
{assert(pc);free(pc->arr);pc->arr == NULL;pc->top = pc->capcity = 0;
}

stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;//直接定義動態(tài)版本的棧  棧頂表示就是要插入
typedef struct  Stack
{STDataType* arr;//定義指向?？臻g的指針int top;//棧頂int capcity;//定義容量}Stack;void SInit(Stack* pc);
//入棧
void StackPush(Stack* pc, STDataType data);
//出棧
void StackPop(Stack* pc);
//獲取棧頂元素
STDataType StackTop(Stack* pc);
//檢查棧是否為空
bool StackEmpty(Stack* pc);
//棧的大小
int StackSize(Stack* pc);
//打印
void  StackPrint(Stack* pc);
//銷毀棧
void StackDestory(Stack* pc);

?