# queue介紹與實作
## 介紹
queue是一種具有先進先出(FIFO, First-In-First-Out)性質的資料容器，也就是最先被放入的資料會被最先取出。

在生活中，queue通常被用於類似排隊的情形，先入隊的人會先出隊，也就符合queue的性質。

一般來說，queue支援以下操作：
* push(data)：將資料放入queue的最後。
* pop()：將queue最前的資料丟出。
* front()：存取queue最前的資料
* size()：取得queue的大小
* empty():確認queue是否為空


以上圖為例，5,1,3,4分別入queue，接著5,1分別出queue，10入queue，3出queue，此時的front()為4。

與stack相似，queue在不額外進行pop()時只能存取最前方的資料，若要存取後面的資料，需要pop()掉前面的資料。

## 應用
基於queue的First-In-First-Out的性質，queue時常被應用於先到先執行、排程的情形：
- 基於queue的演算法：
- BFS(廣度優先搜尋)
- Tree 的 Level-Order Traversal
- 安排被多個程式所共享的資源(CPU、印表機、網站伺服器等)的執行順序
- [Tutorialspoint：Operating System - Process Scheduling]( http://www.tutorialspoint.com/operating_system/os_process_scheduling.htm)
- [Stack Overflow : What are practical applications of Queues?](https://stackoverflow.com/questions/2392824/what-are-practical-applications-of-queues)
- [StackExchange : Which queue does the long-term scheduler maintain?](https://cs.stackexchange.com/questions/1106/which-queue-does-the-long-term-scheduler-maintain)

## 實作

queue的實作，通常是以Linked-List實作。整體的概念是利用在鏈頭加點，在鏈尾刪點達到queue的性質。
在queue中，我們要維護3個東西:
- head: 指向queue後端的指標
- tail: 指向queue的前端的指標
- size: queue的大小

### node

struct node{
    int data;
    node* last;
    node* next;
};

用於Linked-List的節點，其中data存取容器內的一筆資料，last和next分別存取指向後方與前方的節點的指標。

### push

void push(int data){
    size++;
    node tmp;
    tmp.data = data;
    if(head!=nullptr){
        tmp.next = head;
        head->last = &tmp;
    }
    head = &tmp;
    if(size==1)tail = &tmp;

    return;
}

將資料放入容器時，queue大小+1，並且在鍊頭上增加一個節點，更新鍊頭。如果queue大小為1，則鍊頭也是鍊尾。

### empty

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

檢查queue是否為空檢查queue大小是否為零即可。
### pop

void pop(){
    if(empty())return;
    else{
        size--;
        if(tail->last!=nullptr){
            tail = tail->last;
            tail->next = nullptr;
        }else{
            tail = nullptr;
        }
        if(size==0)head = nullptr;
    }
    return;

}

檢查queue是否非空，並將鍊尾刪除一個節點，queue大小-1。若queue的大小為1，則鍊頭一並刪除。

### front

int front(){
    if(size==0)return -1;
    else return tail->data;
}

存取queue最前方資料利用tail指標來存取即可。

### size

int size(){
    return size;
}

存取queue大小利用維護的size即可。

## 參考資料
https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/xian-xing-zi-liao-jie-gou-queue-stack-huolinked-list-yu-you-xian-quan-zhu-lie-priority-queue

https://alrightchiu.github.io/SecondRound/queue-introjian-jie-bing-yi-linked-listshi-zuo.html

http://www.tutorialspoint.com/operating_system/os_process_scheduling.htm

https://stackoverflow.com/questions/2392824/what-are-practical-applications-of-queues

https://cs.stackexchange.com/questions/1106/which-queue-does-the-long-term-scheduler-maintain

https://finalfrank.pixnet.net/blog/post/22382141

https://www.ithome.com.tw/node/82042

https://zh.wikipedia.org/wiki/%E9%98%9F%E5%88%97