隊列（Queue）是一種常見的資料結構，它遵循先進先出（FIFO）的原則，這意味著在隊列中添加的元素將按照它們被添加的順序被移除。
實作之前首先要看Queue是如何運作的，back會記錄容器內資料隊列的尾端而Front會記錄資料隊列的頭，執行Enqueue時在尾端新增資料、Dequeue時在頭端拿出資料，這就是先進先出（FIFO）
再來要進行實作，首先是創建對象，以Array實作除了記錄數據需要的矩陣以外還需要四個變數、size紀錄目前有的內容大小，capacity紀錄目前容器的容量、再來是front記住容器內資料的頭位置back記住容器內資料的尾端位置。
執行建構子時將size front back都先設為0，因為這時容器內還沒有任何資料，而記錄容量的capacity則是由宣告時提供的參數決定，如果是沒有提供參數的宣告則是使用#define SIZE 10的SIZE設為１０
| private: Datatype *data; int size; // 紀錄內容大小 int capacity; // 紀錄容量 int front; // 以front記住容器頭位置 int back; // 以back記住容器尾端位置 public: Queue() { size = 0; capacity = SIZE; data = new Datatype[capacity]; front = 0; back = 0; } Queue(int Size) { size = 0; capacity = Size; data = new Datatype[capacity]; front = 0; back = 0; } ~Queue() { delete[] data; } |
然後是方便程式編寫執行的程式Front() Bcak()分別查看隊首隊尾的資料
is_Empty() is_Full()分別判斷容器是否為空或是已滿| Datatype Front() { return data[front]; } Datatype Bcak() { return data[back]; } bool is_Empty() { return (size == 0); } bool is_Full() { return (capacity == size); } |
用Array實作Dequeue()的方式很簡單，只要把front提前也就是+1就能模擬出移出一個元素的動作
| void Dequeue() // Dequeue { front++; size--; } |
然後就是要用Array實作時需要處裡的最麻煩的部分Enqueue新增元素
在Enqueue(Datatype element)新增資料
如果容器已滿需要呼叫expand()擴張容器內空間
如果容器未滿則呼叫reset()來重製矩陣
雖然只要用循環佇列（Circular Queue）就不用reset()這麼麻煩但是又要Circular Queue又要能擴充空間會很麻煩
void Enqueue(Datatype element) // Enqueue { if (is_Empty()) // 容器為空時直接新增資料於data[0]並同時設為頭尾 { data[0] = element; back = data[0]; front = data[0]; size++; // cout << "push " << data[back] << " "; return; } else if (is_Full()) // 容器已滿時進行擴張 { //cout << "Queue is full!" << endl; expand(); size++; back++; data[back] = element; // cout << "push " << data[back] << " "; return; } else { if (back == capacity - 1)//當back已經到達矩陣中最後一個元素時需要進行重設 { // cout << (capacity - 1) << endl; //reset(); back++; data[back] = element; size++; //cout << "reset" << endl; return; } back++; data[back] = element; // cout << "push " << data[back] << " "; size++; } } void expand() // 擴張容器內的空間 { // 創建一個暫時的陣列temp儲存data內的資料 Datatype temp[capacity + 1]; int p = front; for (int i = 0; i < capacity; i++) { temp[i] = data[p]; p++; } // 紀錄front and back的距離 用於修正重設後back位置 int distance_front_back = back - front; delete[] data; // 創建一個容量+1的新data矩陣並完成資料轉移 data = new Datatype[capacity + 1]; for (int i = 0; i < capacity; i++) { data[i] = temp[i]; } front = 0; back = distance_front_back; capacity++; } void reset() // 重設矩陣內容將整個隊列往前移 讓第一個元素能放在data[0]的位置 { // 創建一個暫時的陣列temp儲存data內的資料 Datatype temp[capacity]; int p = front; for (int i = 0; i < capacity; i++) { temp[i] = data[p]; p++; } // 紀錄front and back的距離 用於修正重設後back位置 int distance_front_back = back - front; // 完成重設 delete[] data; data = new Datatype[capacity]; for (int i = 0; i < capacity; i++) { data[i] = temp[i]; } front = 0; back = distance_front_back; } |
完整程式碼:
| #include <iostream> using namespace std; #define SIZE 10 template <class Datatype> class Queue { private: Datatype *data; int size; // 紀錄內容大小 int capacity; // 紀錄容量 int front; // 以front記住容器頭位置 int back; // 以back記住容器尾端位置 public: Queue() { size = 0; capacity = SIZE; data = new Datatype[capacity]; front = 0; back = 0; } Queue(int Size) { size = 0; capacity = Size; data = new Datatype[capacity]; front = 0; back = 0; } ~Queue() { delete[] data; } bool is_Empty() { return (size == 0); } bool is_Full() { return (capacity == size); } void Enqueue(Datatype element) // Enqueue { if (is_Empty()) // 容器為空時直接新增資料於data[0]並同時設為頭尾 { data[0] = element; back = data[0]; front = data[0]; size++; // cout << "push " << data[back] << " "; return; } else if (is_Full()) // 容器已滿時進行擴張 { //cout << "Queue is full!" << endl; expand(); size++; back++; data[back] = element; // cout << "push " << data[back] << " "; return; } else { if (back == capacity - 1)//當back已經到達矩陣中最後一個元素時需要進行重設 { // cout << (capacity - 1) << endl; //reset(); back++; data[back] = element; size++; //cout << "reset" << endl; return; } back++; data[back] = element; // cout << "push " << data[back] << " "; size++; } } void expand() // 擴張容器內的空間 { // 創建一個暫時的陣列temp儲存data內的資料 Datatype temp[capacity + 1]; int p = front; for (int i = 0; i < capacity; i++) { temp[i] = data[p]; p++; } // 紀錄front and back的距離 用於修正重設後back位置 int distance_front_back = back - front; delete[] data; // 創建一個容量+1的新data矩陣並完成資料轉移 data = new Datatype[capacity + 1]; for (int i = 0; i < capacity; i++) { data[i] = temp[i]; } front = 0; back = distance_front_back; capacity++; } void reset() // 重設矩陣內容將整個隊列往前移 讓第一個元素能放在data[0]的位置 { // 創建一個暫時的陣列temp儲存data內的資料 Datatype temp[capacity]; int p = front; for (int i = 0; i < capacity; i++) { temp[i] = data[p]; p++; } // 紀錄front and back的距離 用於修正重設後back位置 int distance_front_back = back - front; // 完成重設 delete[] data; data = new Datatype[capacity]; for (int i = 0; i < capacity; i++) { data[i] = temp[i]; } front = 0; back = distance_front_back; } void Dequeue() // Dequeue { front++; size--; } Datatype Front() { return data[front]; } Datatype Bcak() { return data[back]; } void print() { // cout << "front:" << front << endl; // cout << "back:" << back << endl; for (int i = 0; i < size; i++) { cout << data[(front + i)] << " "; } cout << endl; /*for (int i = 0; i < size; i++) { cout << data[(back - i)] << " "; } cout << endl;*/ } }; int main() { Queue<int> test1(10); for (int i = 0; i < 10; i++) { test1.Enqueue(i); } test1.Dequeue(); test1.Dequeue(); test1.Enqueue(1); test1.Enqueue(1); test1.Enqueue(1); test1.Dequeue(); test1.Dequeue(); test1.Enqueue(1); test1.Enqueue(1); cout << "content:" << endl; test1.print(); cout << "content:" << endl; test1.print(); return 0; } |
