# 演算法與資料結構 堆疊(Stack)
###### tags: `Algorithm`
## 堆疊介紹
堆疊是限制插入元素和刪除元素只能在同一個位置的表(list)，該位置一般來說稱為棧頂(Top)。對堆疊的基本操作有 ==Push(推入，將資料加到棧頂)== 和 ==Pop(彈出，將棧頂的資料移出)== 這兩種操作。

Push可以把它想像成把洋芋片放到洋芋片罐裡，Pop則是拿出洋芋片

堆疊有時候也會被稱為先進後出表(LIFO，Last In First Out)，最先進入的資料會最後被彈出，如同函式呼叫，最先呼叫的函式會最後彈出記憶體。

堆疊在軟體中是相當常見的應用，像是瀏覽器的上一頁就是一種應用，會按照你所存取的網頁，依照堆疊的順序進行存取(事實上，上一頁其實並非邏輯上的上一頁，如果現在在yahoo，上一頁是google，我們按下上一頁後會回到google，但再按上一頁事實上並不是回到yahoo...要不然就是死循環了...)

## 堆疊實做
一般來說我們有兩種方法可以實作出堆疊，一種為使用單向鏈結串列的方式，另一種則是使用陣列的方式，以下先舉單向鏈結串列的實作方式。

### 堆疊的ADT，使用單向鏈結串列(single linked list)
我們透過在表的頂端插入來實現Push的操作，通過刪除頂端資料來實作Pop，Top表示回傳最頂端的值，以下為堆疊的ADT

#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實作

int IsEmpty(Stack S)
{
    return S->next == NULL; 
}

為空則回傳true，否則false。
#### CreateStack實作

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實作

void MakeEmpty(Stack S)
{
    if(S == NULL)
    {
        printf("Must use CreateStack first");
    }
    else
    {
        while(!IsEmpty(S))
        {
            Pop(S);
        }
    }
}

當傳入的Stack S不為空時，將所有的元素Pop，建立出空的Stack。
#### Push實作

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

第二步:將原先鏈結串列的內容接續到TmpCell

第三步:將原鏈結串列的頭的下一個元素設為TmpCell

#### Top實作

int Top(Stack S)
{
    if(!IsEmpty(S))
    {
        return S->next->value;
    }
    printf("Empty Stack");
    return 0;
}

直接回傳頭的元素
#### Pop實作

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與原先串鍊串接
第二步，將S->next指向S->next->next，也就是將頭的下一個節點指到下下個節點
第三步，將FirstCell所指到的節點，也就是S->next記憶體空間釋放

#### 小節
我們所有的操作，都是線性時間，$O(1)$，因為我們不需要任何涉及堆疊大小的操作(遍歷等等...)，但是缺點為使用鏈結串列進行實作會大量的使用到malloc和free函式，而這一些函式操作是相當的耗費時間的。

### 堆疊的ADT，使用陣列(Array)
除了使用鏈結串列進行實作，我們也可以使用陣列的方式進行實作，相較於鏈結串列的實作，我們需要注意陣列大小的問題，但是一般來說，我們不會太在意陣列大小問題，原因為同一時間，堆疊內的元素個數通常不會太大，因此宣告一個足夠大小的陣列便足夠。

若同一時間可能存在大量的元素，導致我們需要宣告較大的陣列時，使用鏈結串列的方式可以減少空間的浪費。

以下為使用陣列實作的堆疊ADT模型。

#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實作

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實作

void DisposeStack(Stack S)
{
    if(S != NULL)
    {
        free(S->array);
        free(S);
    }
}

#### IsEmpty實作

int IsEmpty(Stack S)
{
    return S->TopOfStack == EMptyTOS;
}

#### MakeEmpty實作

void MakeEmpty(Stack S)
{
    S->TopOfStack = EmptyTOS;
}

#### Push實作

void Push(ElementType X, Stack S)
{
    if(IsFull(S))
    {
        printf("Full Stack");
    }
    else
    {
        S->array[++S->TopOfStack] = X;
    }
}

#### Top實作

ElementType Top(Stack S)
{
    if(!IsEmpty(S))
    {
        return S->array[S->TopOfStack];
    }
    printf("Empty Stack");
    return 0;
}

#### Pop實作

void Pop(Stack S)
{
    if(IsEmpty(S))
    {
        printf("Empty Stack");
    }
    else
    {
        S->TopOfStack--;
    }
}

參考資料: 大話數據結構，C语言程序设计现代方法第2版，圖片源於網路(沒有工商洋芋片~)