014ライタはスタックを昇順に並べ替えて、このスタックがどのように実現されているのか、特別な仮定をするべきではありません(keep it up)


ライトプログラムはスタックを昇順に並べ替えます.このスタックがどのように実現されているかについては、特別な仮定をするべきではありません.
プログラムで使用できるスタック操作は、push|pop|isEmpty
一番考えやすいのは優先キューでこの問題をして、実現しやすいことです.
さらに、スタックの昇順配列を実現するために、スタックをもう1つ使用することができます.
優先キュー:
//       
void sortStack(std::stack<int>& vStk)
{
	std::priority_queue<int, std::vector<int>, std::greater<int>> Queue;
	while (!vStk.empty())
	{
		Queue.push(vStk.top());
		vStk.pop();
	}

	while (!Queue.empty())
	{
		vStk.push(Queue.top());
		Queue.pop();
	}
}

追加のスタックで実装:
//        
void sortStack_(std::stack<int>& vStk)
{
	std::stack<int> Tmp;
	while (!vStk.empty())
	{
		int Top = vStk.top();
		vStk.pop();
		while (!Tmp.top() && Top < Tmp.top())
		{
			vStk.push(Tmp.top());
			Tmp.pop();
		}
		Tmp.push(Top);
	}
}

第2のアルゴリズムには極端なテスト列があります.元のスタックのデータの下部から上部までが小さい場合、例えば:
1 2 3 4 5 6 7
Tmpはpushのたびに異なる数でスタック内のすべてのデータを空にします.例えば、ある時点で
vStk:1 2 3 4 5
Tmp:6 7
Tmpがpush 5を必要とする場合は6 7を空にし、push 5でvStkスタックのデータが増加します.
vStk: 1 2 3 4 7 6
Tmp: 5