首页 > 试题广场 >

双栈排序

[编程题]双栈排序
  • 热度指数:16110 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个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进行如上操作。
图片说明

代码如下:

import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        //构建栈,并初始化栈
        Stack<Integer> initStack = new Stack<>();
        for (int i = 0 ; i < numbers.length; i++){
            initStack.push(numbers[i]);
        }

        //构建辅助栈,用来存放排好序的数
        Stack<Integer> tempStack = new Stack<>();
        while(!initStack.isEmpty()){

            if (tempStack.isEmpty()){
                tempStack.push(initStack.pop());
            }else {
                //新建变量,存储原始栈中待排序的栈
                int tmp = initStack.pop();

                //将辅助栈中的排好序中的大于tmp的数放入原始栈中
                while (!tempStack.isEmpty() && tempStack.peek() > tmp){
                    initStack.push(tempStack.pop());
                }
                //辅助栈存储之前保存的变量
                tempStack.push(tmp);

            }


        }

        while(!tempStack.isEmpty()){
            list.add(tempStack.pop());
        }

        return list;
    }
}
发表于 2017-06-22 15:53:11 回复(3)
如果严格按照题目中“给定一个int[]  numbers (C++中为vector&ltint>),其中第一个元素为栈顶”的意思来,这里的第一个元素应该是指数组的第0项,即第0项为栈顶元素,那么就应该倒序来push,讨论中很多回答都是正序来push,但这个影响不大。
虽然Java中Stack继承Vector,但既然这里题目主要是考察双栈排序,那就不要用get(),remove(),以及peek()等方法,就只用push()与pop()来完成对栈中元素的操作。
public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
    // write code here
    ArrayList<Integer> result = new ArrayList<>(numbers.length);

    //初始化原始栈
    Stack<Integer> stack = new Stack<>();
    int index = numbers.length - 1;
    for (int i = index; i >= 0; i--) {
        stack.push(numbers[i]);
    }

    Stack<Integer> resultStack = new Stack<>();//额外的栈
    while (!stack.empty()) {
        if (resultStack.empty()) {
            resultStack.push(stack.pop());
        } else {
            int a = stack.pop();
            int b = resultStack.pop();
            if (a < b) {
                stack.push(b);
                while (!resultStack.empty() && a < (b = resultStack.pop())) {
                    stack.push(b);
                }
            }
            if (a >= b) {
                resultStack.push(b);
            }
            resultStack.push(a);
        }
    }

    //返回ArrayList结果
    while (!resultStack.empty()) {
        result.add(resultStack.pop());
    }
    return result;
}

发表于 2016-07-12 15:01:41 回复(0)
Ron头像 Ron
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
    	/*
    	 * 思路:
    	 * 只用两个栈排序,一个是有序的asc,另一个是无序的buffer就可以实现对一个栈的排序。如何有序,当原始栈只有一个时就有序了
    	 * numbers中第一个为栈顶
    	 * 主要是解决buffer栈顶元素放在asc的位置
    	 * 1. buffer栈顶大于等于asc栈顶或asc空
    	 * 	直接放
    	 * 2. buffer栈顶小于asc栈顶
    	 *  buffer栈顶值出栈,临时变量存放buffer栈顶值
    	 * 	循环从asc中拿出值放到buffer直至asc空或满足1条件
    	 */
    	if(numbers == null || numbers.length == 0){
    		return null;
    	}
    	int length = numbers.length;
    	ArrayList<Integer> res = new ArrayList<Integer>(length);
    	Stack<Integer> buffer = new Stack<Integer>();
    	Stack<Integer> ascStack = new Stack<Integer>();
    	//初始状态,buffer中放了length-1个与numbers逆序的数串,asc只剩栈底元素
    	for(int i = 0; i < length-1; i++){
    		buffer.push(numbers[i]);
    	}
    	ascStack.push(numbers[length-1]);
    	//排序
    	int bufTop = 0;
    	while(buffer.size() > 0){
    		if(ascStack.isEmpty() || buffer.peek() >= ascStack.peek()){
    			ascStack.push(buffer.pop());
    		}else{
    			bufTop = buffer.pop();
    			int count_curBuffer = buffer.size();
    			while(!ascStack.isEmpty() && bufTop < ascStack.peek()){
    				buffer.push(ascStack.pop());
    			}
    			ascStack.push(bufTop);
    			int count_numsFromAsc = buffer.size()-count_curBuffer;
    			for(int i = 0; i < count_numsFromAsc; i++){
    				ascStack.push(buffer.pop());
    			}
    		}
    	}
    	for(int i = 0; i < length; i++){
    		res.add(ascStack.pop());
    	}
    	return res;
    }

编辑于 2016-04-18 16:46:24 回复(0)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
			vector<int> forSort;
			if(numbers.size() <= 1) return numbers;
			forSort.push_back(numbers.back());
			numbers.pop_back();
			while(numbers.size() > 0)
			{
				int temp = numbers.back();
				numbers.pop_back();
				int popNum = 0;  // 出栈元素的数量
				while(!forSort.empty() && temp < forSort.back()){
					numbers.push_back(forSort.back());
					forSort.pop_back();
					popNum++;
				}
				forSort.push_back(temp);
				while(popNum > 0){
					forSort.push_back(numbers.back());
					numbers.pop_back();
					popNum--;
				}
			}
			reverse(forSort.begin(),forSort.end());
			return forSort;
	}
};
插入排,一个作为备用存储临时元素。
发表于 2016-01-09 22:36:28 回复(3)
    vector<int> twoStacksSort(vector<int> numbers) {
        vector<int> stack;
        while(!numbers.empty()){
            int num = numbers.back();
            numbers.pop_back();
            while(!stack.empty() && num > stack.back()){
                numbers.push_back(stack.back());
                stack.pop_back();
            }
            stack.push_back(num);
        }
        return stack;
    }

发表于 2017-08-18 16:25:17 回复(0)
import java.util.*;
/*
是左程云《程序员代码指南》里的
要排序的栈为stack,辅助的栈为help,在stack上执行pop操作,弹出的元素记为cur
1.如果cur小于或者等于help的栈顶元素,则将cur直接压入help(目的是要小的放在下面)
2.如果cur大于help的栈顶元素,则将help的元素逐一弹出,逐一压入stack,直到1
就是为了将小的数都放在help的底下
*/
public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        Stack<Integer> stack=new Stack<Integer>();
        Stack<Integer> help=new Stack<Integer>();
        ArrayList<Integer>  list=new ArrayList<Integer>();
        for(int  i=0;i<numbers.length;i++)
            stack.push(numbers[i]);
        while(!stack.isEmpty()){
            int cur =stack.pop();
            while(!help.isEmpty()&& help.peek()>cur ){ //比cur大 出栈
                stack.push(help.pop());               
            }
            help.push(cur); 
        }
        while(!help.isEmpty()){
            list.add(stack.push(help.pop()));
        }
        return list;
    }
}

发表于 2017-07-27 23:13:54 回复(1)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        stack<int> a;
        stack<int> b;
        int siz = numbers.size();
        for(int i = 0; i < siz; i++){
            a.push(numbers[i]);
        }
        for(int i = 0; i < siz; i++){
            int min = a.top();
            int count = 0;
            for(int j = i; j < siz; j++){
                if(a.top() < min){
                    min = a.top();
                }
                b.push(a.top());
                a.pop();
            }
            a.push(min);
            for(int j = i; j < siz; j++){
                if(count == 0 && b.top() == min){
                    b.pop();
                    count++;
                    continue;
                }
                a.push(b.top());
                b.pop();
            }
        }
        for(int i = 0; i < siz; i++){
            numbers[i] = a.top();
            a.pop();
        }
        return numbers;
    }
};

发表于 2016-05-09 17:11:31 回复(1)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        vector<int> help;
        while (!numbers.empty()) {
            int cur = numbers.back();
            numbers.pop_back();      
            while (!help.empty() && cur < help.back()) {
		        numbers.push_back(help.back());
                help.pop_back();
            }
            help.push_back(cur);
        }
        numbers.clear();
        while (!help.empty()) {
            numbers.push_back(help.back());
            help.pop_back();
        }
        return numbers;
    }
};  
好想知道为什么不用stack<int>而要用vector<int>?
vector<int>的第一个元素是栈顶的话,操作起来好麻烦啊。
这里我投机取巧了,把vector的最后的一个元素当做栈顶,每次移动栈顶的操作就是
pop_back(),每次获取栈顶元素就直接用back()。
思路很简单啊,就两点:
1. 如果栈顶元素cur<=辅助栈help栈顶元素,那么就直接push入辅助栈。
2. 否则,就将辅助栈的栈顶元素push到原栈,直至cur>辅助栈的栈顶元素,此时再将cur
push入辅助栈。保证辅助栈的数据是从栈顶到栈底升序,最后将辅助栈的数据逆序push到原栈
就可以使得原栈是降序啦~

编辑于 2017-02-25 10:46:29 回复(2)
public ArrayList<Integer> twoStacksSort(int[] numbers) {
	if(numbers==null || numbers.length<1)
		return null;
	Stack<Integer> myStack1 = new Stack<Integer>();
	Stack<Integer> myStack2 = new Stack<Integer>();
        ArrayList<Integer> myResult = new ArrayList<Integer>();        
        for(int i=0;i<numbers.length;i++){           
            myStack1.push(numbers[i]);
        }
        while(!myStack1.empty()){
        	int myTemp=myStack1.pop();
        	while(!myStack2.empty() && myStack2.peek()>myTemp){
        		myStack1.push(myStack2.pop());
        	}
        	myStack2.push(myTemp);
        }
        while(!myStack2.empty()){
        	myResult.add(myStack2.pop());
        }
        return myResult;
    }

发表于 2015-12-24 21:49:27 回复(9)
//看到题目蛋碎一地,说好的是栈,你给我一个数组是什么意思,人与人之间最基本的信任呢
//还只让我用一个额外栈,结果输出是个ArrayList,如果照题目意思把ArrayList也当成一个栈。。。那还要啥自行车
//我的内心是崩溃的,然后就有了这样的写法
//思路,取出栈1中元素放在栈2中,然后栈1再弹出一个元素,比较这个元素与栈2顶元素大小,如果大于等于栈二顶元素,就把它压入栈2中,如果小于,就把栈2中元素弹出一个压入栈1中,重复比较,直到元素大于栈2顶元素或栈2为空,就把它压入栈2中,实现排序。
//方法一:
 public ArrayList<Integer> twoStacksSort(int[] numbers) {
        ArrayList<Integer> result=new ArrayList<Integer>();
        if(numbers==null) return result;
        int count=0,temp=0,index=0;
        while(index<numbers.length){
            temp=count==0?numbers[index++]:temp;
            if(result.size()==0||temp>=result.get(0)){
                 result.add(0,temp);
                // while(count-->0) result.add(0,numbers[index++]);//这句话可以不要
                 count=0;
            } 
            else {
                 numbers[--index]=result.remove(0);
                 count++;
            }
        }
        return result;
    }
//方法二,原理同方法一,不让我用栈我偏用,我是菜鸟我怕谁QAQ
 public ArrayList<Integer> twoStacksSort(int[] numbers) {
        ArrayList<Integer> result=new ArrayList<Integer>();
        if(numbers==null) return result;
        Stack<Integer> stack= new Stack<Integer>();
        Stack<Integer> resultStack= new Stack<Integer>();
        for(int i=0;i<numbers.length;i++) stack.push(numbers[numbers.length-i-1]);
        int count=0,temp=0;
        while(!stack.isEmpty()){
            temp=count==0?stack.pop():temp;
            if(resultStack.isEmpty()||temp>=resultStack.peek()){
                 resultStack.push(temp);
                // while(count-->0) resultStack.push(stack.pop());//这句话可以不要,不过不知道为什么加上这句话,运行占用内存是1000多K,不加是3000多K
                 count=0;
            } 
            else {
                 stack.push(resultStack.pop());
                 count++;
            }
        }
        while(!resultStack.isEmpty()) result.add(resultStack.pop());
        return result;
    }


编辑于 2017-05-12 20:24:46 回复(0)
//解题思路:一个原栈,一个辅助栈,我们可以将原栈中的元素依次出栈和辅助栈中的栈顶元素进行比较,如果原大于辅,将原出栈到辅助中,
//如果辅助大于原,将辅助出栈到原中,知道将原栈中的元素全部出栈,排序完成。
 //code 20160816
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        //边界条件判断
        if(numbers.empty())
          return numbers;
       vector<int> SortNumber;
       while(!numbers.empty())
       {
           int temp=numbers.front();//栈顶
               numbers.erase(numbers.begin());
           if(SortNumber.empty())
               SortNumber.insert(SortNumber.begin(),temp);//在最前面插入新元素
           else//辅助栈不是空
           {
               bool flag=true;
               while(!SortNumber.empty())
               {
                   int tempSort=SortNumber.front();//栈顶
                   if(tempSort>temp)//辅助栈数字更大
                   {
                        numbers.insert(numbers.begin(),tempSort);//在最前面插入新元素
                        SortNumber.erase(SortNumber.begin());
                   }                       
                   else//满足递减规律
                   {
                        SortNumber.insert(SortNumber.begin(),temp);//在最前面插入新元素
                         flag=false;
                         break;
                   }
               }
               if(flag)//全部弹出辅助栈
               {
                   SortNumber.insert(SortNumber.begin(),temp);//在最前面插入新元素
               }
           }
       }
      return SortNumber;  
    }
};

发表于 2016-08-16 15:46:44 回复(0)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        vector<int> temp;
        temp.push_back(numbers.back());
        numbers.pop_back();
        while(!numbers.empty()){
            int n=numbers.back();
            numbers.pop_back();
            while(!temp.empty()&&n>temp.back()){//下沉操作,弹出到temp中不小于n的位置
                numbers.push_back(temp.back());//temp弹出的数放到numbers中
                temp.pop_back();
            }
            temp.push_back(n);
		} 
        return temp;
    }
};

发表于 2016-06-01 11:17:36 回复(3)

python one line solution:


        return sorted(numbers,reverse=True)
发表于 2017-10-01 20:28:53 回复(1)
public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> stack=new ArrayList<Integer>();
        int temp,i;
        for(i=0;i<numbers.length;i++){
            temp=numbers[i];
            while(!stack.isEmpty()&&stack.get(stack.size()-1)<temp){
                numbers[i--]=stack.get(stack.size()-1);
                stack.remove(stack.size()-1);
            }
            stack.add(temp);
        }
        return stack;
    }

发表于 2016-03-15 13:51:09 回复(2)
设置一个临时栈存放已经排序好的序列。如果临时栈为空,则从初始栈pop一个压入临时栈,如果不为空,则初始栈pop出一个元素与临时栈最后一个元素(栈底)比较
class TwoStacks:
    def twoStacksSort(self, numbers):
        #return sorted(numbers,reverse=True)
        if not numbers&nbs***bsp;len(numbers)==1:
            return numbers
        res = []
        while numbers:
            if not res:
                res.append(numbers.pop())
            else:
                pre = numbers.pop()
                if pre<=res[-1]:
                    res.append(pre)
                else:
                    while res and res[-1]<pre:
                        numbers.append(res.pop())
                    res.append(pre)
        return res

发表于 2020-06-16 10:22:39 回复(0)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        vector<int> temp_stack;
        int temp;
        while(!numbers.empty()){
            temp = numbers.back();
            numbers.pop_back();
            while(!temp_stack.empty() && temp_stack.back() < temp) {
                numbers.push_back(temp_stack.back());
                temp_stack.pop_back();
            }
            temp_stack.push_back(temp);
        }
        return temp_stack;
    }
};

编辑于 2019-10-30 17:54:14 回复(0)

class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        vector<int> res;
        while (!numbers.empty()) {
            int num = numbers.back();
            numbers.pop_back();
            while (!res.empty() && res.back() < num) {
                numbers.push_back(res.back());
                res.pop_back();
            }
            res.push_back(num);
        }
        return res;
    }
};

运行时间:6ms

占用内存:504k


发表于 2018-12-24 17:03:09 回复(1)
纯用 vector
classTwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        vector<int> buf;
        while(!numbers.empty())
        {
            int top = numbers[0];
            numbers.erase(numbers.begin());
            while(!buf.empty()&&(top<buf[0]))
            {
                numbers.insert(numbers.begin(),buf[0]);
                buf.erase(buf.begin());
            }
            buf.insert(buf.begin(),top);
        }
        return buf;
    }
};
时间复杂度O(N^2),空间复杂度O(N)
发表于 2018-03-29 12:13:58 回复(0)
//构建一个辅助栈存放排好序的 和 一个变量存放临时值
public ArrayList<Integer> twoStacksSort(int[] numbers) {
    ArrayList<Integer> res = new ArrayList<>();
    if (numbers == null || numbers.length == 0) return res;
    Stack<Integer> stack1 = new Stack<>();//原始栈
    for (int i = numbers.length - 1; i >= 0; i--)
        stack1.push(numbers[i]);
    int temp;//存放临时值
    Stack<Integer> stack2 = new Stack<>();
    while (stack1.size() != 0) {
        temp = stack1.pop();
        while (stack2.size() != 0 && stack2.peek() > temp) {//辅助栈不为空,且栈头元素比临时值大
            stack1.push(stack2.pop());
        }
        stack2.push(temp);
    }

    while (stack2.size() != 0) {
        res.add(stack2.pop());
    }
    return res;
}
发表于 2018-03-14 10:07:38 回复(0)
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> num) {
        vector<int> res;
        stack<int> tempsta;
        while(num.size()){
            while(!res.size() || (num.size() && num[0]>res[0])){
                res.insert(res.begin(),num[0]);
                num.erase(num.begin());
            }
            if(num.size()){
                while(res.size() && num[0]<res[0]){
                    tempsta.push(res[0]);
                    res.erase(res.begin());
                }
                res.insert(res.begin(),num[0]);
                num.erase(num.begin());
                while(!tempsta.empty()){ res.insert(res.begin(),tempsta.top()); tempsta.pop(); }
            }
        }
        return res;
    }
};
发表于 2017-08-23 21:36:55 回复(0)