スタックの思想は駅を出る問題を解決する

問題1:アルゴリズムコンテストからの入門6.1
ある都市には駅があり、レールの敷設は図6-1に示す.n両の車両がA方向から駅に入り、駅に入る順番で1~nと番号がついています.あなたの任務は、ある特定の順序でB方向のレールに入って駅を出ることです.車両を再編するために、乗り換え駅Cを借りることができます.任意の複数の車両を停めることができる駅ですが、末端が閉鎖されているため、Cに入る車両は写真の逆の順序でCを出なければなりません.各車両について、AからCに移動すると、Aに戻ることができません.CからBに移動すると、Cに戻ることはできません.言い換えれば、任意の時点で、A->CとC->Bの2つの選択しかありません.
サンプル入力:
5
1 2 3 4 5
5 
5 4 1 2 3
6
654321
サンプル出力:
Yes
No
Yes
分析:
中継局Cにあります.車両は後進先出の原則に合致し、LIFO表、すなわちスタックとなり、スタックを実現するには1つの配列stackとスタックトップポインタ(常にスタックトップ要素を指す)が必要である.便宜上、ここで使用する配列下標はいずれも1から始まる.例えば、target[1]とは、ターゲットシーケンスにおける第1車両の番号である、stack[1]はスタックベース要素である、スタックが空でありtop=0の場合のみである.(それ以外の場合、スタックの下要素として0の下付きを開始すると、top=0の場合もスタックは空ではありません)
晴神の考え:

//     ，          。         ！！ 
#include<cstdio>
#include<stack>
using namespace std;
const int maxn=1010;
int arr[maxn]; 
stack<int> st;
int main(){
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&arr[i]);
	}
	while(!st.empty()){
		st.pop();
	}
	int current=1;
	for(i=1;i<=n;i++){//      6 Enter 6 5 4 3 2 1     ！ 
		st.push(i);
		while(!st.empty()&&st.top()==arr[current]){
			st.pop();
			current++;
		}
	}
	if(!st.empty()) printf("NO
");
	else printf("YES
");
	return 0;
} 

実装:

#include<stdio.h>
const int MAXN =1000+10;
int n,target[MAXN];
int stack[MAXN];

int main(){
	while(scanf("%d",&n)==1){
		int top=0;//top=0     ，                   
		int A=1,B=1;//              
		//        
		for(int i=1;i<=n;i++){
			scanf("%d",&target[i]);
		}
		//        
		int ok=1;
		while(B<n){		//              ，  
			if(A==target[B]) {A++;B++;}  //             
			else if(top && stack[top]==target[B]){top--;B++;}
			else if(A<=n){stack[++top]=A++;} //         ，      ，     
			else {ok=0;break;}//             ，      ，   ，      
		} 	
		printf("%s
",ok?"YES":"NO");
		/*getchar();
		getchar();*/
	}
	return 0; 
} 

問題1の解法2:(STLスタックで実現)
実装:

#include<stdio.h> 
#include<stack>//     
using namespace std;

const int MAXN =1000+10;

int n,target[MAXN];

int main(){
	while(scanf("%d",&n)==1){
		stack<int> s;
		int A=1,B=1;
		for(int i=1;i<=n;i++)
			scanf("%d",&target[i]);
		int ok=1;
		while(B<=n){
			if(A==target[B]){A++;B++;}
			else if(!s.empty() && s.top()==target[B]){s.pop();B++;}
			//          ，          
			else if(A<=n) s.push(A++);
			else{ok=0;break;} //        ，      ，      0，         
		}
		printf("%s
",ok?)
	} 
}

質問3:転載サイト:http://blog.csdn.net/gubojun123/article/details/8036482
1,2,3,4番の4列の列車が1つの桟式の列車のスケジューリングステーションを通過して、得られるスケジューリング結果はどれらがありますか?場合
n列の列車がスケジューリングステーションを通過する場合は、可能なすべてのスケジューリング結果を出力するアルゴリズムを設計してください. 
【回答】:
問題を解く構想:スタックは先進的な後出、後進的な先出の特徴を持っているので、どのスケジューリング結果も1,2,3,4であるべきである.
全配列の要素.スタックに入る順序は小さいから大きいので、スタックを出る順序は以下の条件を満たすべきです.
シーケンス内の任意の数は、その後のすべての小さい数が逆シーケンスであるべきであり、例えば4321は有効なスタックシーケンスである.
1423は有効なスタック結果ではありません(4の後にはそれより小さい2つの数2、3は逆順序ではありません).これにより、
この問題はアルゴリズムによってn個数の全配列を生成し,スタック規則を満たすシーケンスを出力することができる. 
この再帰定義に従って、再帰アルゴリズムは次のようになります.

#include<stdio.h>
int cont=1;
void print(int str[],int n);
void perm(int str[],int k,int n)
{
	int i,temp;
	if(k==n-1)print(str,n);//k n-1  ，        
	else{
		for(i=k;i<n;i++){//                 
			temp=str[k]; str[k]=str[i]; str[i]=temp;//   
			perm(str,k+1,n);//                  
			temp=str[i]; str[i]=str[k]; str[k]=temp;//    	
		}
	}
}
/*           str[]          ,       */ 
void print(int str[],int n) 
{
	int i,j,k,l,m,flag=1,b[2]; 
	for(i=0;i<n;i++)    /*    str[i]                 */ 
	{
		m=0; 
		for(j=i+1;j<n&&flag;j++){ 
 			if (str[i]>str[j])
	 		{
	 			if (m==0) b[m++]=str[j];//  str[i]       
     			else 
			 	{
			 		//               ，       
		 			if (str[j]>b[0]) flag=0;
		 			//           
        			else b[0]=str[j]; 
      			} 
      		}
		} 
	} 
	if(flag)        /*           str[]     */ 
	{   
		printf(" %2d:",cont++); //     
        for(i=0;i<n;i++) 
			printf("%d",str[i]);//     
        printf("
"); 
    } 
} 
int main() 
{
	int str[100],n,i; 
	printf("input a int:");		/*          */ 
	scanf("%d",&n); 
	for(i=0;i<n;i++)			/*        */ 
		str[i]=i+1;				// i      i+1 
	printf("input the result:
"); 
	perm(str,0,n);				//     
	printf("
"); 
	return 0; 
}