---
# System prepended metadata

title: queue介紹與實作

---

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

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

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


![](https://i.imgur.com/iPqoNnL.png)
![](https://i.imgur.com/jg3vDIy.png)
![](https://i.imgur.com/oZGGdVp.png)
![](https://i.imgur.com/wIGi5UA.png)
![](https://i.imgur.com/rIPCZ7F.png)
![](https://i.imgur.com/sLsRIQD.png)
![](https://i.imgur.com/15bfG2N.png)
![](https://i.imgur.com/rkcxqmi.png)

以上圖為例，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

```cpp=
struct node{
    int data;
    node* last;
    node* next;
};
```

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


### push
```cpp=
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
```cpp=
bool empty(){
    if(size==0)return true;
    else return false;
}
```
檢查queue是否為空檢查queue大小是否為零即可。
### pop
```cpp=
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
```cpp=
int front(){
    if(size==0)return -1;
    else return tail->data;
}
```

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

### size
```cpp=
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