3.6双栈排序

题目描述

请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。

测试样例：

[1,2,3,4,5]

返回：[5,4,3,2,1]

学习总结：1.栈的使用判断是否为空用empty（）函数
　　　　　2.栈和向量的转换，栈只能访问到栈顶元素。push有参数，pop无参数。
　　　　　3.双栈排序的使用技巧，先比栈顶，一次排完后保持临时栈底元素最小。

class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        //只用到一个栈来暂存中间变量，这个比较有难度
        stack<int> num;
        stack<int> temp;
        int val;
        //只能访问栈顶元素，先进行入栈，通过逆序将向量进行入栈，第一个元素为栈顶元素
        for(int i = numbers.size()-1; i >= 0 ; i--){
            num.push(numbers[i]);
        }
        val = num.top();
        temp.push(val);
        num.pop();
        while(!num.empty()) {
            if(num.top() < temp.top()) { //两个栈顶比较，则进行压临时栈操作
                val = num.top();
                num.pop();
                while(!temp.empty() && temp.top() > val) { //大于比较值，则统统出临时栈
                    num.push(temp.top());
                    temp.pop();
                }
                temp.push(val); //比较值进行入临时栈
            }
            else { //栈的退回，大于临时栈顶元素回临时栈
                temp.push(num.top());
                num.pop();
            }
        }
        //最后返回的向量形式，所以进行转换
        for(int j = 0; j < numbers.size(); j++) {
            numbers[j] = temp.top();
            temp.pop();
        }
        return numbers;      
    }
};