首页 > 试题广场 >

双栈排序

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

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

测试样例： 
[1,2,3,4,5]
返回：[5,4,3,2,1]
算法知识视频讲解
添加回答
Java
Simms头像 Simms 
public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> result = new ArrayList<>();

        if(numbers.length == 0){
            return result;
        }


        Stack<Integer> tmp = new Stack<>();
        Stack<Integer> help = new Stack<>();

        for (int i = 0; i< numbers .length; i++){
            tmp.push(numbers[i]);
        }


        while(tmp.size() != 0){

            int num = tmp.pop();

            if (help.size() == 0 || help.peek() <= num){
                help.push(num);
            }else {
                tmp.push(help.pop());
                tmp.push(num);//复原
            }
        }

        while(help.size() != 0){
            result.add(help.pop());
        }
        return result;
    }

发表于 2020-07-06 18:51:48 回复(0)
Java
陌渝头像 陌渝
import java.util.*;
/*将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。
（1）如果cur大于或者等于help的栈顶元素，则将cur直接压入help；
（2）如果cur小于help的栈顶元素，则将该help的元素逐一弹出并压入stack栈，
    直到cur小于或等于help的栈顶元素，再将cur压入help。*/
public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        Stack <Integer> stack = new Stack<>();
        Stack <Integer> help = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++){
            stack.push(numbers[i]);
        }
        while(!stack.isEmpty())
        {
            int cur = stack.pop();
            while(!help.isEmpty() && cur < help.peek()){
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while(!help.isEmpty()){
            res.add(help.pop());
        }
        return res;
    }
}
发表于 2018-08-20 15:38:06 回复(0)
Java
zidianlyu头像 zidianlyu

时间
O(N^2)

import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (numbers.length == 0) return res;

        stackA意在存数
        Stack<Integer> stackA = new Stack<Integer>();
        for(int n: numbers) stackA.push(n);

        stackB意在存升序
        Stack<Integer> stackB = new Stack<Integer>();
        stackB.push(stackA.pop());

        while(!stackA.isEmpty()) {
            int a = stackA.pop();

            如果stackB里面有比当前小的数，就扔回去stackA
            while(!stackB.isEmpty() && a < stackB.peek()){
                stackA.push(stackB.pop());
            }
            stackB.push(a);
        }

        while(!stackB.isEmpty()){
            res.add(stackB.pop());
        }
        return res;
    }
}
发表于 2018-07-01 08:42:12 回复(0)
Java
小猪佩7头像 小猪佩7 
//构建一个辅助栈存放排好序的 和 一个变量存放临时值
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)
Java
追逐繁星的孩子头像 追逐繁星的孩子
思路：
申请一个栈名为help，从原来的栈中弹出栈顶元素，记为cur，
若栈help为空，则cur直接存入help
否则比较cur和栈help的栈顶元素的大小：
1）cur小，则直接入栈
2）否则将help的栈顶弹出，直到栈顶比cur小
最后将栈转为数组返回
import java.util.*;

public class TwoStacks {
     public ArrayList<Integer> twoStacksSort(int[] numbers) {
        Stack<Integer> help=new Stack<>();
        int top=0; 
        while(top<numbers.length){
            int cur=numbers[top];
            top++;
            if(help.empty()||cur<=help.peek()){
                help.push(cur);
                continue;
            }
            while(!help.empty()&&cur>help.peek()){
                top--;
                numbers[top]=help.pop();
            }
            help.push(cur);
        }
        return new ArrayList<>(help);
    } 
}

发表于 2017-08-25 16:19:59 回复(0)
Java
面什么过什么头像 面什么过什么 
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        int n = numbers.length - 1;
        while (n >= 0) {
            stack.push(numbers[n]);
            n--;
        }
        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            while (result.size() != 0 && result.get(result.size() - 1) < tmp) {
                stack.push(result.remove(result.size() - 1));
            }
            result.add(tmp);
        }
        return result;
    }
}

发表于 2017-06-26 17:11:13 回复(0)
Java
姑娘要去哪里？头像 姑娘要去哪里？ 
1.设置两个栈，一个保存结果，一个用来临时存放数据进行比较
2.当结果栈空或栈的第一个数据小于要插入的数据时直接插入
3.当结果栈不是空的时候，取出栈顶放入临时栈
4.循环2,3步骤直到数据插入
5.把临时栈的数据按序插入回结果栈



public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for(int i=0;i<numbers.length;i++){
            if(result.isEmpty())
                result.add(numbers[i]);
            else{
                while(!result.isEmpty()&&result.get(0)>numbers[i]){
                    temp.add(0,result.remove(0));
                }
                result.add(0,numbers[i]);
                while(!temp.isEmpty()){
                    result.add(0,temp.remove(0));
                }
            }
        }
        return result;
    }
}

发表于 2017-06-02 17:14:59 回复(0)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//看到题目蛋碎一地，说好的是栈，你给我一个数组是什么意思，人与人之间最基本的信任呢
//还只让我用一个额外栈，结果输出是个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)
Java
❤pep_G头像 ❤pep_G 
public class TwoStacks {
	public ArrayList<Integer> twoStacksSort(int[] numbers) {
	    //首先判断传过来的数组是否为空，
		if(numbers==null||numbers.length==0){
			return null;
		}
		//创建需要的量
		/*(1)
		 * 用于返回的链表
		 * (2)两个栈
		 * (3)用于储存buffer部分栈顶的临时变量bufTop
		 * */
		ArrayList<Integer> res=new ArrayList<Integer>();
		Stack<Integer> buffer=new Stack<Integer>();
		Stack<Integer> asc=new Stack<Integer>();
		int bufTop=0;
		//buffer栈装入numbers的数字(这里留了一个未装)
		for(int i=0;i<numbers.length-1;i++){
			buffer.push(numbers[i]);
		}
		//留下的那一个装给asc
		asc.push(numbers[numbers.length-1]);
		/*如果buffer栈顶元素a>=asc栈顶元素，则直接把buffer的栈顶元素装入asc
		否则，把buffer的栈顶元素a出栈，并装入临时变量bufTop,然后把asc的栈顶进行出栈并装入buffer，
		直到bufTop<asc的栈顶元素，才把bufTop装入asc并把之前从asc已经出栈的元素全部压入asc，
		不断循环，直到buffer为空
		*/
		//设置一个变量，用于标记buffer的初始长度
		int bufSize=0;
		while(buffer.size()>0){
			//如果buffer栈顶大于等于asc栈顶，则直接把buffer的栈顶元素出栈，并压入到asc中
			if(buffer.peek()>=asc.peek()){
				asc.push(buffer.pop());
			}else{
				bufTop=buffer.pop();
				//记录初始长度
				bufSize=buffer.size();
				while(!asc.isEmpty()&&bufTop<asc.peek()){
					buffer.push(asc.pop());
				}
				//一旦bufTop小于了asc的栈顶，就立即装入bufTop
				asc.push(bufTop);
				//此时计算buffer中压入了多少asc的元素
				int countFromAsce=buffer.size()-bufSize;
				//把从asc中得到的元素全部返还asc 
				for(int j=1;j<=countFromAsce;j++){
					asc.push(buffer.pop());
				}
			}
		}
		//返还排好序的链表
		while(asc.size()>0){
			System.out.println(asc.peek());
			res.add(asc.pop());
			
		}
		return res;
	}

发表于 2017-04-13 21:22:33 回复(0)
Java
Holiday_12138头像 Holiday_12138 
//一个结果栈，一个辅助栈，保持结果栈的数据都要大于辅助栈的数据，并且结果栈升序，辅助栈降序
//Arraylist 竟然是0作为栈顶，有点晕
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        ArrayList<Integer> tmp=new ArrayList<Integer>();
        for(int i=0;i<numbers.length;i++){
            while(res.size()>0&&numbers[i]<res.get(0))
                tmp.add(0,res.remove(0));
            while(tmp.size()>0&&numbers[i]>tmp.get(0))
                res.add(0,tmp.remove(0));
            res.add(0,numbers[i]);
        }
        while(tmp.size()>0)
            res.add(0,tmp.remove(0));
        return res;
    }
}

发表于 2017-04-12 11:59:39 回复(0)
Java
强大的马来熊在改简历头像 强大的马来熊在改简历
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        if(numbers.length == 0 || numbers == null) return null;
        Stack<Integer> unsorted = createStack(numbers);
        Stack<Integer> res = sortStack(unsorted);
        ArrayList<Integer> result = new ArrayList<Integer>();
        while(!res.isEmpty()){
            result.add(res.pop());
        }
        return result;
    }
    private Stack<Integer> createStack(int[] numbers){
        Stack<Integer> unsorted = new Stack<Integer>();
        for(int i =0; i < numbers.length; ++i){
            unsorted.push(numbers[i]);
        }
        return unsorted;
    }
    private Stack<Integer> sortStack(Stack<Integer> s){
        Stack<Integer> r = new Stack<Integer>();
        while (!s.isEmpty()){
            int tmp = s.pop();
            while(!r.isEmpty() && r.peek() > tmp){
                s.push(r.pop());
            }
            r.push(tmp);
        }
        return r;
    } 
}

发表于 2017-04-01 23:36:49 回复(0)
Java
未缘头像 未缘
import java.util.*;

public class TwoStacks {
    
    // 利用两个栈来实现排序 将 s1的栈顶元素弹出 到 变量temp 与 s2的栈顶比较，如果大 直接压入，
  //否则将 s2中 比 temp 大的元素 先压至 s1中，再将 temp 压入 s2 ，如此往复 直到 s1为空 
    Stack<Integer> s1=new Stack<Integer>();
    Stack<Integer> s2=new Stack<Integer>();
    
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
 
        ArrayList<Integer> list=new ArrayList<Integer>();
        int temp;
     
     for(int i=0 ;i<numbers.length ;i++)
         s1.push(numbers[i]);
    
     while(s1.size()!=0){
         
         temp=s1.pop();
         
         if(s2.size()==0){
             
             s2.push(temp);
         }else{
          
             while( s2.size()!=0 && temp < s2.lastElement() ){
                 s1.push(s2.pop());    
             }  
             s2.push(temp);      
         }
     }
  // 最后要求的返回结果为 List 类型   
   while(s2.size()!=0){ 
       list.add(s2.pop());
   }
  
     return list;
       
    }
}
发表于 2017-03-26 23:24:13 回复(0)
Java
Sunny_ivy头像 Sunny_ivy 
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        if(numbers==null || numbers.length<=0){
            return null;
        }
        ArrayList<Integer> resultStack = new ArrayList<Integer>(numbers.length);
        //构建额外的栈
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=numbers.length-1;i>=0;i--){
            stack.push(numbers[i]);
        }
        //排序添加至数组链表，因链表头表示栈顶，所以应调用add(0,num)方法
        while(!stack.empty()){
            if(resultStack.size()==0){
                resultStack.add(0,stack.pop());
            }else{
                int a = stack.pop();
                int b = resultStack.remove(0);
                if(a<b){
                    stack.push(b);
                    while(resultStack.size()>0 && a<(b = resultStack.remove(0))){
                        stack.push(b);
                    }
                }
                if(a>=b){
                    resultStack.add(0,b);
                }
                resultStack.add(0,a);
            }
        }
        
        //返回的数组链表的第一个元素为栈顶
        return resultStack;
    }
}

发表于 2017-03-14 13:55:13 回复(0)
Java
一神头像 一神 
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = numbers.length - 1; i >= 0; i --) {
            stack.push(numbers[i]);
        }
        
        ArrayDeque<Integer> sortStack = new ArrayDeque<Integer>();
        
        while (!stack.isEmpty()) {
            int num = stack.pop();
            if (sortStack.isEmpty()) {
                sortStack.push(num);
                continue;
            }
            
            while (!sortStack.isEmpty() && sortStack.peek() > num) {
                stack.push(sortStack.pop());
            }
            
            sortStack.push(num);
        }
        
        ArrayList<Integer> res = new ArrayList<Integer>();
        while (!sortStack.isEmpty()) {
            res.add(sortStack.pop());
        }
        
        return res;
    }
}

发表于 2017-01-31 16:14:37 回复(0)
Java
qnz_l头像 qnz_l
import java.util.*;

public class TwoStacks {
    public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> stack=new ArrayList<Integer>();
        int index1=numbers.length-1;
        int index2=-1;
        while(index1>=0){
            int val=numbers[index1--];
            while(!stack.isEmpty()&&stack.get(index2)<val){
            numbers[++index1]=stack.remove(index2);
                index2--;
            }
            stack.add(val);
            index2++;
        }
        return stack;
    }
}
发表于 2016-06-23 15:37:53 回复(0)
提交观点

问题信息

栈
难度：
15条回答 31607浏览

热门推荐

通过挑战的用户

查看代码

相关试题

双栈排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号