目錄

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

2.棧的實(shí)現(xiàn)

2.1棧結(jié)構(gòu)定義

2.2初始化及銷(xiāo)毀

2.3插入數(shù)據(jù)

2.4刪除數(shù)據(jù)

2.5訪問(wèn)棧頂數(shù)據(jù)

2.6判斷是否為空棧

2.7計(jì)算棧的大小

3.8訪問(wèn)棧中所有數(shù)據(jù)

---

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

棧：棧是一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除操作

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

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

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

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

如下圖為一個(gè)棧的結(jié)構(gòu)：

上圖中入棧順序?yàn)?#xff1a;123456789

出棧順序?yàn)?#xff1a;987654321

區(qū)分?jǐn)?shù)據(jù)結(jié)構(gòu)中的棧和內(nèi)存中的棧：

內(nèi)存區(qū)域劃分：堆區(qū)，棧區(qū)，靜態(tài)區(qū)，常量區(qū)......

一般操作系統(tǒng)中的棧指的是內(nèi)存中的棧，數(shù)據(jù)結(jié)構(gòu)中的棧是可以插入刪除數(shù)據(jù)的棧

2.棧的實(shí)現(xiàn)

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，使用數(shù)組在尾插數(shù)據(jù)時(shí)的代價(jià)比較小，所以一般使用數(shù)組實(shí)現(xiàn)棧

2.1棧結(jié)構(gòu)定義

棧結(jié)構(gòu)的定義分為靜態(tài)開(kāi)辟和動(dòng)態(tài)開(kāi)辟兩種

靜態(tài)開(kāi)辟時(shí)棧的空間大小是固定的，所以一般情況我們使用動(dòng)態(tài)開(kāi)辟

動(dòng)態(tài)開(kāi)辟的棧結(jié)構(gòu)包括三個(gè)成員變量：數(shù)組指針，可以訪問(wèn)棧頂?shù)膖op，棧的當(dāng)前容量

📖Note:

我們創(chuàng)建的棧結(jié)構(gòu)是數(shù)組形式的，所以可以通過(guò)下標(biāo)訪問(wèn)，top即為時(shí)刻指向棧頂?shù)南聵?biāo)

top也可以看作為棧中實(shí)際元素的個(gè)數(shù)

typedef int  STDataType;
//靜態(tài)開(kāi)辟
#define N 100
struct Stack
{STDataType a[N];int top;
};//動(dòng)態(tài)內(nèi)存開(kāi)辟
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

2.2初始化及銷(xiāo)毀

初始化時(shí)對(duì)三個(gè)成員變量都要進(jìn)行初始化

數(shù)組指針初始化為NULL

top = 0，同時(shí)指向棧底和棧頂，top可以看作為棧中實(shí)際元素的個(gè)數(shù)，棧頂是動(dòng)態(tài)變化的，每次插入數(shù)據(jù)或刪除數(shù)據(jù)棧頂都會(huì)發(fā)生變化，而棧底是相對(duì)固定不變的

初始化時(shí)棧的容量為0，需要使用棧時(shí)再動(dòng)態(tài)開(kāi)辟空間

銷(xiāo)毀時(shí)同樣對(duì)三個(gè)結(jié)構(gòu)成員分別置空或置0

//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
//銷(xiāo)毀
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

2.3插入數(shù)據(jù)

插入數(shù)據(jù)首先要擴(kuò)容，第一次插入我們開(kāi)辟4個(gè)空間(根據(jù)需求)，其他情況擴(kuò)容為原來(lái)的二倍

📖Note:

以下代碼中realloc的第二個(gè)參數(shù)應(yīng)該是newcapacity * sizeof(STDataType)而不newcapacity

使用realloc函數(shù)擴(kuò)容，第二個(gè)參數(shù)的單位是字節(jié)，是我們開(kāi)辟空間的總字節(jié)數(shù)

擴(kuò)容失敗直接退出函數(shù)即可

擴(kuò)容成功才可以插入數(shù)據(jù)

數(shù)組形式的棧中數(shù)據(jù)訪問(wèn)通過(guò)下標(biāo)訪問(wèn)，棧結(jié)構(gòu)的特殊性使其只能在棧頂進(jìn)行數(shù)據(jù)的插入和刪除，而top正是時(shí)刻指向棧頂?shù)南聵?biāo)，所以使數(shù)據(jù)的插入和刪除更加方便

//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x)
{assert(ps);//擴(kuò)容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;STDataType* tmp = realloc(ps->a, newcapacity * sizeof(STDataType));//擴(kuò)容失敗if (tmp == NULL){perror("realloc fail");exit(-1);}//擴(kuò)容成功ps->a = tmp;ps->capacity = newcapacity;}//插入數(shù)據(jù)ps->a[ps->top] = x;ps->top++;
}

下圖是將12345一次壓棧后棧中的結(jié)構(gòu)?

2.4刪除數(shù)據(jù)

數(shù)據(jù)的刪除就更加方便，只要棧非空，指向棧頂?shù)膖op直接向棧底方向移動(dòng)一塊空間即可

//刪除數(shù)據(jù)
void StackPop(ST* ps)
{assert(ps);//棧不為空才能刪除assert(!StackEmpty(ps));--ps->top;
}

2.5訪問(wèn)棧頂數(shù)據(jù)

訪問(wèn)棧頂數(shù)據(jù)的前提也是棧非空

注意數(shù)組的下標(biāo)與元素的對(duì)應(yīng)關(guān)系，數(shù)組的下標(biāo)從0開(kāi)時(shí)，所以第n個(gè)元素對(duì)應(yīng)下標(biāo)n-1

//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{assert(ps);//棧不為空才能訪問(wèn)assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

2.6判斷是否為空棧

當(dāng)棧中實(shí)際元素的個(gè)數(shù)為0時(shí)，棧即為空棧

//判斷是否為空棧
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

2.7計(jì)算棧的大小

棧的大小即為棧中實(shí)際元素的個(gè)數(shù)，所以返回ps->top即可

//計(jì)算棧的大小
int StackSize(ST* ps) 
{assert(ps);return ps->top;
}

3.8訪問(wèn)棧中所有數(shù)據(jù)

棧中數(shù)據(jù)的訪問(wèn)只能從棧頂，當(dāng)棧非空時(shí)，每次訪問(wèn)棧頂元素即可，訪問(wèn)棧頂?shù)南乱粋€(gè)元素需要棧頂元素先出棧，直至棧為空停止訪問(wèn)

//訪問(wèn)棧中數(shù)據(jù)
void StackPopAll(ST* ps)
{while (!StackEmpty(ps)){printf("%d ", StackTop(ps));StackPop(ps);}printf("\n");
}

?