【演算】堆疊 - Stack

　　堆疊(stack)是一種同質元素(像是相同型態的變數)集合的資料結構，只允許在結構的一端，進行推入(push)或是彈出(pop)兩種資料操作。



　　讓我們舉個實例：想像現在有一疊盤子，每當執行一次 "push" 就相當於往上再疊上一個盤子，而執行一次 "pop" 則像是拿走最上面的那一個盤子。

　　因此，我們可以發現：由於越晚疊入的盤子(資料)在越上層，因此是這個盤子(資料)是越早被取下來的。而這種資料操作方式，我們就稱之為 LIFO (Last In First Out，後入先出)。

　　也因為這種特性，堆疊的應用範圍相當的廣。像是程式設計函式(function)的呼叫(call)與返回(return)、河內塔(Towers of Hanoi)、算術式轉換等等。這些應用我以後會找機會一一說明，在此不加贅述。


　　在程式語言中，要實現堆疊有許多種方法，最簡單的方式就是使用陣列模擬。即定義一個大小為 MAX_SIZE 的陣列，並使用一個變數 top 來表示堆疊的頂端。而資料操作的方式可以參考以下虛擬碼：

void push(Stack &stack, Type data)
{
    Index top;

    if (top = MAX_SIZE)
    {
        print "The stack is full!";
    }
    else
    {
        stack[top] = data;
        top = top + 1;
    }
}

void pop(Stack &stack)
{
    Index top;

    if (top = 0)
    {
        print "The stack is empty!";
    }
    else
    {
        top = top - 1;
    }
}

　　當然，除了陣列之外，你也可以使用其他資料結構(例如：連結串列，linked list) 來模擬。另外，在 C++ 的 STL(Standard Template Library，標準樣板庫) 中，也早已實現了堆疊結構及相關函式。不過這些都不在本篇的討論範圍中，有興趣的人就自行摸索囉。

　　以下是 C 以陣列實現的堆疊原始碼，可以參考看看：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

void push(int);
void pop(void);

int stack[MAX_SIZE], top = 0;

int main(void)
{
    push(0);
    push(1);
    push(2);
    pop();
    pop();
    push(3);
    push(4);
    pop();
    pop();
    pop();
    push(5);
    push(6);
    push(7);
    pop();
    pop();
    pop();

    system("pause");
}

void push(int data)
{
    if (top == MAX_SIZE)
    {
        printf("The stack is full!\n");
    }
    else
    {
        stack[top++] = data;
    }
}

void pop(void)
{
    if (top == 0)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", stack[--top]);
    }
}