【プログラマー面接宝典】スタックとキューに関する面接問題

1、集合スタック
タイトルの説明:
複数のスタックからなるデータ構造SetOfStacksを実装してください.各スタックのサイズはsizeで、現在のスタックが満たされている場合、新しいスタックが作成されます.このデータ構造は、通常のスタックと同じpushおよびpop動作をサポートする必要があります.
1つの操作シーケンスint[][2]ope(C++はvector>)が与えられ、各操作の最初の数は操作タイプを表し、1であればpush操作、後の数はpushに対応する数字である.2であればpop操作であり,後の数は意味がない.すべての操作を完了したSetOfStacksの順序は下から上で、デフォルトの初期のSetOfStacksは空です.データの合法性を保証する.
問題の分析:
(1)まずsizeに達するスタックvecを確立し、sizeに達するスタック(vector>)を格納する.
(2)tempスタックを作成して現在操作するデータ(vector)を操作する.
(3)入ってくるとforループが0~opeを巡る.size()は、スタックを押す場合ope[i][0]=1で、スタックtempスタックの要素がsize個に達しているかどうかを判断し、達したらvecスタックに先に圧入し、tempスタックを空にし、tempのスタック操作を実行し、否者は直接要素をtempに圧入する.
(4)スタックを出る場合は、まずtempスタックが空であるか否かを判断し、空でない場合は直接tempから要素を投げ出す.そうでない場合はtempをvecスタックのスタックトップに向け、vecとtempの両方に要素スタック出し動作を実行させる.
(5)最後にtemp中の要素の個数が空でなければtempをvecに押し込みvecに戻せばよい
コード実装

vector > setOfStacks(vector > ope, int size) {
	vector > stack;
	vector temp;
	for (int i = 0; i0){
				temp.pop_back();
			}
			else{
				temp = stack[stack.size() - 1];
				temp.pop_back();
				stack.pop_back();
			}

		}
	}
	if (temp.size() != 0)
		stack.push_back(temp);
	return stack;
}

2、2つのスタック実装キュー
2つのスタックで1つのキューを実現
3、ダブルスタック並べ替え
タイトルの説明:
スタックを昇順にソートするプログラムを作成してください(つまり、最大要素はスタックの上部にあります).追加のスタックを使用して一時データを格納することはできませんが、要素を別のデータ構造にコピーすることはできません.
int[]numbers(C++でvector)が与えられ、最初の要素がスタックの上部にある場合は、ソートされたスタックに戻ります.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
テストサンプル:[1,2,3,4,5]戻り:[5,4,3,2,1]
問題の分析:
(1)まず、最終的に戻るスタックを格納するための補助スタックtempを確立する.
(2)numbersの最初の要素pushを補助スタックに挿入し、その後のプロセスは挿入ソートの考え方と全く同じであるが、vectorのインタフェースを用いて実現される.
(3)スタックを昇順に並べ替えるためnumbers[i]
(4)すべての要素を操作した後、最後に並べたtempスタックに戻ればよい
コード実装:

vector twoStacksSort(vector numbers) {
	vector temp;
	int size = numbers.size();
	if (size <= 1)
		return numbers;
	temp.push_back(numbers[0]);
	for (int i = 1; i::iterator it;
			for (it = temp.begin(); it != temp.end(); ++it)
			{
				if (*it

4、猫と犬の収容所
タイトルの説明:
ある動物収容所には猫と犬しか収容されていないが、特殊な養子縁組規則があり、養子縁組者には2つの養子縁組方式があり、1つ目はすべての動物の中で最も早く収容所に入ったものを直接養子縁組し、2つ目は養子縁組の動物タイプ(猫または犬)を選択し、この動物の中で最も早く収容所に入ったものを養子縁組する.
操作シーケンスint[][2]ope(C++でvector>)は、すべてのイベントを表す.1番目の元素が1であれば、動物が収容所に入ることを表し、2番目の元素は動物の番号であり、正数は犬を表し、負数は猫を表す.1番目の要素が2であれば、養子縁組動物を表し、2番目の要素が0であれば、1番目の養子縁組方式を採用し、1であれば養子縁組犬を指定し、-1であれば養子縁組猫を指定する.養子縁組のシーケンスを順番に返してください.不法な操作、すなわち養子縁組の要求に合致する動物がいなければ、今回の養子縁組操作は無視される.
テストサンプル:[[1,1],[1,-1],[2,0],[2,-1]]戻り:[1,-1]
問題の分析:
(1)テーマの要求に基づいて、この問題は私たちの論理思想を考査して、問題の説明はすでに非常にはっきりしていて、それに応じてコードで実現すればいいです.
(2)まず2つのvectorの変数vecとarrを確立し、収容所に入った動物と養子縁組された動物をそれぞれ保存する.
(3)次は状況別で、ope[i][0]=1が動物が入ってきたことを示すと、arrに絶えずpushするだけで、そうでなければ動物が養子縁組されることを示し、養子縁組される動物には3つの状況がある.
(4)arrスタックが空でない場合、ope[i][1]=0は、arrから順にpushし、push後のデータをarrからeraseするだけで、ope[i][1]=1/-1の場合、方法は同じであり、arrを巡って必要な要素を見つけ、そのpushをvecに、arrからeraseに落とす必要がある.
(5)最後にすべての要素が処理され,処理後のresを返すだけでよい.
コード実装:

vector asylum(vector > ope)
{
	vector res, arr;
	int size = ope.size();
	if (ope.empty())
		return arr;
	for (int i = 0; i < size; i++)
	{
		if (ope[i][0] == 1)
		{
			res.push_back(ope[i][1]);
		}
		else if (ope[i][0] == 2)
		{
			if (!arr.empty())
			{
				if (ope[i][1] == 0)
				{
					res.push_back(arr[0]);
					arr.erase(arr.begin());
				}
				else if (ope[i][1] == 1)
				{
					for (int j = 0; j < res.size(); j++)
					{
						if (arr[j]>0)
						{
							res.push_back(arr[j]);
							arr.erase(arr.begin() + j);
							break;
						}
					}
				}
				else if (ope[i][1] == 2)
				{
					for (int j = 0; j < res.size(); j++)
					{
						if (arr[j]>0)
						{
							res.push_back(arr[j]);
							arr.erase(arr.begin() + j);
							break;
						}
					}
				}
			}
		}
		return res;
	}
}