【算法】使用栈为栈的元素排序

使用栈为栈的元素排序

栈中的元素采用LIFO (Last In First Out)，即后进先出。
基本思路就是：

1. 从源栈中取出一个元素
2. 在临时栈中找到元素的位置，该位置到栈顶不合适的元素（大于或者小于，或者其他pred类型）将其全部“扔”回源栈
3. 循环1和2即可得到新的临时栈，其中元素就是排好的元素
   实现代码如下：

stack<int> srcStack;
stack<int> tmpStack;

void sortStack()
{
	while (!srcStack.empty())
	{
		int temp = srcStack.top();
		srcStack.pop();

		//tmpStack找到temp合适的位置,大于temp的将重新回到srcStack
		while (!tmpStack.empty() && tmpStack.top() > temp)
		{
			srcStack.push(tmpStack.top());
			tmpStack.pop();
		}
		tmpStack.push(temp);
	}
}

int main()
{
	srcStack.push(5);
	srcStack.push(3);
	srcStack.push(7);
	srcStack.push(1);
	srcStack.push(9);

	sortStack();

	while (!tmpStack.empty())
	{
		cout << tmpStack.top() << " ";
		tmpStack.pop();
	}
	getchar();
	return 0;
}

打印：9 7 5 3 1