用一个栈实现另一个栈的排序

[编程题]用一个栈实现另一个栈的排序

热度指数：6345 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

输入描述:

第一行输入一个N，表示栈中元素的个数
第二行输入N个整数表示栈顶到栈底的各个元素

输出描述:

输出一行表示排序后的栈中栈顶到栈底的各个元素。

示例1

输入

5
5 8 4 3 6

输出

8 6 5 4 3

备注:

1 <= N <= 10000
-1000000 <=  <= 1000000

算法知识视频讲解

Java

helloxuanbao

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        br.readLine();
        String[] secondLine = br.readLine().split(" ");
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> help = new LinkedList<>();
        for (String s : secondLine) {
            stack.push(Integer.parseInt(s));
        }
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && cur > help.peek()) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pop());
            if (!stack.isEmpty()) {
                res.append(" ");
            }
        }
        System.out.println(res);
    }
}

发表于 2022-02-18 23:53:08 回复(0)

Java

wanbf

import java.util.*;
public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        Stack<Integer> stackA = new Stack<Integer>();
        Stack<Integer> stackB = new Stack<Integer>();
        while(sc.hasNextInt()){
            stackA.push(sc.nextInt());
        }
        while(!stackA.isEmpty()){
            int temp=stackA.pop();
            while( !stackB.isEmpty() && stackB.peek()>temp){
                stackA.push(stackB.pop());
            }
            stackB.push(temp);
        }
        while(!stackB.isEmpty()){
            System.out.print(stackB.pop()+" ");
        }
    }
}

发表于 2022-01-17 16:42:09 回复(0)

Java

hugh98

用了递归，实现的比题解复杂太多...555不亏是我，fw

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author hugh
 * @create 2021-09-04 23:10
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        String[] line = in.readLine().split(" ");
        Stack<Integer> data = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            data.push(Integer.parseInt(line[i]));
        }
        Stack<Integer> stack = new Stack<>();
        sort(data, stack);
        StringBuilder res = new StringBuilder();
        while (!data.isEmpty()) {
            res.append(data.pop() + " ");
        }
        System.out.println(res.substring(0, res.length() - 1));
    }

    public static void sort(Stack<Integer> data, Stack<Integer> stack) {
        while (!data.isEmpty()) {
            Integer num1 = data.pop();
            put(stack, num1);
        }

        while (!stack.isEmpty()) {
            data.push(stack.pop());
        }
    }

    /**
     * 将x插入data中的合适位置，保证从大到小的顺序
     * @param stack 按照从大到小(栈底->栈顶)排序的栈
     * @param x  整数
     */
    public static void put(Stack<Integer> stack, Integer x) {
        if (stack.isEmpty() || stack.peek() > x) {
            stack.push(x);
        } else {
            Integer num = stack.pop();
            put(stack, x);
            stack.push(num);
        }
    }
}

发表于 2021-09-04 23:45:50 回复(0)

Java

deh

看到自己6300+ms然后看到你们160+ms，开始怀疑人生；

点进去看了下你们竟然偷偷用库函数.....

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> helpInput = new Stack<>();
        int n = Integer.parseInt(in.readLine());
        String[] stackArray = in.readLine().split(" ");
        for (int i = n-1;i >=0;i--){
            helpInput.push(Integer.parseInt(stackArray[i]));
        }
        sortStackByStack(helpInput);
        while (!helpInput.isEmpty()){
            System.out.print(helpInput.pop()+ " ");
        }
        in.close();
    }
}

发表于 2020-04-04 21:28:21 回复(0)

Java

拷斤锟

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void sortStackByTheOtherStack(ArrayDeque<Integer> stack) {
        ArrayDeque<Integer> helperStack = new ArrayDeque<>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!helperStack.isEmpty() && helperStack.peek() < cur) {
                stack.push(helperStack.pop());
            }
            helperStack.push(cur);
        }
        while (!helperStack.isEmpty()) {
            stack.push(helperStack.pop());
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 操作总数
        int N = sc.nextInt();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            stack.push(sc.nextInt());
        }
        sortStackByTheOtherStack(stack);
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

Java用java.util.Stack会超时，用java.util.ArrayDeque能提升一个数量级

发表于 2020-01-28 23:51:57 回复(0)

Java

Mono_Chrome

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            while (!help.isEmpty() && help.peek() > temp) {
                stack.push(help.pop());
            }
            help.push(temp);
        }
        while (!help.isEmpty()) {
            int temp = help.pop();
            stack.push(temp);
            System.out.print(temp + " ");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();
        while (n-- > 0) {
            stack.push(sc.nextInt());
        }
        sortStackByStack(stack);
    }

}

发表于 2019-10-10 18:32:47 回复(0)