1.定義
棧(stack)是一個(gè)后進(jìn)先出(Last in first out,LIFO)的線(xiàn)性表，它要求只在表尾進(jìn)行刪除和插入操作掉冶。
棧在操作上有一些特殊的要求和限制:
- 棧的元素必須后進(jìn)先出
- 棧的操作只能在這個(gè)線(xiàn)性表的表尾進(jìn)行
- 對(duì)于棧來(lái)說(shuō)真竖，這個(gè)表尾成為棧的棧定(top),相應(yīng)的表頭稱(chēng)為棧底(bottom)
2.棧的插入和刪除操作
- 棧的插入操作(push)，叫做進(jìn)棧厌小，也成為壓棧恢共，入棧。
- 棧的刪除操作(pop),叫做出棧璧亚，也稱(chēng)為彈棧讨韭。
3. 棧的順序存儲(chǔ)結(jié)構(gòu)
因?yàn)闂５谋举|(zhì)是一個(gè)線(xiàn)性表，線(xiàn)性表有兩種存儲(chǔ)形式癣蟋，那么棧也有分為棧的順序存儲(chǔ)結(jié)構(gòu)和棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
最開(kāi)始棧中不含有任何數(shù)據(jù)透硝，叫做空棧，此時(shí)棧頂就是棧底疯搅。然后數(shù)據(jù)從棧頂進(jìn)入濒生，棧頂棧底分離，整個(gè)棧的當(dāng)前容量變大幔欧。數(shù)據(jù)出棧時(shí)從棧頂彈出罪治，棧頂下移，整個(gè)棧的當(dāng)前容量變小琐馆。
(1)棧的結(jié)構(gòu)定義
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct SqStack{
ElemType *base;//棧底
ElemType *top;//棧頂
int stackSize;
}SqStack;
(2)初始化一個(gè)空棧
Status initStack(SqStack *s){
s->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if (!(s->base)) {
return ERROR;
}
s->top = s->base;//最開(kāi)始规阀，棧頂就是棧底，代表它是一個(gè)空棧
s->stackSize = STACK_INIT_SIZE;
return OK;
}
(3)入棧操作
入棧操作又叫壓棧操作瘦麸，就是向棧中存放數(shù)據(jù)谁撼。
入棧操作要在棧頂進(jìn)行，每次向棧中壓入一個(gè)數(shù)據(jù)，top指針就要+1厉碟，直到棧滿(mǎn)為止
Status Push(SqStack *s,ElemType e){
//如果空間不夠喊巍，要?jiǎng)討B(tài)追加空間
if (s->top - s->base >= s->stackSize) {
s->base = (ElemType *)realloc(s->base, sizeof(ElemType)*(s->stackSize + STACKINCREMENT));
if (!s->base) {
return ERROR;
}
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}
//壓入值
*(s->top) = e;
//移動(dòng)棧頂指針
s->top++;
return OK;
}
(4)出棧操作
出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作箍鼓。
每當(dāng)從棧內(nèi)彈出一個(gè)數(shù)據(jù)崭参，棧的當(dāng)前容量就-1
Status Pop(SqStack *s,ElemType *e){
if (s->base == s->top) {
//空棧直接返回
return ERROR;
}
//先棧頂下移一位后再取值才是正確的
*e = *(--s->top);
return OK;
}
(5)清空一個(gè)棧
所謂清空一個(gè)棧，就是將棧中的元素全部作廢款咖，但棧本身物理空間并不發(fā)生改變（不是銷(xiāo)毀）何暮。
因此我們只要將s->top的內(nèi)容賦值為s->base即可，這樣s->base等于s->top铐殃，也就表明這個(gè)棧是空的了海洼。這個(gè)原理跟高級(jí)格式化只是但單純地清空文件列表而沒(méi)有覆蓋硬盤(pán)的原理是一樣的。
void clearStack(SqStack *s){
s->top = s->base;
}
(6)銷(xiāo)毀一個(gè)棧
銷(xiāo)毀一個(gè)棧與清空一個(gè)棧不同富腊，銷(xiāo)毀一個(gè)棧是要釋放掉該棧所占據(jù)的物理內(nèi)存空間
void DestroyStack(SqStack *s){
int length = s->stackSize;
for (int i = 0; i < length; i++) {
//循環(huán)將所有內(nèi)存都釋放
free(s->base++);
}
//將指針都置為空
s->base = s->top = NULL;
s->stackSize = 0;
}
(7)計(jì)算一個(gè)棧的當(dāng)前容量
計(jì)算棧的當(dāng)前容量也就是計(jì)算棧中元素的個(gè)數(shù)坏逢，因此只要返回s.top-s.base即可。
注意赘被，棧的最大容量是指該棧占據(jù)內(nèi)存空間的大小是整，其值是s.stackSize，它與棧的當(dāng)前容量不是一個(gè)概念哦民假。
int stackLenth(SqStack s){
//同類(lèi)型指針的相加減就是它們之間所隔的此類(lèi)元素的個(gè)數(shù)
return (int)(s.top - s.base);
}
4.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
通常我們用的都是棧的順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)浮入，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只作為一個(gè)知識(shí)點(diǎn)，有所了解就好羊异。
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)舵盈，簡(jiǎn)稱(chēng)棧鏈。
棧因?yàn)橹皇菞ｍ攣?lái)做插入和刪除操作球化，所以比較好的方法就是將棧頂放在單鏈表的頭部，棧頂指針和單鏈表的頭指針合二為一瓦糟。
(1)定義
typedef struct StackNode{
ElemType data;//存放棧的數(shù)據(jù)
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;//top指針
int count;//棧元素計(jì)數(shù)器
}LinkStack;
(2)進(jìn)棧操作
對(duì)于棧鏈的Push操作筒愚，假設(shè)元素值為e的新結(jié)點(diǎn)是s，top為棧頂指針菩浙，我們得到如下代碼:
Status Push(LinkStack *s,ElemType e){
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
if (!p) {
return ERROR;
}
p->data = e;
p->next = s->top;
s->top = p;
s->count++;
return OK;
}
(3)出棧操作
對(duì)于鏈棧的出棧Pop操作巢掺，假設(shè)變量P用來(lái)存儲(chǔ)要?jiǎng)h除的棧頂結(jié)點(diǎn)，將棧頂指針下移一位劲蜻，最后釋放p即可
Status Pop(LinkStack *s,ElemType *e){
if (s->count == 0 ) {
return ERROR;
}
LinkStackPtr p = s->top;
*e = p->data;
s->top = p->next;
free(p);
s->count--;
return OK;
}
