1.棧的概念及結構

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

此圖來源與網絡

這里我們可以比作肉串,我們先把肉串好,后串上的肉,是先吃的.

2.棧的實現

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

這里我就用數組來實現一下,感興趣的可以用鏈表實現一下

個人感覺這個的寫法比較類似順序表

我們先創建棧,然后定義相應的功能

Stack.h#pragma once
// 支持動態增長的棧
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 棧頂int _capacity;  // 容量 
}Stack;
// 初始化棧 
void StackInit(Stack* ps);
// 入棧 
void StackPush(Stack* ps, STDataType data);
// 出棧 
void StackPop(Stack* ps);
// 獲取棧頂元素 
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數 
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 
int StackEmpty(Stack* ps);
// 銷毀棧 
void StackDestroy(Stack* ps);

? ?注意:棧只能從后面入棧,從后面出棧.

#include"Stack.h"
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++;
}
bool STEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
void StackPop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
int STSize(Stack* ps)
{assert(ps);return ps->top;
}

最后我們來測試一下相關的功能

#include"Stack.h"
int main()
{Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);int top = StackTop(&s);printf("%d ", top);StackPop(&s);StackPush(&s, 4);StackPush(&s, 5);while (!STEmpty(&s)){int top = StackTop(&s);printf("%d ", top);StackPop(&s);}StackDestroy(&s);return 0;
}

我們預期的結果是輸入的倒著的,所以結果應該是 3 5 4 2 1

我們運行一下:

所以這就是一個棧.

---

這會我們介紹了棧,并完成了相關的操作,如果有什么不懂,或者錯誤,歡迎指出.