# [資料結構] CH4. Stacks

* Stack(堆疊)是一個可以儲存資料的有序空間，我們可以在裡面加入資料或刪除資料。
* 在這裡你可以先將想成是有特殊性質的**陣列**，下面的範例或圖片也都會先以陣列的樣子做展示。
* 然而Stack在記憶體空間中不一定是連續的，我們也可以藉由**Linked List**等其他方式來實作，這會在更之後的部分才會提到。

* Stack就像是一個細長的桶子，在裡面加入資料時只能從上面加入，而資料不停地往上堆，而最早加入的會被壓在最下面。
* Top指的是最上面的資料，也就是我們唯一可以拿出來的資料(其他的資料被壓住了)。
* 最先進去的卻最後才能出來，因此Stack是一種<b>後進先出(Last-In-First-Out)</b>的結構。
* 在Array中大概長成這樣：

digraph stack {
	node[shape=record]
	stack [label="{ <f0>Data_n|<f1>...|<f2>...|<f3>data3|<f4>data2|<f5>data1}"];
    array [label="<f0>data1|<f1>data2|<f2>data3|<f3>...|<f4>...|<f5>Data_n"];
    
    stack:f5->array:f0
    stack:f4->array:f1
    stack:f3->array:f2
    stack:f0->array:f5
    Top[shape=""]
    Top->array:f5
    Top->stack:f0
}

## Stack Permutation
* 給一序列資料，再給一個空的Stack，我們可以藉由push進去pop出來的動作，交換原本資料的前後順序，而這就被稱作**Stack Permutation**。
* 來個常見的例題：
`For a given sequence of elements {𝐴, 𝐵, 𝐶}, please write down
its stack permutation.`
* 答案(請反白)：
* <font color="#FFFFFF">ABC；push 𝐴, pop 𝐴, push 𝐵, pop 𝐵, push 𝐶, pop C</font>
* <font color="#FFFFFF">ACB；push 𝐴, pop 𝐴, push 𝐵, push C, pop C, pop B</font>
* <font color="#FFFFFF">BAC；push 𝐴, push 𝐵, pop B, pop A, push C, pop C</font>
* <font color="#FFFFFF">BCA；push 𝐴, push 𝐵, pop B, push C, pop C, pop A</font>
* <font color="#FFFFFF">CBA；push 𝐴, push 𝐵, push C, pop C, pop B, pop A</font>

## Stack的應用

### function的堆疊指標
* 假設某程式function A call了Function B時，電腦必須記住我們Function A是執行到哪裡，以便Function B執行完畢後，知道要回到哪裡繼續執行。
* 在CH1中講到的遞迴程式，系統就是利用堆疊的結構儲存剛剛執行到哪裡，然後在遞迴的function結束時回到剛剛的地方。
* 以階層的程式為範例，在Visual Studio 2017中，使用break point也提供堆疊指標的除錯功能：

#include <iostream>
using namespace std;

int factorial(int a)
{
	if (a == 0)return 1;
	else return factorial(a - 1)*a;
}

int main()
{
	cout << factorial(5);
	return 0;
}


### Expression
* 一個數學式子$A\div B-C+D\times E-A$，我們把那些加減乘除稱作**運算子(Operator)**，而ABC那些數字稱作**運算元(Operand)**。
* 我們知道一段式子對於每個運算子來說，是有先後順序的，例如先乘除、後加減等。
* 當一段式子變得更加複雜時，我們人類可能都會忘記先計算括號內的東西，電腦來說一定更難看懂。
* 因此，我們可以利用堆疊的結構，將一般常用的式子(又稱**中序表示式(infix)**)，轉換成電腦比較好理解的**後序表示式(postfix)**或**前序表示式(prefix)**。

#### postfix and prefix
* 一般的式子叫中序表示法，那是因為我們是將運算子放在兩個運算元中間做運算；同理後序與前序便是將運算子放在後面與前面。
* infix: $A\div B-C+D\times E-A$
* postfix: $AB\div C-DE\times+A-$
* prefix: $-+-\div ABC\times DEA$
* 在學會如何用code轉換之前，先來學學如何在考卷上自己轉換：
* 中序轉後序：

1.把式子各處按照優先度加上括號。
2.把運算子替換到離它最近的右括號(一樣要先做括弧內的東西)。
3.移除所有括號。

1.$A\div B-C+D\times E-A$
2.$((((A\div B)-C)+(D\times E))-A)$
3.$((((AB\div C-(DE\times +A-$
4.$AB\div C-DE\times +A-$
* 中序轉前序：

1.把式子各處按照優先度加上括號。
2.把運算子替換到離它最近的左括號(一樣要先做括弧內的東西)。
3.移除所有括號。

1.$A\div B-C+D\times E-A$
2.$((((A\div B)-C)+(D\times E))-A)$
3.$-+-\div AB)C)\times DE))A)$
4.$-+-\div ABC\times DEA$

##### 用畫&看快速得到答案：
* 如果你已經學過Tree，且你可以從中序式直接想出下面這棵樹：

digraph Tree{
	1 [label="-"];
	2 [label="+"];
	3 [label="A"];
	4 [label="-"];
    5 [label="×"];
    6 [label="÷"];
    7 [label="C"];
    8 [label="D"];
    9 [label="E"];
    10 [label="A"];
    11 [label="B"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    4 -> 6
    4 -> 7
    5 -> 8
    5 -> 9
    6 -> 10
    6 -> 11
}

* 那麼恭喜你，只要再加上一條線，你已經得到它的中序、前序、後序：
* 如果要得到**前序**，只要被這條線經過**左邊**的node，你就把它寫下來。
* 如果要得到**中序**，只要被這條線經過**下面**的node，你就把它寫下來。
* 如果要得到**後序**，只要被這條線經過**右邊**的node，你就把它寫下來。

## 簡單地用陣列實作Stack
* 標頭與定義：

#include <iostream>
using namespace std;
//The size of your stack.
#define MAXSIZE 3

int myStack[MAXSIZE], top = -1;
void push(int myStack[], int val);
int pop(int myStack[]);
int peek(int myStack[]);
void display(int myStack[]);

* push

void push(int myStack[], int val)
{
    if(top == MAXSIZE - 1)
    {
        cout << "Stack overflow" << endl;
    }
    else
    {
        top++;
        mystack[top] = val;
    }
}

* pop

int pop(int myStack[])
{
    int val;
    if(top == -1)
    {
        cout << "Stack underflow" << endl;
        return -1;
    }
    else
    {
        val = mystack[top];
        top--;
        return val;
    }
}

* display

void display(int myStack[])
{
    if(top == -1)cout << "Stack is empty" <<endl;
    else
    {
       cout << i << ": " << mystack[i] << endl;
    }
}

* peek

int peek(int myStack[])
{
    if(top == -1)
    {
        cout << "Stack is empty" <<endl;
        return -1;
    }
    else
        return myStack[top];
}

* 上面這些只是個概念，正常當然不會這樣做，但對理解Stack的結構和特性還是有所幫助。
* 實際上C++中，vector就是一個幫你實作好的stack結構，除了上面那些還有很多其他功能，歡迎自己多多研究。

## Expression Convertor
* 最後我們要使用程式來幫助我們轉換前中後序。
* 先講中序轉後序：

1.加入一個")"到式子的尾巴。
2.Push一個"("到stack裡面
3.For each char in infix
    如果遇到"("：將它放入stack中。
    如果遇到一個運算元：將它放入postfix中(也就是結果)。
    如果遇到")"：
        a) 不停將stack的東西pop到postfix中，直到pop出"("。
        b) "("請不要放入postfix，因為最後結果不會有括號。
    如果遇到一個運算子：
        a) 將該運算子與stack的top比較優先度：
            I) 若stack的top優先度較小，將stack pop出來並加到postfix中。完成後繼續回到a)。
            II) 若stack的top優先度較大或相等，將此運算子push到stack中。

* 如果你已經會中序轉後序，中序轉前序鐵定難不倒你：

1. 將infix前後顛倒，記得將"("和")"做反向。
2. 將該式做"中序轉後序"。
3. 將輸出結果再次顛倒。

* 該部份如果要做範例很麻煩也很占版面，在此附上本人的code，還請需要者自行參閱。
* [我丟～](https://github.com/Zero871015/ExpressionConvertor)
* 我有做step by step，以方便理解。

###### tags: `DS` `note`