目錄

棧的概念及其結構

棧的實現

數組棧

鏈式棧

?棧的常見接口實現

主函數Test.c

頭文件&函數聲明Stack.h

頭文件

函數聲明

函數實現Stack.c

初始化SLInit

擴容Createcapacity

壓棧STPush

出棧STPop

棧頂元素STTop

判斷棧是否為空STempty

棧內元素個數STSzie

數組棧空間釋放STDestroy

數組棧總代碼?

---

我們已經學習過了【線性表】中的順序表和鏈表。今天開始進入棧和隊列。棧和隊列是順序表和鏈表的延續，也是一種線性表（線性表在邏輯上也是連續的）。大體結構上都很相似，所以大家學習起來也會很容易的。但是棧和隊列也有自己獨特的性質，學習也需要特別注意哦。

棧的概念及其結構

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

棧中的數據元素遵守 后進先出 / 后進先出 LIFO（Last In First Out）的原則

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。?

?

【先進后出/后進先出】可以類比【彈夾】

棧的實現

了解了棧的概念，如何實現棧呢？

根據前面博文我們可以【數組棧】和【鏈式棧】?

數組棧

數組棧比較簡單，也是快速容易實現，首先就是【數組棧】實現。

鏈式棧

鏈式棧分為【單鏈表】和【雙向鏈表】去實現棧。毋庸置疑，【雙向鏈表實現】棧頂可以是尾巴，也可以是頭，因為雙向鏈表的頭插/頭刪和尾插/尾刪都是很方便的。

但是為了節省資源，我們用【單鏈表】該怎樣去設計呢？

單鏈表實現棧：棧頂只能是單鏈表頭（頭插/頭刪易），棧底只能是單鏈表尾（頭刪很復雜）

?

?棧的常見接口實現

• 斷言NULL/Pop==0情況
• 改變結構體用指針
• top的指向
• 單個數據直接用，多個數據用結構體包含起來
• 數組的數據訪問用數組下標即可訪問
• pst和pst->a搞清楚！
• 入棧順序是只有一種，但是出棧順序有多種！！

主函數Test.c

#include"Stack.h"
int main()
{ST pst;//創建結構體STInit(&pst);//傳地址是修改結構體內部STPush(&pst, 1);STPush(&pst, 2);STPush(&pst, 3);STPush(&pst, 4);STPush(&pst, 5);while (!STempty(&pst)){printf("%d ", STTop(&pst));STPop(&pst);}STDestroy(&pst);
}

由于棧是其只允許在固定的一端進行插入和刪除元素操作。所以棧的訪問是必須先Pop彈出元素才能訪問下一個元素。

	while (!STempty(&pst)){printf("%d ", STTop(&pst));STPop(&pst);}

頭文件&函數聲明Stack.h

頭文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

函數聲明

• 創建結構體

typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;

• 初始化

void STInit(ST* pst);

• 釋放銷毀

void STDestroy(ST* pst);

• 壓棧

void STPush(ST* pst, STDatatype x);

• 出棧

void STPop(ST* pst);

• 棧頂元素

STDatatype STTop(ST* pst);

• 判斷棧是否為NULL

bool STempty(ST* pst);

• 棧內的元素個數?

int STSize(ST* pst);

函數實現Stack.c

初始化SLInit

?如果初始化 top=0：表示棧內元素的個數。作為a[top]指針指向棧頂元素的下一個。

?如果初始化 top=-1：表示數組元素的下標。作為a[top]指針指向棧頂元素。?

#include"Stack.h"
void STInit(ST* pst)
{assert(pst);pst->a = 0;
//表示top指向棧頂元素的下一個位置pst->top = 0;
//表示top指向棧頂元素//pst->top = -1;pst->capacity = 0;
}

擴容Createcapacity

void Createcapacity(ST* pst)
{//擴容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}
}

壓棧STPush

void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst->a[pst->top] = x;pst->top++;
}

出棧STPop

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

棧頂元素STTop

STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}

判斷棧是否為空STempty

bool STempty(ST* pst)
{assert(pst);return pst->top == 0;//為0就是true 為！=0就是為flase
}

棧內元素個數STSzie

int STSize(ST* pst)
{assert(pst);return pst->top;
}

數組棧空間釋放STDestroy

void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}

數組棧總代碼?

//Test.c
#include"Stack.h"
int main()
{ST pst;STInit(&pst);STPush(&pst, 1);STPush(&pst, 2);STPush(&pst, 3);STPush(&pst, 4);STPush(&pst, 5);while (!STempty(&pst)){printf("%d ", STTop(&pst));STPop(&pst);}STDestroy(&pst);
}
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
//Stack.c
#include"Stack.h"
void STInit(ST* pst)
{assert(pst);pst->a = 0;pst->top = 0;pst->capacity = 0;
}void Createcapacity(ST* pst)
{//擴容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}bool STempty(ST* pst)
{assert(pst);return pst->top == 0;//為0就是true 為！=0就是為flase
}int STSize(ST* pst)
{assert(pst);return pst->top;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}

?????最后，感謝大家的閱讀，若有錯誤和不足，歡迎指正！各位小伙伴乖乖敲代碼哦。?

代碼---------→【唐棣棣 (TSQXG) - Gitee.com】

聯系---------→【郵箱：2784139418@qq.com】