諸城網(wǎng)站建設(shè)電子商務(wù)網(wǎng)店運營推廣
目錄
1.棧的概念及結(jié)構(gòu)
2.棧的實現(xiàn)
2.1棧結(jié)構(gòu)定義
2.2初始化及銷毀
2.3插入數(shù)據(jù)
2.4刪除數(shù)據(jù)
2.5訪問棧頂數(shù)據(jù)
2.6判斷是否為空棧
2.7計算棧的大小
3.8訪問棧中所有數(shù)據(jù)
1.棧的概念及結(jié)構(gòu)
棧:棧是一種特殊的線性表,其只允許在固定的一端進行插入和刪除操作
進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂,另一端稱為棧底
棧中的數(shù)據(jù)元素遵守后進先出LIFO(Last? In First Out)的原則
壓棧:棧的插入操作叫做進棧/壓棧/入棧,插入數(shù)據(jù)在棧頂
出棧:棧的刪除操作叫做出棧,刪除數(shù)據(jù)也在棧頂
如下圖為一個棧的結(jié)構(gòu):
上圖中入棧順序為:123456789
出棧順序為: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.棧的實現(xiàn)
棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn),使用數(shù)組在尾插數(shù)據(jù)時的代價比較小,所以一般使用數(shù)組實現(xiàn)棧
2.1棧結(jié)構(gòu)定義
棧結(jié)構(gòu)的定義分為靜態(tài)開辟和動態(tài)開辟兩種
靜態(tài)開辟時棧的空間大小是固定的,所以一般情況我們使用動態(tài)開辟
動態(tài)開辟的棧結(jié)構(gòu)包括三個成員變量:數(shù)組指針,可以訪問棧頂?shù)膖op,棧的當(dāng)前容量
📖Note:
我們創(chuàng)建的棧結(jié)構(gòu)是數(shù)組形式的,所以可以通過下標(biāo)訪問,top即為時刻指向棧頂?shù)南聵?biāo)
top也可以看作為棧中實際元素的個數(shù)
typedef int STDataType;
//靜態(tài)開辟
#define N 100
struct Stack
{STDataType a[N];int top;
};//動態(tài)內(nèi)存開辟
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
2.2初始化及銷毀
初始化時對三個成員變量都要進行初始化
數(shù)組指針初始化為NULL
top = 0,同時指向棧底和棧頂,top可以看作為棧中實際元素的個數(shù),棧頂是動態(tài)變化的,每次插入數(shù)據(jù)或刪除數(shù)據(jù)棧頂都會發(fā)生變化,而棧底是相對固定不變的
初始化時棧的容量為0,需要使用棧時再動態(tài)開辟空間
銷毀時同樣對三個結(jié)構(gòu)成員分別置空或置0
//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
//銷毀
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
2.3插入數(shù)據(jù)
插入數(shù)據(jù)首先要擴容,第一次插入我們開辟4個空間(根據(jù)需求),其他情況擴容為原來的二倍
📖Note:
以下代碼中realloc的第二個參數(shù)應(yīng)該是newcapacity * sizeof(STDataType)而不newcapacity
使用realloc函數(shù)擴容,第二個參數(shù)的單位是字節(jié),是我們開辟空間的總字節(jié)數(shù)
擴容失敗直接退出函數(shù)即可
擴容成功才可以插入數(shù)據(jù)
數(shù)組形式的棧中數(shù)據(jù)訪問通過下標(biāo)訪問,棧結(jié)構(gòu)的特殊性使其只能在棧頂進行數(shù)據(jù)的插入和刪除,而top正是時刻指向棧頂?shù)南聵?biāo),所以使數(shù)據(jù)的插入和刪除更加方便
//插入數(shù)據(jù)
void StackPush(ST* ps, STDataType x)
{assert(ps);//擴容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;STDataType* tmp = realloc(ps->a, newcapacity * sizeof(STDataType));//擴容失敗if (tmp == NULL){perror("realloc fail");exit(-1);}//擴容成功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直接向棧底方向移動一塊空間即可
//刪除數(shù)據(jù)
void StackPop(ST* ps)
{assert(ps);//棧不為空才能刪除assert(!StackEmpty(ps));--ps->top;
}
2.5訪問棧頂數(shù)據(jù)
訪問棧頂數(shù)據(jù)的前提也是棧非空
注意數(shù)組的下標(biāo)與元素的對應(yīng)關(guān)系,數(shù)組的下標(biāo)從0開時,所以第n個元素對應(yīng)下標(biāo)n-1
//訪問棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{assert(ps);//棧不為空才能訪問assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
2.6判斷是否為空棧
當(dāng)棧中實際元素的個數(shù)為0時,棧即為空棧
//判斷是否為空棧
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
2.7計算棧的大小
棧的大小即為棧中實際元素的個數(shù),所以返回ps->top即可
//計算棧的大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
3.8訪問棧中所有數(shù)據(jù)
棧中數(shù)據(jù)的訪問只能從棧頂,當(dāng)棧非空時,每次訪問棧頂元素即可,訪問棧頂?shù)南乱粋€元素需要棧頂元素先出棧,直至棧為空停止訪問
//訪問棧中數(shù)據(jù)
void StackPopAll(ST* ps)
{while (!StackEmpty(ps)){printf("%d ", StackTop(ps));StackPop(ps);}printf("\n");
}
?