文章轉(zhuǎn)自編程珠璣，作者：守望先生

前言

棧是一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)，例如函數(shù)的調(diào)用就需要使用棧，其實我們在介紹《

棧的操作

棧的常見操作有出棧(POP)，從棧中彈出一個元素；入棧(PUSH)，將一個元素壓入棧中，訪問棧頂元素(TOP)，判斷棧是否為空等。

棧的實現(xiàn)

棧是較容易實現(xiàn)的抽象數(shù)據(jù)結(jié)構(gòu)之一。我們可以選擇數(shù)組或者鏈表來實現(xiàn)，它們各有特點，前者容量有限且固定，但操作簡單，而后者容量理論上不受限，但是操作并不如數(shù)組方便，每次入棧要進(jìn)行內(nèi)存申請，出棧要釋放內(nèi)存，稍有不慎便造成內(nèi)存泄露。本文對兩種實現(xiàn)都做介紹。

數(shù)組實現(xiàn)棧

用數(shù)組實現(xiàn)棧是比較容易的。這個時候的棧其實更像是訪問受限的數(shù)組，數(shù)組可以通過下標(biāo)訪問，查找，插入等，但是棧只能從棧頂，或者說數(shù)組的末尾進(jìn)行操作。我們只需要一個指針記錄棧頂即可。有人可能問了，既然這里棧是訪問受限的數(shù)組，為什么不直接使用數(shù)組呢？所謂能力越大，責(zé)任越大，而你暴露的越多，風(fēng)險也越大就是如此。

我們來看一下數(shù)組實現(xiàn)棧的時候，棧的操作都是怎么實現(xiàn)的呢？

定義棧

用數(shù)組實現(xiàn)棧時是很容易定義的，只要定一個固定長度的數(shù)組即可，然后使用一個指針或者數(shù)組下標(biāo)標(biāo)記棧頂（topOfStack），棧為空時，它是-1：

#define?STACK_SIZE?64?/*棧大小*/ #define?TOP_OF_STACK?-1?/*棧頂位置*/ typedef?int?ElementType?/*棧元素類型*/ typedef?struct?StackInfo {int?topOfStack;?/*記錄棧頂位置*/ElementType?stack[STACK_SIZE];?/*棧數(shù)組，也可以使用動態(tài)數(shù)組實現(xiàn)*/ }StackInfo_st;/*創(chuàng)建棧*/ StackInfo_st?stack; stack.topOfStack?=?TOP_OF_STACK;

入棧

入棧操作也很簡單，只需要先將topOfStack加1，然后將元素放入數(shù)組即可。當(dāng)然特別要注意檢查此時棧是否已滿。

將1入棧，此時topOfStack = 0，

topOfStack

1

代碼實現(xiàn)：

#define?SUCCESS?0 #define?FAILURE?-1 /*入棧，0表示成功，非0表示出錯*/ int?stack_push(StackInfo_st?*s,?ElementType?value) {if(stack_is_full(s))return?FAILURE;/*先增加topOfStack，再賦值*/s->topOfStack++;s->stack[s->topOfStack]?=?value;return?SUCCESS; }

出棧或訪問棧頂元素

與入棧相反，先訪問元素，然后將topOfStack減1，但是此時要注意檢查棧是否已空。訪問棧頂元素可直接使用下標(biāo)訪問，而不用將topOfStack減1。

/*出棧*/ int?stack_pop(StackInfo_st?*s,ElementType?*value) {/*首先判斷棧是否為空*/if(stack_is_empty(s))return?FAILURE;*value?=?s->stack[s->topOfStack];s->topOfStack--;return?SUCCESS; } /*訪問棧頂元素*/ int?stack_top(StackInfo_st?*s,ElementType?*value); {/*首先判斷棧是否為空*/if(stack_is_empty(s))return?FAILURE;*value?=?s->stack[s->topOfStack];return?SUCCESS; }

判斷棧是否滿

只要判斷topOfStack與數(shù)組大小-1的大小即可。

/*判斷棧是否已滿，滿返回1，未滿返回0*/ int?stack_is_full(StackInfo_st?*s) {return?s->topOfStack?==?STACK_SIZE?-?1; }

判斷棧是否為空

只需要判斷topOfStack是否小于等于-1即可。

/*判斷棧是否為空，空返回1，非空返回0*/ int?stack_is_empty(StackInfo_st?*s) {return?s->topOfStack?==??-?1; }

完整可運行代碼

代碼較長，可點擊閱讀原文查看或訪問：

鏈表實現(xiàn)棧

與數(shù)組實現(xiàn)棧不一樣的地方是，鏈?zhǔn)綏？梢詣討B(tài)擴(kuò)容，基本沒有長度限制（受限于內(nèi)存）。另外，它在入棧以及出棧的時候需要申請或者釋放內(nèi)存。

創(chuàng)建棧

創(chuàng)建棧很容易，只需要聲明一個頭指針即可，它的next指針指向棧頂，初始時為空：

/*定義棧結(jié)構(gòu)*/ typedef?struct?StackInfo {ElementType?value;?/*記錄棧頂位置*/struct?StackInfo?*next;?/*指向棧的下一個元素*/ }StackInfo_st;/*創(chuàng)建棧，外部釋放內(nèi)存*/ StackInfo_st?*createStack(void) {StackInfo_st?*stack?=?malloc(sizeof(StackInfo_st));if(NULL?==?stack){printf("malloc?failed\n");return?NULL;}?/*stack-next為棧頂指針*/stack->next?=?NULL;return?stack; }

入棧

入棧只需要為新的元素申請內(nèi)存空間，并將棧頂指針指向新的節(jié)點即可。

入棧操作/*入棧，0表示成功，非0表示出錯*/ int?stack_push(StackInfo_st?*s,ElementType?value) {StackInfo_st?*temp?=?malloc(sizeof(StackInfo_st));if(NULL?==?temp){printf("malloc?failed\n");return?FAILURE;}/*將新的節(jié)點添加s->next前，使得s->next永遠(yuǎn)指向棧頂*/temp->value?=?value;temp->next?=?s->next;s->next?=?temp;return?SUCCESS; }

出棧或訪問棧頂元素

出棧時，將棧頂指針指向下下個節(jié)點，返回元素值，并釋放棧頂指針下個節(jié)點的內(nèi)存。而訪問棧頂元素只需要返回棧頂指針指向節(jié)點的元素值即可。

出棧/*出棧*/ int?stack_pop(StackInfo_st?*s,ElementType?*value) {/*首先判斷棧是否為空*/if(stack_is_empty(s))return?FAILURE;/*找出棧頂元素*/*value?=?s->next->value;StackInfo_st?*temp?=?s->next;s->next?=?s->next->next;/*釋放棧頂節(jié)點內(nèi)存*/free(temp);temp?=?NULL;return?SUCCESS; } /*訪問棧頂元素*/ int?stack_top(StackInfo_st?*s,ElementType?*value) {/*首先判斷棧是否為空*/if(stack_is_empty(s))return?FAILURE;*value?=?s->next->value;return?SUCCESS; }

判斷棧是否為空

判斷棧空也很簡單，只需要判斷棧頂指針是否為空即可。

/*判斷棧是否為空，空返回1，未空返回0*/ int?stack_is_empty(StackInfo_st?*s) {/*棧頂指針為空，則棧為空*/return?s->next?==?NULL; }

完整可運行代碼

代碼較長，可點擊閱讀原文查看或訪問：

總結(jié)

本文介紹了棧的基本操作以及棧的基本實現(xiàn)。后面將會介紹一些棧的具體應(yīng)用。

---

掃碼或長按關(guān)注

回復(fù)「?加群?」進(jìn)入技術(shù)群聊

總結(jié)

以上是生活随笔為你收集整理的如何自己实现一个栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。