# stack介紹與實作

## 介紹
stack是一種具有後入先出(Last-In-First-Out, LIFO)性質的資料容器，也就是最後被放進容器的資料，會最先被取出。

以生活的例子來說，一疊堆起來的盤子就具有stack的性質，因為在沒有取出額外的盤子的情況下，只有最上方的盤子能夠被取出，也只能從最上方放入。

事實上，stack是個抽象的觀念，只要符合First-In-Last-Out的性質，我們都會稱之為stack。

一般來說，stack會支援以下操作:

* push(data)：將資料放入stack的最上方
* pop()：將stack最上方的資料丟出
* top()：取得stack最上方的資料(不影響stack本身)
* size()：取得stack的大小(不影響stack本身)
* empty()：確認stack是否為空(不影響stack本身)

以上圖為例，5,1,3分別被push()進到stack中，接著4,3分別被pop()出stack，10再被push()進stack再被pop()，此時的top()為1。

此外，stack的其中一個性質是只有最上方的資料能夠被存取，若要取得下方的資料，需要進行pop()將上方的資料拿出。以圖一為例，在最後若想取得編號5的資料，必須再執行pop()將編號1的資料丟出。

## 應用
stack的主要用途是用來回復「先前的狀態」，也就是類似Ctrl+Z的操作，並且此種問題也被稱為Back-Tracking問題。
* 文字編輯器的undo功能
* 瀏覽器的「回到上一頁」
* 遞迴形式的任何演算法，如DFS(深度優先搜尋)，最晚被呼叫的函數會最先結束，可見他們都具有stack的性質。事實上，他們的stack性質是被隱含在系統的Call Stack。

## 實作
stack的實作，可以利用陣列或Linked-List進行實作，我們在這裏選擇用陣列來實作。整體的概念是利用指針在陣列中的移動來達到LIFO的效果。

在容器中我們要維護三個資料：
* arr[] : stack儲存的資料
* topptr : 指向stack最上方的「下一個」位置的指針(根據不同的實作方式，也可以指向stack的最上方)
* size : stack的大小

### push

void push(int data){
    size++;
    arr[topptr] = data;
    topptr++;
} 

將資料丟入容器後，大小會+1，同時原本的topptr指針(指向原本的「下一個位置」，即新的最上方)位置要寫入資料。並且指針要向右移一格(因為最上方的位置向上移動了)。

### empty

bool empty(){
    if(size==0)return true;
    else return false;
}

判斷stack是否為空僅需判斷大小是否為0即可。

### pop

void pop(){
    if(empty())return;
    size--;
    topptr--;
}

將資料丟出，大小會-1，同時指針向左移一格(最上方的位置向下了一格)。
此外在丟出前須判斷stack是否非空，否則會存取到陣列外的資料。

### top

int top(){
    if(empty())return -1;
    else return arr[topptr-1];
}

利用指向最上方的下一個位置的指針，我們可以存取到上一個(即是stack最上方)的資料進行回傳。

### size

int size(){
    return size;
}

stack大小即是維護的size資訊。

整個程式碼如：

struct stack{

    int arr[10000];
    int topptr = 0;
    int size = 0;

    void push(int data){
        size++;
        arr[topptr] = data;
        topptr++;
    } 
    bool empty(){
        if(size==0)return true;
        else return false;
    }
    void pop(){
        if(empty())return;
        size--;
        topptr--;
    }
    int top(){
        if(empty())return -1;
        else return arr[topptr-1];
    }
    int size(){
        return size;
    }

};

## 參考資料
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%A0%88
http://alrightchiu.github.io/SecondRound/stack-introjian-jie.html
https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/stack.html
https://www.csie.ntu.edu.tw/~r95116/CA200/slide/C8_StackQueue.pdf