# 演算法與資料結構 堆疊(Stack) ###### tags: `Algorithm` ## 堆疊介紹 堆疊是限制插入元素和刪除元素只能在同一個位置的表(list),該位置一般來說稱為棧頂(Top)。對堆疊的基本操作有 ==Push(推入,將資料加到棧頂)== 和 ==Pop(彈出,將棧頂的資料移出)== 這兩種操作。 Push可以把它想像成把洋芋片放到洋芋片罐裡,Pop則是拿出洋芋片 ![](https://i.imgur.com/wp2MsxC.png) 堆疊有時候也會被稱為先進後出表(LIFO,Last In First Out),最先進入的資料會最後被彈出,如同函式呼叫,最先呼叫的函式會最後彈出記憶體。 堆疊在軟體中是相當常見的應用,像是瀏覽器的上一頁就是一種應用,會按照你所存取的網頁,依照堆疊的順序進行存取(事實上,上一頁其實並非邏輯上的上一頁,如果現在在yahoo,上一頁是google,我們按下上一頁後會回到google,但再按上一頁事實上並不是回到yahoo...要不然就是死循環了...) ## 堆疊實做 一般來說我們有兩種方法可以實作出堆疊,一種為使用單向鏈結串列的方式,另一種則是使用陣列的方式,以下先舉單向鏈結串列的實作方式。 ### 堆疊的ADT,使用單向鏈結串列(single linked list) 我們透過在表的頂端插入來實現Push的操作,通過刪除頂端資料來實作Pop,Top表示回傳最頂端的值,以下為堆疊的ADT ```c= #ifndef _Stack_h struct Node; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(int X, Stack S); int Top(Stack S); void Pop(Stack S); #endif /* Place in implementation file */ /* Stack implementation is a linked list with a header*/ struct NODE{ ElementType Element; PtrToNode next; }; ``` #### IsEmpty實作 ```c= int IsEmpty(Stack S) { return S->next == NULL; } ``` 為空則回傳true,否則false。 #### CreateStack實作 ```c= Stack CreateStack(void) { Stack S = (Stack)malloc(sizeof(Stack)); if(S == NULL) { printf("Out of space!!!"); } S->next = NULL; MakeEmpty(S); return S; } ``` 令節點S為指向Node的指標(typedef取代成 Stack),並將分配到記憶體空間的指標回傳給S,下一個節點為空,並回傳S。 #### MakeEmpty實作 ```c= void MakeEmpty(Stack S) { if(S == NULL) { printf("Must use CreateStack first"); } else { while(!IsEmpty(S)) { Pop(S); } } } ``` 當傳入的Stack S不為空時,將所有的元素Pop,建立出空的Stack。 #### Push實作 ```c= void Push(int X, Stack S) { Stack TmpCell = (Stack)malloc(sizeof(Stack)); if(TmpCell == NULL) { printf("Out of space!!!"); } else { TmpCell->value = X; TmpCell->next = S->next; S->next = TmpCell; } } ``` 第一步:建立節點,如果成功建立,則填入傳入值X ![](https://i.imgur.com/xKxZt49.png) 第二步:將原先鏈結串列的內容接續到TmpCell ![](https://i.imgur.com/XTZOKu9.png) 第三步:將原鏈結串列的頭的下一個元素設為TmpCell ![](https://i.imgur.com/COkICQ6.png) #### Top實作 ```c= int Top(Stack S) { if(!IsEmpty(S)) { return S->next->value; } printf("Empty Stack"); return 0; } ``` 直接回傳頭的元素 #### Pop實作 ```c= void Pop(Stack S) { PtrToNode FirstCell; if(IsEmpty(S)) { printf("Empty Stack"); } else { FirstCell = S->next; S->next = S->next->next; free(FirstCell); } } ``` 第一步,將FirstCell指向S->next,也就是將FirstCell與原先串鍊串接 ![](https://i.imgur.com/83U9QrO.png) 第二步,將S->next指向S->next->next,也就是將頭的下一個節點指到下下個節點 ![](https://i.imgur.com/lMUKM2v.png) 第三步,將FirstCell所指到的節點,也就是S->next記憶體空間釋放 ![](https://i.imgur.com/zxkYVEL.png) #### 小節 我們所有的操作,都是線性時間,$O(1)$,因為我們不需要任何涉及堆疊大小的操作(遍歷等等...),但是缺點為使用鏈結串列進行實作會大量的使用到malloc和free函式,而這一些函式操作是相當的耗費時間的。 ### 堆疊的ADT,使用陣列(Array) 除了使用鏈結串列進行實作,我們也可以使用陣列的方式進行實作,相較於鏈結串列的實作,我們需要注意陣列大小的問題,但是一般來說,我們不會太在意陣列大小問題,原因為同一時間,堆疊內的元素個數通常不會太大,因此宣告一個足夠大小的陣列便足夠。 若同一時間可能存在大量的元素,導致我們需要宣告較大的陣列時,使用鏈結串列的方式可以減少空間的浪費。 以下為使用陣列實作的堆疊ADT模型。 ```c= #ifndef _Stack_h struct StackRecord; typedef struct StackRecord *Stack; int IsEmpty(Stack S); int IsFull(Stack S); Stack CreateStack(int MaxElements); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(ElementType X, Stack S); ElementType Top(Stack S); void Pop(Stack S); ElementType TopAndPop(Stack S); #endif /*_Stack_h */ /* Place in implementation file */ /* Stack implementation is a dynamically allocated array */ #define EmptyTOS (-1) #define MinStackSize (5) struct StackRecord{ int Capacity; int TopOfStack; ElementType *array; }; ``` 我們在ADT模型中, #### CreateStack實作 ```c= Stack CreateStack(int MaxElements) { Stack S; if(MaxElements < MinStackSize) { printf("Stack size is too small"); } S = (Stack *)malloc(sizeof(sturct StackRecord)); if(S == NULL) { printf("Out of space!!!"); } S->array = malloc(sizeof(ElementType) * MaxElements); if(S->array == NULL) { printf("Out of space!!!"); } S->Capacity = MaxElements; MakeEmpty(S); return S; } ``` #### DisposeStack實作 ```c= void DisposeStack(Stack S) { if(S != NULL) { free(S->array); free(S); } } ``` #### IsEmpty實作 ```c= int IsEmpty(Stack S) { return S->TopOfStack == EMptyTOS; } ``` #### MakeEmpty實作 ```c= void MakeEmpty(Stack S) { S->TopOfStack = EmptyTOS; } ``` #### Push實作 ```c= void Push(ElementType X, Stack S) { if(IsFull(S)) { printf("Full Stack"); } else { S->array[++S->TopOfStack] = X; } } ``` #### Top實作 ```c= ElementType Top(Stack S) { if(!IsEmpty(S)) { return S->array[S->TopOfStack]; } printf("Empty Stack"); return 0; } ``` #### Pop實作 ```c= void Pop(Stack S) { if(IsEmpty(S)) { printf("Empty Stack"); } else { S->TopOfStack--; } } ``` 參考資料: 大話數據結構,C语言程序设计现代方法第2版,圖片源於網路(沒有工商洋芋片~)
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up