廢話時間

好想要當一個可以跟同學都說沒有讀書然後考很好ㄉ人...

前言

先前介紹過了stack，而今天要介紹的就是stack的好兄弟啦，在進入Queue的特性、實作講解之前，也可以先來思考一下生活上的應用，最淺顯易懂的例子不外乎就是在餐廳排隊等待入座，最先開始排隊的可以先排到座位，愈晚候位的人愈晚入座，了解完這個例子之後特性就很簡單可以了解ㄌ喔！

Queue特性

先開始排隊的人可以先進入座位也就意味著Queue最重要的特性

• FIFO (First in First out)

接著可以想像整條排隊的隊伍，前端可以先排到位子離開排隊隊伍、後端可以再遞補新來的客人，因此可以談即Queue的其他特性

• Front(頭) 可以進行資料的取出
• rear(尾) 可以進行資料的輸入

Queue的實作

在談及Queue的實作時，我們會嘗試著使用

1. Linear Array
2. Circular Array
3. Linkedlist
4. Circular LinkedList

Linear Array

create(){
    // 建立一個 [1...n] 的 Array Q
    int front = 0; // 宣告 front 為 0
    int rear = 0; // 宣告 rear 為 0
}
enqueue(item, Q){
    if(rear == n)  { // 如果 rear 已經到達 Array 的個數即為滿
        return "full";
    }
    rear+=1; // 將 rear 往前一格
    Q[rear] = item; //　item 放入陣列 A 中
}
dequeue(Q){
    if(front==rear){
        return "empty";
    }
    front+=1;
    int item = Q[front];
    return item;
}

仔細看完，可以發現利用 Linear Array 製作 Queue 時，在 Enqueue 的時候，若已經新增資料到 n 個了，然而 front 卻沒有 == 0 時，會造成空間並沒有用完，程式卻告知佇列已經滿了的狀況，如此一來便會浪費空間
解決方法可以在 Enqueue 的時候，把資料往前搬 front 格，讓 front 回到 0，但是這樣時間複雜度便會從 O(1) 增加到 O(n)

Circular Array

create(){
    // 建立一個 [1...n] 的 Array Q
    int front = 0; // 宣告 front 為 0
    int rear = 0; // 宣告 rear 為 0
}
enqueue(item, Q){
    rear = (rear+1)%n; // 將 rear 往前一格
    if(rear == front)  { // 如果 rear 已經追上 front 即為滿
        rear = (rear-1)%n; // 將 rear 退回一格
        return "full";
    }
    Q[rear] = item; //　item 放入陣列 A 中
}
dequeue(Q){
    if(front==rear){
        return "empty";
    }
    front=(front+1)%n;
    int item = Q[front];
    return item;
}

使用 Circular Array 就可以解決掉剛剛 Linear Array 的問題，然而卻出現了一個新問題，也就是會浪費一格空間，因為當 rear 追上 front 必定要退一格，如果沒有做這個動作的話，就會造成無法 dequeue 哦！

Linkedlist

create(){
	// 宣告 node 結構
	// 宣告 front=nil , rear=nil
}
enqueue(item,q){
	t = new(node);
	t->data = item;
	t->next = nil;
	if(rear==front) // case1 代表為空
		front = t;
	else rear->next = t; // case2 正常狀況
	rear = t;
}
dequeue(q){
	if(front==nil) return 'empty'; // case1
	t = front;
	item = front->data;
	front = front->next; // case3，若為 case2 front會變nil
	if(front==nil) // case2
		rear = nil;
	delete(t)
	return item;
}

Circular Linkedlist

create(){
	// 宣告 node 結構
	// 宣告 rear=nil
}
enqueue(item,q){
	t = new(node);
	t->data = item;
	t->next = nil;
	if(rear==nil) // case1 代表為空
		t->next = t;
	else{ // case2 正常
		t->next=rear->next // t指回最前面
		rear->next = t;
	}  // t與前一個建立連結
	rear = t; // rear 指 t
}
dequeue(q){
	if(rear == nil) return 'empty'; //case1
	t = rear->next;
	item = (rear->next)->data;
	if(t==rear->next){ //case2
		rear = nil;
	}
	else{
		rear->next = (rear->next)->next;
	}
	delete(t);
	return item;
}