# [資料結構] CH5. Queues
* 還記得我們的Stack長這樣：

digraph stack {
	node[shape=record]
    in [label="push",shape="none"]
    out[label="pop",shape="none"]
	stack [label="{ <f0>Data_n|<f1>...|<f2>...|<f3>data3|<f4>data2|<f5>data1}"];
    in->stack
    stack->out
    {rank=same;in;out;}
}

* 特色是先進後出，放入和拿出在同一端(Top)。
---
* 現在我們要給你一個新的東西(太酷了！)：佇列(queue)。
* 它大概長成這樣：

digraph queue {
	node[shape=record]
    in [label="push",shape="none"]
    out[label="pop",shape="none"]
	queue [label="{ <f0>Data_n|<f1>...|<f2>...|<f3>data3|<f4>data2|<f5>data1}"];
    in->queue
    queue->out
}

* 聰明的你一定看到這張圖就知道了，queue是一種**先進先出**的結構。
* 也因此我們的size紀錄器不能一個只有`Top`，我們需要有一個`front`記住你下一個資料要加在哪裡、一個`rear`記住你刪除(pop)時要對queue中哪個資料動作。
* 就像是買東西的時候排隊的隊伍，先到的會先買到東西。

## 範例
* 來個在陣列中的範例好了，假設現在有一個空的queue，依序放入`5`,`10`,`15`：

digraph queue {
	node[shape=record]
    in [label="front",shape="none"]
    out[label="rear",shape="none"]
	queue [label=" <f0>5|<f1>10|<f2>15|<f3>|<f4>|<f5>"];
    in->queue:f0
    out->queue:f2
}

* 這時候pop兩次再放入一次`7`：

digraph queue {
	node[shape=record]
    in [label="front",shape="none"]
    out[label="rear",shape="none"]
	queue [label=" <f0>|<f1>|<f2>15|<f3>7|<f4>|<f5>"];
    in->queue:f2
    out->queue:f3
}

## Implementation for Queue by Array
* 用簡單的方法實作一遍，首先是定義基本功能：

#define MAXSIZE 10
int queue[MAXSIZE];
int front = -1, rear = -1;
void Insert(int v);
int Pop();
void Display();

* 插入：

void Insert(int v)
{
    if(rear == MAXSIZE)
        cout << "overflow" << endl;
    else
    {
        if(front == -1 && rear == -1)
            front = rear = 0;
        else
            rear++;
        queue[rear] = v;
    }
}

* 刪除：

int Pop()
{
    if(front == -1 || fornt > rear)
    {
        cout << "No element" << endl;
        return -1;
    }
    else
    {
        int v = queue[front];
        front++;
        if(front > rear)
            front = rear = -1;
        return v;
    }
}

* 輸出：

void Display()
{
    for(int i = front; i <= rear; i++)
    {
        cout << queue[i] << endl;
    }
}

## Implementation for Queue by Linked List
* 其實用陣列時做會有一些缺點，就是當你加入元素又刪除元素後，你陣列前面的空間會是被浪費的，這可能讓你的queue根本還沒到最大容量就爆掉。
* 你可以每次刪除時都把資料移動到最前面，然而這樣會讓執行效率變差。
* 上方的程式碼只有在queue為空的時候才會移動。
* 因此使用**Linked List**實作其實是相當不錯的，讓我們來看看如何使用。
---
* 礙於篇幅可能過長，我應該會放在另一個地方獨立出來：
* [點我](https://hackmd.io/s/H12vTu8aX)
---

## Queue的延伸
* 除了上述介紹的queue之外，還擁有一些變形：

### Circular Queue
* 為解決`front`前面有未使用空間的問題，我們想到將queue的結尾和開頭接起來，形成一個圈圈的感覺。
* 簡單的作法是在`rear`到達`MAXSIZE`時，將`rear`設為`0`。

### Deque
* 又名**Double-ended queue**或**head-tail linked list**。
* 特色是兩端都可以放資料和拿資料，也可以想成是stack和queue的合體版。
* 基本上已經快跟queue沒關係了ㄎㄎ。
* **Input restricted deque**指只有一邊可以放入的deque。
* **Output restricted deque**則是只有一邊可以刪除。

### Priority Queue
* 具有優先度的queue，意旨除了看誰先來後到之外，還會先考慮誰權限比較大讓他先排。
* CPU的工作排程中，更改程式優先度就是這個概念。
* 工作排程就是一個queue的例子。
* 可以利用多個queue並行比較的方式來實作。

### Multiple Queue
* 當我們使用陣列來實作queue的時候，為節省空間可以用Multiple Queue。
* 意思是兩個queue共用一個array，一個從頭加入，另一個從尾巴加入。
* 撞在一起就爆ㄌ。
* 當兩筆資料的數量呈反比關係的時候可以用這個結構。

###### tags: `DS` `note`