算法經典：卡片遊戲（隊列模擬）

算法經典：卡片遊戲（隊列模擬）

《算法競賽入門經典》6.1 例題：桌上一疊牌，頂面為 1，依次編號 1~n。重複操作：丟棄頂牌，將新頂牌移至底部。輸出丟棄順序。樣例：n=7 → 1 3 5 7 4 2 6。

隊列模型

隊列（FIFO，先進先出）完美契合：隊頭出隊（丟棄），新隊頭出隊再入隊（移至底）。

C 語言手寫循環隊列

#include <stdio.h>
int queue[500];
int main() {
    int n, front, rear;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) queue[i] = i+1;  // 初始化
    front = 0; rear = n;  // [front, rear) 區間
    while (front < rear) {
        printf("%d ", queue[front++]);      // 丟棄隊頭
        queue[rear++] = queue[front++];     // 隊頭移至隊尾
    }
    return 0;
}

隱患：rear 會增長到 2n，若數組不夠大會越界寫入非法內存（不一定崩潰，極其危險）。解決：開大數組或用循環隊列（取模復用空間）。

C++ STL queue 版（推薦）

#include <cstdio>
#include <queue>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);
    while (!q.empty()) {
        printf("%d ", q.front()); q.pop();  // 丟棄
        q.push(q.front()); q.pop();         // 移至尾
    }
    return 0;
}

STL 版優勢

• 語義清晰：push/pop/front/empty 望文知義。
• 自動管理記憶體，無魔術數（無需預估 n 上限）。
• 變量少（無 front/rear），錯誤面小。
• 標準庫組件，可移植、經過充分測試。

算法複雜度

• 時間 O(n)：每張牌進隊出隊各常數次。
• 空間 O(n)：隊列存儲所有牌。

延伸思考

若改為「丟棄頂牌，將新頂牌移至底部，再丟棄頂牌……」（即每輪丟兩張、移一張），如何修改？只需調整循環體操作順序。隊列模型極靈活，適合各類「輪轉/丟棄」模擬題。