# Stack 堆疊
[TOC]
## 介紹
**Stack**是一個「Last-In-First-Out」的資料結構，==**比較早放入Stack的資料會比較晚拿出來**==，==**比較晚放進去的資料會比較早拿出來**==。就像把書要放進箱子一樣，先放進的書本會放在最下面，其他的書則會慢慢疊上去，最後放上去的書則會是在最上面。當我們要拿出來的時候，最上面的書，也就是最後放進去的書，會被先拿出來，而最先放進箱子的書，則要先把要在上面的書先拿走之後，才會是最後一個拿出來的。
### 程式碼
```C=
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct Node* next;
};
typedef struct node Stack_Node;
Stack_Node* top = NULL;
int isEmpty(){ /*檢測Stack是否為空*/
if (top==NULL){
return 1;
}
else{
return 0;
}
}
void push (int data){ /*增加資料*/
Stack_Node* newnode=(Stack_Node*)malloc(sizeof(Stack_Node));
newnode->data=data;
newnode->next=top;
top=newnode;
}
int pop(){ /*取出資料*/
Stack_Node* ptr;
int tmp;
if (isEmpty()){ /*判斷Stack是否為空*/
printf("Stack is empty!\n");
return -1;
}
else{
ptr=top;
tmp=ptr->data;
top=top->next;
free(ptr);
return tmp;
}
}
int main(){
int value;
int i;
printf("請輸入五筆資料:\n");
for (i=0;i<5;i++){
scanf("%d",&value);
push(value);
}
printf("====================\n");
while(!isEmpty()){
printf("Stack彈出的資料為%d\n",pop());
}
pop();
return 0;
}
```
## 程式解說
在 pop() 的函數中，如果 Stack 內還有東西時，則會取出最上面的資料出來;相反地，Stack 內沒有東西時，會回傳一個值-1回去，此時有可能會誤會是回傳 Stack 內的資料回去，因此這函數是較不完善的。而在Queue的介紹中有另一種比較好的寫法可以參考!
``` c
int main() {
int a;
if (0 != dequeue(&a)) {
printf("dequeue error");
return -1;
}
printf("dequeue: %d", a);
return 0;
}
int dequeue(int *ret){
int data;
Queue_Node* tmp;
if (isEmpty()){
printf("Queue is empty!")
return -1;
}
else{
data=front->data;
tmp=front;
front = front->next;
free(tmp);
*ret = data;
return 0;
}
}
```