014寫程序將一個棧按升序排序,對這個棧是如何實現的，你不應該做任何特殊的假設(keep it up)

014寫程序將一個棧按升序排序,對這個棧是如何實現的，你不應該做任何特殊的假設(keep it up)

寫程序將一個棧按升序排序。對這個棧是如何實現的，你不應該做任何特殊的假設。
程序中能用到的棧操作有：push | pop |isEmpty
最容易想到的就是優先隊列來做此題，容易實現。

另外我們可以再用一個棧來實現棧的升序排列。

優先隊列：

//優先隊列來實現
void sortStack(std::stack& vStk)
{
	std::priority_queue, std::greater> Queue;
	while (!vStk.empty())
	{
		Queue.push(vStk.top());
		vStk.pop();
	}

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

附加棧來實現：

//附加一個棧來實現
void sortStack_(std::stack& vStk)
{
	std::stack 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);
	}
}

第二種算法有個極端的測試列子：如果原來棧的數據底部到頂部是從小到大的，例如：
1 2 3 4 5 6 7
那麼Tmp每次push一個不同的數就要清空棧中的所有數據，比如某時刻
vStk：1 2 3 4 5
Tmp：6 7
當Tmp要push 5的時候就要清空6 7，然後在push5，這時候vStk棧的數據增加：
vStk: 1 2 3 4 7 6
Tmp: 5