【程序员金典】双栈排序

本文主要是介绍【程序员金典】双栈排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到最后一个元素。
测试样例：
[1,2,3,4,5]
返回：[5,4,3,2,1]

解析：

思路：

1. 先看下图
   
   初始栈initStack中存放的数组中待排序的数；临时栈tempStack中存放的是已经排好序的数。现在继续对初始栈中的数进行排序，5应当插入到临时栈哪个位置？

2. 5应该插入到8下，3上。具体如何操作呢？首先初始栈initStack弹出待排序的数5，存入变量tmp；而临时栈tempStack弹出比5大的数，并存入初始化栈initStack中。如下图：

3. 将变量tmp保存的数插入到临时栈tempStack中去，由于初始化栈initStack中8，12是排好序的，可以再直接弹入临时栈中，再对下一个数10进行如上操作。
   

c++代码

class TwoStacks {
public:vector<int> 

这篇关于【程序员金典】双栈排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---