【剣指offer】【九度oj】スタックの圧入圧出

タイトルの説明:
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序であるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.
入力:
各テストケースには、次の3行があります.
第1の動作は1つの整数n(1<=n<=10000000)であり、シーケンスの長さを表す.
2行目はn個の整数を含み、スタックの圧入順序を表す.
3行目はn個の整数を含み、スタックのポップアップ順序を表す.
出力:
各テストケースに対応して、2番目のシーケンスが1番目のシーケンスのポップアップシーケンスであればYesを出力し、そうでなければNoを出力します.
サンプル入力:

5

1 2 3 4 5

4 5 3 2 1

5

1 2 3 4 5

4 3 5 1 2

サンプル出力:

Yes

No

概略的な考え方:スタックに格納された部分シーケンスを格納するために補助スタックを構築することができ、o(n)の時間的複雑さ内で問題を解決することができる.スタックシーケンスを出力する要素は、まず補助スタック(空でない場合)のスタックトップ要素と比較され、待たない場合はスタックシーケンスに入力する要素と比較されます.スタックシーケンスの要素と等しくない場合、現在のスタックシーケンスの要素は補助スタックに入り、スタックシーケンスの現在の要素はスタックシーケンスの後の要素と比較されます.補助スタックのスタックトップ要素とインスタックシーケンスのすべての要素がアウトスタックシーケンスの現在の要素と等しくない場合、このシーケンスは正しいアウトスタックシーケンスではありません.すべてのスタックシーケンス要素が比較されると、正しいスタックシーケンスになります.
コードは次のとおりです.

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

int a[100010],b[100010];
stack<int> s;

int main()
{
	int n,i,j;
	while(cin>>n)
	{
		for( i=0; i<n; i++ )
			cin>>a[i];
		for( i=0; i<n; i++ )
			cin>>b[i];
		i=j=0;
		while( !s.empty() )  //     ，         ，              。
			s.pop();
		while(i<=n)
		{
			if( !s.empty() && b[j]==s.top() )
			{
				s.pop();
				j++;
			}
			else
			{
				if( i==n )
					break;
				if( b[j]==a[i] )
				{
					i++;
					j++;
				}
				else
				{
					s.push(a[i]);
					i++;
				}
			}
		}
	if( j == n )
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	}
	return 0;
}