《算法競賽入門經典》6.1棧和隊列-卡片游戲，算法競賽入門經典
桌上有一疊牌，從第一張牌（即位於頂面的牌）開始從上往下依次編號為1~n；當至少還剩兩張牌時進行以下操作：把第一張牌扔掉，然後把新的第一張放到整疊牌的最後。輸入n，輸出每次扔掉的牌。
樣例輸入：
7
樣例輸出：
1 3 5 7 4 2 6
![]()
1 #include <stdio.h>
2 int queue[500];
3 int main()
4 {
5 int i, n, front, rear; //n<=strlen(queue)/2
6 scanf("%d", &n);
7 for(i = 0; i < n; i++)
8 queue[i] = i+1; //初始化隊列
9 front = 0; //隊首元素的位置
10 rear = n; //隊尾元素的後一個位置
11 while(front < rear) //當隊列非空
12 {
13 printf("%d ", queue[front++]); //輸出並拋棄隊首元素
14 queue[rear++] = queue[front++]; //隊首元素轉移到隊尾
15 }
16 return 0;
17 }
View Code
分析：
1.隊列：每次從排頭拿到兩個，其中第二個再排到尾部；這種數據結構稱為隊列（queue），或FIFO表。其中FIFO表示先進先出（First In，First Out），符合日常生活中的排隊。
2.用一個數組queue來實現這個隊列，再設兩個指針front和rear。盡管運行結果沒錯，但如果在最後把rear的值打印出來，rear會比n大（恰好是2n）。換言之，在程序運行的後期，queue[rear++]=queue[front++]讀寫了非法內存（讀寫非法內存不一定導致程序崩潰）！因此要麼把數組空間開大些；要麼采用一種稱為循環隊列的技術，重用已出隊元素占用的空間。
C++提供了一種更加簡單的處理方式—STL隊列：
![]()
1 #include <cstdio>
2 #include <queue>
3 using namespace std;
4 queue<int> q;
5 int main()
6 {
7 int i, n;
8 scanf("%d", &n);
9 for(i = 0; i < n; i++)
10 q.push(i+1); //初始化隊列
11 while(!q.empty()) //當隊列非空
12 {
13 printf("%d ", q.front()); //打印隊首元素
14 q.pop(); //拋棄隊首元素
15 q.push(q.front()); //把新的隊首元素加入隊列
16 q.pop(); //拋棄隊首元素
17 }
18 return 0;
19 }
View Code
分析：
1.該程序代碼並沒有簡潔很多，但可讀性大大增強：一方面體現在“queue”、“rear”這些望文知義的命名，另一方面體現在STL庫的標准性（它是C++不可分割的組成部分）。
2.減少魔術數（majic number），即不需要事先知道n的大小；減少變量個數（少用了兩個變量front和rear）都是提高代碼可讀性，減少錯誤可能性的重要手段。
