寒光博客

[java]Stack 用临栈对栈排序
TwoStackSort cc150 请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一...
扫描右侧二维码阅读全文
26
2019/10

[java]Stack 用临栈对栈排序

TwoStackSort

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

[1,2,3,4,5]

返回:

[5,4,3,2,1]

代码

package _09_Linear.Stack_QueuePractice;

import java.util.ArrayList;
import java.util.Stack;

public class TwoStackSort {
    public static void main(String[] args) {
        int[] arr = {80, 2, 3, 14, 5, 19, 4, 70};
        ArrayList<Integer> res = new TwoStackSort().twoStackSort(arr);
        for (int a : res) {
            System.out.println(a);
        }
    }

    public ArrayList<Integer> twoStackSort(int[] number) {
        // 初始化原始栈
        Stack<Integer> source = new Stack<>();

        for (int i = 0; i < number.length; i++) {
            source.push(number[i]);
        }
        Stack<Integer> target = twoStackSort(source);

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

        while (!target.empty()) {
            list.add(target.pop());//从栈顶取出 从大大小 --> list
        }
        return list;

    }

    public Stack<Integer> twoStackSort(Stack<Integer> source) {
        Stack<Integer> target = new Stack<>();
        while (!source.empty()) {
            int v1 = source.pop();//揭开 盖子
            if (target.empty()) {
                target.push(v1);
            } else {//比较
                if (v1 >= target.peek())//比盖子大 就 压进去 大的在栈顶
                    target.push(v1);
                else {
                    while (!target.empty() && v1 < target.peek()) {//逆序 装回去
                        source.push(target.pop());
                    }
                    target.push(v1);
                }
            }
        }
        return target;
    }
}
本文作者:Author:     文章标题:[java]Stack 用临栈对栈排序
本文地址:https://dxoca.cn/java/308.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 26th, 2019 at 09:36 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment