第 02 篇、queue 的運用 - 進階程式設計 - 多元選修 (高中)

像是在排隊結帳一樣，最先開始排隊的人，可以最先離開隊列完成結帳

# 基本用法

名稱	意義
`queue<int> q`	建立一個 `int` 型別的 `queue`
`q.size()`	佇列元素數量
`q.empty()`	判斷佇列是否為空
`q.push(x)`	從佇列「前端」加入一個元素 x
`q.pop()`	刪除佇列前端元素
`q.front()`	取得佇列前端元素
`q.back()`	取得後端元素

刪除 q.front() 並不會刪除前端元素

# 上課例題

# e155: 10935 - Throwing cards away I

給你一副照順序放好的紙牌，其中卡片的編號從 1~n，且 1 號排在最上面，n 號牌在最底下。
只要這副牌還有兩張以上，你就必須照以下的規則操作：
丟掉最上面的那張牌，然後把目前最上面的那張牌放到牌堆的最下面。
你的工作是找出每張牌被丟掉的順序，以及最後剩下的那張牌。

依照題意將 queue 的最上層取出並移除，
接著再取最上層推到佇列的最後面。

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n;
	while(cin >> n && n ){
	queue<int> Q;
	int card[100]={0},end=0;

	for(int i=1;i<=n;i++) Q.push(i);
	cout<<"Discarded cards: ";
	while(Q.size()>1){
	cout<<Q.front();
	if(Q.size()!=2)cout<<", ";
	card[end++]=Q.front();
	Q.pop();
	Q.push(Q.front());
	Q.pop();
	}
	cout<<"\nRemaining card: "<<Q.front()<<'\n';
	}
	}

# a982: 迷宮問題 #1

給你一個 NXN 格的迷宮，迷宮中以 #代表障礙物，以。代表路，你固定在 (2,2) 出發，目的地是 (n-1,n-1), 求包括起點和終點，最少路徑的長度。

將可行徑的點加入佇列中，不斷向外拓張，直到尋找到終點為止
( 就是基礎的 BFS 實作 )

	#include<bits/stdc++.h>
	using namespace std;
	int Maze[100][100];

	struct point{
	int x,y;
	};

	int main() {
	point k,next;
	int N;
	while(cin>>N) {
	queue<point> qu;
	for(int y=0;y<N&&getchar();y++)
	for(int x=0;x<N&&scanf("%c",&Maze[y][x]);Maze[y][x]=(Maze[y][x]=='.'?-1:-2),x++);
	k.x=1,k.y=1;
	qu.push(k);
	Maze[1][1]=1;
	while(!qu.empty()) {
	k = qu.front();qu.pop();
	next.x=k.x-1,next.y=k.y;
	if(Maze[next.y][next.x]==-1) {qu.push(next);Maze[next.y][next.x]=Maze[k.y][k.x]+1;}
	next.x=k.x+1,next.y=k.y;
	if(Maze[next.y][next.x]==-1) {qu.push(next);Maze[next.y][next.x]=Maze[k.y][k.x]+1;}
	next.x=k.x,next.y=k.y-1;
	if(Maze[next.y][next.x]==-1) {qu.push(next);Maze[next.y][next.x]=Maze[k.y][k.x]+1;}
	next.x=k.x,next.y=k.y+1;
	if(Maze[next.y][next.x]==-1) {qu.push(next);Maze[next.y][next.x]=Maze[k.y][k.x]+1;}
	}
	if(Maze[N-2][N-2]>0) printf("%d\n",Maze[N-2][N-2]);
	else printf("No solution!\n");
	}
	return 0;
	}

因為上下左右查詢的操作，重複性很大，因此，可以運用兩個陣列定義方向，再運用 for 迴圈簡化

	#include<bits/stdc++.h>
	using namespace std;
	int Maze[100][100];
	int dirX[4] = {-1,1,0,0},dirY[4] = {0,0,-1,1};

	struct point{
	int x,y;
	};

	int main() {
	point k,next;
	int N;
	while(cin>>N) {
	queue<point> qu;
	for(int y=0;y<N&&getchar();y++)
	for(int x=0;x<N&&scanf("%c",&Maze[y][x]);Maze[y][x]=(Maze[y][x]=='.'?-1:-2),x++);
	k.x=1,k.y=1;
	qu.push(k);
	Maze[1][1]=1;
	while(!qu.empty()) {
	k = qu.front();qu.pop();
	for(int i = 0;i<4;i++){
	next.x = k.x + dirX[i];
	next.y = k.y + dirY[i];
	if(Maze[next.y][next.x]==-1) {qu.push(next);Maze[next.y][next.x]=Maze[k.y][k.x]+1;}
	}
	}
	if(Maze[N-2][N-2]>0) printf("%d\n",Maze[N-2][N-2]);
	else printf("No solution!\n");
	}
	return 0;
	}

# 延伸練習

# e447: queue 練習

實作 queue 相關的幾個基本操作：

在隊伍尾端加入元素。
輸出隊伍最前端的元素。
刪除隊伍最前端的元素。

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n,k,t;
	queue <int> q;
	while(cin>>n){
	for(int i=0;i<n;i++) {
	cin>>k;
	if(k==1){
	cin>>t; q.push(t);
	}
	else if(k==2){
	if(q.empty())cout<<-1<<endl;
	else cout<<q.front()<<endl;
	}
	else if(k==3)
	if(!q.empty())q.pop();
	}
	}
	}

# d900: NOIP2010 2. 接水问题

水房裡一共裝有 m 個龍頭，水龍頭每秒鐘的供水量均為 1。
現在有 n 名同學準備接水，他們的初始接水順序已經確定。i 號同學的接水量為 wi。
接水開始時，1 到 m 號同學各佔一個水龍頭，並同時打開水龍頭接水。
當其中某名同學 j 完成其接水量要求 wj 後，下一名排隊等候接水的同學 k
馬上接替 j 同學的位置開始接水。
j 同學第 x 秒結束時完成接水，則 k 同學第 x+1 秒立刻開始接水。
現在給出 n 名同學的接水量，按照上述接水規則，問所有同學都接完水最少需要多少秒。

運用 priority_queue 將數據不斷的排序好，使最小的數值排在第一個，代表下一個完成接水的水龍頭所用的使用的總時間時間，
每次都取最小的數值做相加之後再推入，在過程中找最大值即可～～

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n,m,ans=0;
	priority_queue<int,vector<int>,greater<int> > pq;

	cin>>n>>m;
	for(int i=0;i<m;i++) pq.push(0);
	for(int i=0,wi;i<n;i++){
	cin>>wi;
	wi+=pq.top();pq.pop();
	ans=max(wi,ans);
	pq.push(wi);
	}
	cout<<ans<<"\n";
	return 0;
	}

# d406: 倒水時間

水由上而下的流，現在給你水管之間的地圖
水可以由上而下，可以往右流，往左流。

可是呢 ... 有時候也可以往上流
現在從地圖的最上方開始倒水，請輸出到的時間。

運用 BFS 計算出水流到的時間，如果 S=1，就多判斷是否可以往上走。

	#include <bits/stdc++.h>
	using namespace std;

	struct dot{
	int x,y,cnt;

	dot(int passX,int passY,int passCnt){
	x = passX,y = passY,cnt = passCnt;
	}
	};

	int main(){
	int S,t = 0;
	while(cin>>S){
	int n,m;
	cin>>n>>m;
	int a[n+2][m+2];
	queue< dot > q;
	for(int i = 1;i<=n;i++)
	for(int j = 1;j<=m;j++)
	cin>>a[i][j];

	for(int j = 1;j<=m;j++)
	if(a[1][j] == 1)
	q.push(dot(j,1,1));


	while(q.size()){
	int n_x = q.front().x;
	int n_y = q.front().y;
	int cnt = q.front().cnt;
	q.pop();
	if(a[n_y][n_x+1]==1){
	a[n_y][n_x+1] = cnt+1;
	q.push(dot(n_x+1,n_y,cnt+1));
	}
	if(a[n_y][n_x-1]==1){
	a[n_y][n_x-1] = cnt+1;
	q.push(dot(n_x-1,n_y,cnt+1));
	}
	if(a[n_y+1][n_x]==1){
	a[n_y+1][n_x] = cnt+1;
	q.push(dot(n_x,n_y+1,cnt+1));
	}
	if(S==1){
	if(a[n_y-1][n_x]==1&&n_y-1 != 1){
	a[n_y-1][n_x] = cnt+1;
	q.push(dot(n_x,n_y-1,cnt+1));
	}
	}
	}
	for(int i = 2;i<=n;i++)
	for(int j = 1;j<=m;j++)
	if(a[i][j]==1)
	a[i][j] = 0;

	cout<<"Case "<< ++t <<":\n";
	for(int i = 1;i<=n;i++){
	for(int j = 1;j<=m;j++)
	cout<<a[i][j]<<" ";
	cout<<endl;
	}
	}
	}