C語言深入探究棧的原理
棧
壓棧:棧的插入操作叫做進(jìn)棧/壓棧/入棧,入數(shù)據(jù)在棧頂。
出棧:棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
棧的實(shí)現(xiàn)
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn),相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的 代價(jià)比較小。如下圖:
下面用順序表(數(shù)組)來實(shí)現(xiàn)棧;
建立一個(gè)順序表結(jié)構(gòu):
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //表示棧頂
int capacity;//表示容量,當(dāng)容量滿時(shí),擴(kuò)容;
}ST;
創(chuàng)建一個(gè)結(jié)構(gòu)體變量:ST st;在傳數(shù)據(jù)之前要先初始化;不然當(dāng)你沒賦值就直接訪問時(shí)會(huì)出現(xiàn)亂碼或者報(bào)警告;
//初始化 void StackInit(ST* ps) { assert(ps);//斷言,保證傳進(jìn)來的非空; ps->a = NULL;//先將順序表指針指向空; ps->top = 0;//棧頂位置表示0位置; ps->capacity = 0;//容量為0; }
接下來就是向棧內(nèi)傳數(shù)據(jù)(壓棧),要傳結(jié)構(gòu)體地址和要傳的數(shù)據(jù);
//壓棧 void StackPush(ST* ps, STDataType x) { assert(ps); //判斷:數(shù)據(jù)從下標(biāo)0開始,因?yàn)閜ot表示該插入的棧頂?shù)奈恢?,也是壓棧的個(gè)數(shù) //一次插入一個(gè)數(shù)據(jù),所以數(shù)據(jù)數(shù)量與總?cè)萘肯嗤瑫r(shí),就需要擴(kuò)容 if (ps->top == ps->capacity) { //擴(kuò)容,擴(kuò)二倍 //使用三目運(yùn)算符判斷,當(dāng)是第一次擴(kuò)容時(shí),用二倍沒變化,所以固定開辟4個(gè)空間; int retcapa = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* ret = (STDataType*)realloc(ps->a, sizeof(STDataType)*retcapa); if (ret != NULL) { ps->a = ret; ps->capacity = retcapa; } else { printf("realloc開辟失敗,退出!"); exit(-1); } } //擴(kuò)容完,更新數(shù)據(jù); ps->a[ps->top] = x; ps->top++; }
有壓棧就有出棧;出棧用兩個(gè)接口。1.返回棧頂數(shù)據(jù) 2.出棧
因?yàn)橛袝r(shí)候只需要訪問棧頂數(shù)據(jù)不需要出棧,如果想出棧又想返回?cái)?shù)據(jù),就先調(diào)用1,再調(diào)用2;
//返回棧頂元素; STDataType StackTop(ST* ps) { assert(ps); //直接斷言要求棧中必須要有數(shù)據(jù); assert(ps->top > 0); return ps->a[ps->top - 1]; } //出棧,順序表直接把下標(biāo)減一即可 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
有時(shí)候還需要返回棧中元素
//返回棧中元素個(gè)數(shù); int StackSize(ST* ps) { assert(ps); return ps->top; }
在一些復(fù)雜結(jié)構(gòu)中要直接調(diào)用查看棧中是否有數(shù)據(jù),判斷棧是否為空;
//判斷棧中元素是否為空,返回布爾類型 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//注意這里是沒有數(shù)據(jù)是返回true; }
用動(dòng)態(tài)開辟的空間就必須手動(dòng)釋放
//釋放;順序表釋放頭指針即可 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
看一下如何調(diào)用的:
int main() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 4); StackPush(&st, 5); StackPush(&st, 7); printf("%d\n",StackTop(&st)); StackPop(&st); StackPush(&st, 8); printf("%d\n",StackTop(&st)); StackPop(&st); StackDestroy(&st); return 0; }
到此這篇關(guān)于C語言深入探究棧的原理的文章就介紹到這了,更多相關(guān)C語言 棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言中設(shè)置進(jìn)程優(yōu)先順序的方法
這篇文章主要介紹了C語言中設(shè)置進(jìn)程優(yōu)先順序的方法,包括setpriority()函數(shù)和getpriority()函數(shù)以及nice()函數(shù),需要的朋友可以參考下2015-08-08C語言實(shí)現(xiàn)可增容動(dòng)態(tài)通訊錄詳細(xì)過程
這篇文章主要為大家介紹了C語言實(shí)現(xiàn)簡(jiǎn)易通訊錄的完整流程,此通訊錄還可以增容,并且每個(gè)環(huán)節(jié)都有完整代碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-05-05C語言安全之?dāng)?shù)組長(zhǎng)度與指針實(shí)例解析
這篇文章主要介紹了C語言安全之?dāng)?shù)組長(zhǎng)度與指針,需要的朋友可以參考下2014-07-07緩存處理函數(shù)storageKeySuffix操作示例解析
這篇文章主要介紹了淺析緩存處理函數(shù)storageKeySuffix操作示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08C語言實(shí)現(xiàn)影院管理系統(tǒng)程序設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)影院管理系統(tǒng)程序設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08C++基于socket多線程實(shí)現(xiàn)網(wǎng)絡(luò)聊天室
這篇文章主要為大家詳細(xì)介紹了C++基于socket多線程實(shí)現(xiàn)網(wǎng)絡(luò)聊天室,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07