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

举报
牛哄哄的柯南 发表于 2022/06/28 13:40:10 2022/06/28
【摘要】 用一个栈实现另一个栈的排序

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

【题目】

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

【思路】

需要排序的栈:stackData,用一个辅助栈:stackHelp

从stackData开始pop,记录为cur,那cur和stackHelp的栈顶比较,如果stackHelp的栈顶比cur小,就把stackHelp栈的数据一直往stackData压,知道条件不成立(stackHelp.peek()<cur),前提肯定是stackHelp不为空,然后就把cur压入stackHelp中,模拟下就可以看到一个现象,stackHelp的栈底总是比较大,然后往上面变小,最后stackHelp变成了从栈顶到栈底,数据逐渐变大,最后把stackHelp的数据弹出压入stackData,就行了,就实现了stackData栈从顶到底按从大到小。

【代码】

package pers.keafmd.accumulate.codeinterviewguide.stacksorting;

import java.util.Stack;

/**
 * Keafmd
 *
 * @ClassName: StackSort
 * @Description: 用一个栈排序另外一个栈
 * @author: 牛哄哄的柯南
 * @date: 2022-06-24 16:06
 */
public class StackSort {

    public void sort(Stack<Integer> stackData){
        Stack<Integer> stackHelp = new Stack<>();
        while(!stackData.isEmpty()){
            int cur = stackData.pop();
            while(!stackHelp.isEmpty()&&stackHelp.peek()<cur){
                stackData.push(stackHelp.pop());
            }
            stackHelp.push(cur);
        }

        while(!stackHelp.isEmpty()){
            stackData.push(stackHelp.pop());
        }

    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(6);
        stack.push(5);
        stack.push(7);
        stack.push(3);
        stack.push(1);
        stack.push(2);
        stack.push(4);

        System.out.print("排序前(栈顶到栈底):");
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
        System.out.println();

        stack.push(3);
        stack.push(6);
        stack.push(5);
        stack.push(7);
        stack.push(3);
        stack.push(1);
        stack.push(2);
        stack.push(4);

        StackSort stackSort = new StackSort();
        stackSort.sort(stack);
        System.out.print("排序后(栈顶到栈底):");
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
        System.out.println();

    }

}

效果:

排序前(栈顶到栈底):4 2 1 3 7 5 6 3 
排序后(栈顶到栈底):7 6 5 4 3 3 2 1 

Process finished with exit code 0
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。