生活随笔
收集整理的這篇文章主要介紹了
重学数据结构004——栈的基本操作及实现(数组实现)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
??? 上文提到過棧以及棧的基本操作。上文中是基于鏈表做的實現。但是這種方法會出現大量的malloc()和free()操作，這種開銷是非常昂貴的。
??? 另外一種實現方式是基于數組的實現。這種實現方式需要預先制定一個棧的大小，此外還需要一個Top來記錄棧頂元素下一個位置的數組索引值。如下圖所示：
??? 有的教材將Top指向棧頂元素，也就是上圖中X所在的數組單元。我們這里不這么認為。
??? 這種情況下棧的數據結構定義如下：
typedef?struct?StackRecord?*Stack;?struct?StackRecord?{?????int?Capacity;?????int?Top;?????int?*Array;?};? ??? 主要操作如下：
?int?IsEmpty(Stack?S);??int?IsFull(Stack?S);??Stack?CreateStack(int?MaxElements);??void?DisposeStack(Stack?S);??void?MakeEmpty(Stack?S);??void?Push(int?X,?Stack?S);??int?Top(Stack?S);??void?Pop(Stack?S);??int?PopAndTop(Stack?S);? ??? 一個完整的例子代碼如下：
#include?<stdio.h>?#include?<stdlib.h>?#define?MIN_STACK_SIZE?5??typedef?struct?StackRecord?*Stack;??struct?StackRecord?{?????int?Capacity;?????int?Top;?????int?*Array;?};???int?IsEmpty(Stack?S);??int?IsFull(Stack?S);??Stack?CreateStack(int?MaxElements);??void?DisposeStack(Stack?S);??void?MakeEmpty(Stack?S);??void?Push(int?X,?Stack?S);??int?Top(Stack?S);??void?Pop(Stack?S);??int?PopAndTop(Stack?S);??int?IsEmpty(Stack?S)?{?????return?S->Top?==?0;?}??int?IsFull(Stack?S)?{?????return?S->Top?==?S->Capacity;?}??void?MakeEmpty(Stack?S)?{?????S->Top?=?0;?}??Stack?CreateStack(int?MaxElements)?{?????if(MaxElements?<?MIN_STACK_SIZE)?????{?????????fprintf(stderr,?"Can't?create?a?Stack?less?than?%d?elements\n",MIN_STACK_SIZE);?????????exit(1);?????}?????else?????{?????????Stack?S?=?malloc(sizeof(struct?StackRecord));?????????if(S?==?NULL)?????????{?????????????fprintf(stderr,?"Out?of?space!");?????????????exit(1);?????????}?????????S->Array?=?malloc(sizeof(int)*MaxElements);?????????S->Capacity?=?MaxElements;?????????MakeEmpty(S);?????????return?S;?????}?}???void?DisposeStack(Stack?S)?{?????if(S?!=?NULL)?????{?????????free(S->Array);?????????free(S);?????}?}??void?Push(int?X,?Stack?S)?{?????if(IsFull(S))?????{?????????fprintf(stderr,"The?Stack?Is?Full");?????}?????else?????{??????????????????S->Array[S->Top++]?=?X;?????}?}??int?Top(Stack?S)?{?????if(!IsEmpty(S))?????{?????????int?tmp?=?S->Top?-?1;?????????return?S->Array[tmp];?????}?????else?????{?????????fprintf(stderr,"The?Stack?Is?Full");?????????exit(1);?????}??????}??void?Pop(Stack?S)?{?????if(!IsEmpty(S))?????{?????????--(S->Top);?????}?????else?????{?????????fprintf(stderr,"The?Stack?Is?Full");?????????exit(1);?????}?}?int?PopAndTop(Stack?S)?{?????if(!IsEmpty(S))?????{?????????return?S->Array[--S->Top];?????}?????else?????{?????????fprintf(stderr,"The?Stack?Is?Full");?????????exit(1);?????}?}??int?main(void)??{?????Stack?S?=?CreateStack(10);?????int?i;?????for(i?=?0;?i?<?10;?i++)?????{?????????Push(i,S);?????}?????while(!IsEmpty(S))?????{?????????printf("%d?",PopAndTop(S));?????}?????printf("\n");?????return?0;?}? ?
轉載于:https://blog.51cto.com/wawlian/716195
總結
以上是生活随笔為你收集整理的重学数据结构004——栈的基本操作及实现(数组实现)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
