# Data Structure - Stack

## 用途

程式設計hw1第三題會用到。

## 概念
有人將stack比喻為一疊盤子。

push()代表把一個新的盤子放到堆的頂端，pop()則是將堆頂端的盤子移除，top()會取得堆頂端的盤子，is_empty()會判斷堆中還有沒有盤子，以下以盤子的概念說明。

1. 一開始沒有任何盤子。
| ___ |

2. ```push(3)```

| _ 1 _ |
| _ 2 _ |
| _ 3 _ |

相當於：
放了3這個盤子進去。
放了2這個盤子進去。
放了1這個盤子進去。

3. ```top()```
| _ 1 _ |
| _ 2 _ |
| _ 3 _ |

後放進去的盤子會在頂端，所以會得到1。

4. ```pop()```
| _ 2 _ |
| _ 3 _ |

移除頂端的盤子，所以1被拿走了。

5. ```push(4)```
| _ 4 _ |
| _ 2 _ |
| _ 3 _ |

再放4這個盤子進去。

6. ```top()```
| _ 4 _ |
| _ 2 _ |
| _ 3 _ |

會得到4。

## 實作

### 實作細節
stack可以用linked-list或array的方法來實作，方便起見，我使用array實作，需要有四種函式來操作stack，分別為：

- ```is_empty()```:判斷stack是否為空
- ```top()```:回傳stack頂端的值
- ```push()```:將資料放入到頂端
- ```pop()```:移除stack頂端的值

1. 一開始stack：

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 0  | 0  | 0  | 0  | 0  | 0  |



2. ```push(3)```

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 3  | 3  | 2  | 1  | 0  | 0  |



3. ```top()```

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 3  | 3  | 2  | 1  | 0  | 0  |

會回傳1。

4. ```pop()```

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 2  | 3  | 2  | 0  | 0  | 0  |

5. ```push(4)```

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 3  | 3  | 2  | 4  | 0  | 0  |

6.```top()```

| 0  | 1  | 2  | 3  | 4  | 5  |
| ---| ---| ---| ---| ---| ---|
| 3  | 3  | 2  | 4  | 0  | 0  |

會回傳4。

### 程式碼

int is_empty(int *stack){
return stack[0] == 0;
}

int top(int *stack){
    if(is_empty(stack)) return -MAX;            
    return stack[stack[0]];
}

void push(int *stack , int n){
stack[0]++;
stack[stack[0]] = n;
}

void pop(int *stack){
    if(is_empty(stack)) return;         
    stack[0]--;
}

## 總結
1. stack是一種單向的資料結構，加入資料，移除資料都是在同一邊操作，後進去的資料會先出來。
2. ```stack[0]```代表長度。
3. 每執行一次```push()```，```stack[0]++```；每執行一次```pop()```，```stack[0]--```。
4. 需要四種函式操作stack
- ```is_empty()```:判斷stack是否為空
- ```top()```:回傳stack頂端的值
- ```push()```:將資料放入到頂端
- ```pop()```:移除stack頂端的值
5. 程設的第三題會用到stack。