前言：上一篇結束了堆疊的實作，今天要來介紹新東西「佇列」。

佇列的特性：佇列和堆疊非常類似，同樣都是有序串列(元素以某種順序排列 ，該順序具有一定的意義，不可錯置)，且同樣屬於抽象資料型態。
佇列與堆疊的差別在於佇列為「先進先出(FIFO,First In First Out)」，就好比先排隊的人先買到門票一樣。

圖片來源：http://runningmanmacau.weebly.com/uploads/2/7/2/0/27203993/s416834513424666157_p2_i1_w640.jpeg

如果以電腦的角度來看，堆疊的新增和刪除只能發生在頭節點，而佇列多了一個後端指標負責新增資料，前端指標用來讀取和刪除。

環狀佇列：佇列的實際應用之一，經常用於行車紀錄器或監視器之類的裝置，儲存特定天數的資料，若天數已滿則將第一天從前端刪除，並從末端加入新的一天。



依照這樣的做法就能成功創建了喔！

接著就實際操作看看，一樣要先創建新的專案୧| ” •̀ ل͜ •́ ” |୨

佇列：

std::cout << Q.front() << std::endl;為顯示佇列前端指標的資料，所以可以看到12位在佇列最前端，將其pop之後最前端的位置就變為3。

也可持續pop直到佇列為空的，首先要判斷佇列是否沒有資料。

這樣就完成最初始的佇列了喔，緊接著就來挑戰進階一些的環狀佇列。

環狀佇列：

直接在資源檔中新增項目即可，不需要創建新的專案。但同樣一個專案不能有兩個main程式，如果不知道怎麼操作的，可以看看上一篇文章

之後就可以開始實作了。

因為是環狀佇列，所以也可以從末端查詢資料。

這樣就完成了喔！

本日小結：今天做完了佇列和循環佇列，循環佇列和佇列的概念非常類似，但是如果要對循環佇列進行新增和刪除的話，都必須要用除以容量的餘數去考慮，這個部分比較複雜，需要花時間理解，佇列還有一些東西沒講到，會在之後的文章說明，明天將要進入資料結構中最重要的一環「樹」的部分१|˚–˚|५

佇列

#include<iostream>
using namespace std;

template<class T> class Queue {
	struct Node { //設立節點前端和後端指標
		T data;
		Node* next;
	};
	Node* front_;
	Node* rear;

public: //宣告函式
	Queue();
	bool push(T e);
	bool pop();
	T& front() { //查詢位在前端指標的資料
		if (front_ == rear) throw"佇列為空";
		return front_->next->data;
	}
	bool empty() {
		return front_ == rear;
	}
};

template<class T>
Queue<T>::Queue() { //初始化佇列
	front_ = rear = new Node();
	if (!front_) throw "No Memory";
	front_->next = 0;
}

template<class T> 
bool Queue<T>::push(T e) { //將資料新增置後端指標
	Node* p = new Node;
	if (!p)return false;
	p->data = e; p->next = 0;
	rear->next = p;
	rear = p;
	return true;
}
template<class T>
bool Queue<T>::pop() { // 將資料從前端指標刪除
	if (front_ == rear) return false;
	Node* p = front_->next;
	front_->next = p->next;
	if (rear == p) rear = front_;
	delete p;
	return true;
}

int main() {
	Queue<int> Q;
	Q.push(12); 
	Q.push(3); 
	Q.push(6); 
	std::cout << Q.front() << std::endl;
	Q.pop();
	std::cout << Q.front() << std::endl << std::endl;

	Q.push(30);
	Q.push(16);
	while (!Q.empty()) {
		std::cout << Q.front() << std::endl;
		Q.pop();
	}
}

環狀佇列

#include<iostream>
using namespace std;

template<typename T>
class SqlQueue { //創建新的佇列，並宣告會用到的變數名稱
	T* data;
	int front_, rear_, capacity;
public:
	SqlQueue(int cap = 3) {
		data = new T[cap]; if(!data) throw "儲存空間份配失敗";
		capacity = cap;
		front_ = rear_ = 0; //表示空陣列
	}
	bool push(T e) {
		if ((rear_ + 1) % capacity == front_) {
			T* p = new T[2 * capacity];
			if(!p) return false; //檢查佇列是否已滿，若rear_+1的餘數等於front，則佇列已滿
			for (int i = 0; i < capacity; i++)
				p[i] = data[i];
			delete[] data;
			data = p;
			capacity *= 2;
		}
		data[rear_] = e; rear_ = (rear_ + 1) % capacity; //%為相除的餘數 ex:3%5=2
		return true;
	}
	bool pop() {
		if (front_ == rear_) return false;
		front_ = (front_ + 1) % capacity;
		return true;
	}
	T& front() {
		if (front_ == rear_) throw "佇列為空";
		return data[front_];
	}
	T& rear() {
		if (front_ == rear_) throw "佇列為空";
		return data[(rear_ - 1 + capacity) % capacity];
	}
	int size() {
		return (rear_ - front_ + capacity) % capacity;
	} 
	bool empty() {
		return front_ == rear_;
	}
	bool clear() {
		front_ = rear_ = 0;
	}
};

int main() {
	SqlQueue<int> Q;
	Q.push(54);
	Q.push(94);
	Q.push(67);
	Q.push(39);
	Q.push(86);
	Q.push(13);
	int r = Q.rear();
	std::cout << r << std::endl;
	while (!Q.empty()) {
		int f = Q.front();
		Q.pop();
		std::cout << f << "　";
	}
	std::cout << std::endl;
}