# Queue 佇列
[TOC]
## 介紹
**Queue**是一個「First-In-First-Out」的資料結構，==**比較早放入Queue的資料會比較早拿出來**==，==**而比較晚放進去的資料會比較晚拿出來**==。跟排隊買票一樣，先排隊的人可以先買到，而後來到的人需要等前面的人買完才能輪到他。
## 程式碼
在Queue的程式碼中，==會需要兩個pointer來分別記錄Queue中的第一個以及最後一個的位址==。
```C=
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node* next;
};
typedef struct node Queue_Node;
Queue_Node *front , *rear ;
front = rear = NULL;
int isEmpty(){ /*判斷Queue是否為空*/
if (front==NULL){ /*當front是NULL時，代表Queue裡已沒有資料，回傳1*/
return 1;
}
else{ /*反之，代表Queue裡還有資料，回傳0*/
return 0;
}
}
void enqueue(int data){ /*增加資料至Queue中*/
Queue_Node* newnode=(Queue_Node*)malloc(sizeof(Queue_Node));/*建立新的node*/
newnode->data = data;
newnode->next = NULL;
if (front == NULL){ /*如果front為NULL，代表Queue裡尚未有資料*/
front = newnode; /*將front和rear指向newnode*/
rear = newnode;
return;
}
rear->next = newnode; /*將rear的pointer指向newnode*/
rear = newnode; /*將rear指向newnode*/
}
int dequeue(int* ret){ /*從Queue中拿出資料*/
int data;
Queue_Node* tmp;
if (isEmpty()){ /*判斷Queue是否為空*/
printf("Queue is empty!\n");
return -1; /*如果為空，回傳值-1*/
}
else{ /*如果Queue裡還有資料*/
data=front->data;
tmp=front;
front = front->next;/*將front指向下一筆資料*/
free(tmp); /*釋放記憶體*/
*ret=data; /*將資料傳給*ret*/
return 0; /*回傳值0*/
}
}
int main(){
int value;
int i, a;
printf("輸入五筆資料:\n");
for (i=0;i<5;i++){
scanf("%d",&value);
enqueue(value);
}
printf("============\n");
while(1){
if (dequeue(&a)!=0){ /*判斷dequeue()的回傳值是否為0*/
printf("dequeue error!\n");
return -1;
}
printf("dequeue:%d\n",a);
}
printf("hi");
return 0;
}
```
## 程式解說
在 enqueue( ) 函數中，如果 Queue 是空的時候，執行24~26行，令新的節點 newnode 來當作第一筆資料，並將front 和 rear 指向 newnode。如果已有資料在 Queue 裡的時候，則是執行28~29行，此時 rear 應該會指向其中的最後一個node，因此我們需要將 rear 的 pointer 指向 newnode，再將 rear 指向 newnode (新的最後一個節點)。
在 dequeue( ) 函數中，如果 Queue 是空的，便會回傳值-1，因此在主程式58行做判斷時，因為不為0，因此輸出"dequeue error!"，並且結束程式，所以執行程式時，就不會輸出第64行的"hi"。如果 Queue 裡面還有資料，則會回傳值0，並將資料傳給 *ret ，因此不會進入主程式58行的 if 迴圈，而是直接到62行輸出資料。