本帖最後由 鄭又綸 於 2024-9-21 09:28 編輯
Queue 的概念
queue（佇列）是一種資料結構，用來模擬生活中的「排隊」情境。在 queue 中，元素遵循「先進先出」（FIFO, First In First Out）的規則。這意味著，最先加入 queue 的元素會最先被取出，而新加入的元素會排在最後
你可以想像 queue 就像是一列排隊等候的人：
排隊加入（enqueue）：當一個新的人來排隊時，他會站到隊伍的最後面。
前面離開（dequeue）：當服務窗口處理排隊的人時，最前面的人先被服務並離開隊伍。
隊伍中的順序：隊伍中的順序是固定的，按照人們進來的先後順序排列，不會有人插隊到中間或前面。
以下是 queue 的一些特性：
FIFO（First In First Out）：最先加入的元素最先被取出。
只能從一端插入（尾端），另一端取出（前端）：這與「堆疊（stack）」不同，堆疊是「後進先出」（LIFO, Last In First Out），只能從一端進行操作。
基本語法和操作
要使用 queue，需要包含標頭檔 <queue> 。以下是 queue 的基本操作和用法：
引入 queue 標頭檔：- #include <queue> // 引入 queue 標頭檔
queue<資料型別> 變數名稱;
宣告一個資料型別為 int 的 queue：- queue<int> q; // 宣告一個空的整數佇列
push(x)：將元素 x 加入佇列的尾端。
pop()：移除佇列最前端的元素（FIFO 的原理）。
front()：取得佇列最前端的元素（即將被取出的元素）。
back()：取得佇列尾端的元素（最近加入的元素）。
empty()：檢查佇列是否為空。為空則回傳 true。
size()：回傳佇列中元素的個數。
操作範例：- #include <iostream>
- #include <queue> // 引入 queue 標頭檔
- using namespace std;
- int main() {
- queue<int> q; // 宣告一個整數型別的 queue
- // 加入元素到佇列中
- q.push(10); // 佇列中有 10
- q.push(20); // 佇列中有 10, 20
- q.push(30); // 佇列中有 10, 20, 30
- // 取出並顯示佇列中的元素
- cout << "最前面的元素是: " << q.front() << endl; // 輸出 10
- cout << "尾端的元素是: " << q.back() << endl; // 輸出 30
-
- // 移除最前面的元素
- q.pop(); // 移除 10，佇列剩下 20, 30
- cout << "最前面的元素是: " << q.front() << endl; // 輸出 20
- cout << "目前佇列的大小: " << q.size() << endl; // 輸出 2
- return 0;
- }
記憶體空間初始化：
程式中有四個記憶體空間，用來儲存輸入的數字。一開始這四個記憶體空間全都是「0」，表示它們是空的（用字串 "0000" 表示）。
輸入資料：
讓使用者輸入十個小於 10 的正整數。
如果當前記憶體空間還沒滿，就依序放進去。
當記憶體空間滿的時候（即已經有四個數字），每當有新的數字要進來時，就要使用 FIFO 規則來替換掉最早進入記憶體的數字。
FIFO 規則：
當記憶體空間已滿且新的數字不在記憶體中時，會先將最先進入記憶體的數字「淘汰」掉，然後再把新的數字放進去。
比如，假設記憶體空間中目前有 7 5 1 2，如果要放入新的數字 3，那麼 7 會被替換掉，變成 3 5 1 2。
輸出結果：
每次輸入或替換完畢後，都會輸出當前記憶體空間中的內容。
每個數字用兩個欄位寬顯示，左對齊。如果記憶體中有空位，則顯示為 0。
範例說明
假設輸入以下十個數字：7 5 1 2 5 3 5 4 2 3
前四次輸入（記憶體未滿）：
7 -> 7 0 0 0
5 -> 7 5 0 0
1 -> 7 5 1 0
2 -> 7 5 1 2
第五次輸入：
5 已經在記憶體中，所以記憶體不變：7 5 1 2
第六次輸入：
3 不在記憶體中，使用 FIFO 規則將 7 淘汰：3 5 1 2
第七次輸入：
5 已經在記憶體中，記憶體不變：3 5 1 2
第八次輸入：
4 不在記憶體中，使用 FIFO 規則將 5 淘汰：3 4 1 2
第九次輸入：
2 已經在記憶體中，記憶體不變：3 4 1 2
第十次輸入：
3 已經在記憶體中，記憶體不變：3 4 1 2
逐步解析程式碼- #include<bits/stdc++.h>
- using namespace std;
- string s="0000"; // 初始記憶體空間，四個位置都是 0，表示空的。
- queue<char> q; // FIFO 用的佇列，來追蹤先進來的數字。
- int main() {
- for(int i = 0; i < 10; i++) { // 要輸入 10 個數字
- if(i < 4) { // 前四個數字直接放進記憶體
- cin >> s[i]; // 依序放到字串 s 的位置
- q.push(s[i]); // 加入佇列中
- } else { // 超過四個數字之後，需要判斷是否替換
- char in, ot;
- cin >> in; // 輸入新的數字
- if(s.find(in) == -1) { // 如果新的數字不在記憶體中
- q.push(in); // 加入佇列
- ot = q.front(); // 取出最先進來的數字（要被淘汰的）
- q.pop(); // 從佇列中移除最先進來的數字
- int idx = s.find(ot); // 找到這個數字在記憶體的位置
- s[idx] = in; // 替換成新的數字
- }
- }
- // 輸出目前記憶體的狀態
- printf("%c %c %c %c \n", s[0], s[1], s[2], s[3]);
- }
- return 0;
- }
|
