java – 关于应用于堆栈和队列的排序算法

维基百科参考

> Stack (data structure)
> Queue (data structure)

在堆栈对传染媒介

您可能会注意到在Java中,java.util.Stackextendsjava.util.Vector,并且由于对Vector进行排序是有意义的,因此对堆栈进行排序也许是有意义的.但情况并非如此; Stack扩展Vector的事实实际上是一个设计错误.堆栈不是矢量.

相关问题

> Java Stack class inherit Vector Class

在java.util.Stack上使用Collections.sort

尽管在堆栈上使用快速排序是没有意义的,但实际上你可以在java.util.Stack上使用Collections.sort.为什么？因为,由于设计错误(这不足以强调！),java.util.Stack是一个java.util.Vector,它实现了java.util.List,你当然可以对List进行排序.这是一个例子：

Stack<Integer> stack = new Stack<Integer>();
    stack.push(1);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(4);

    Collections.sort(stack); // by virtue of design error!!!

    System.out.println(stack); // prints "[1,2,3,4,5]"
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    } // prints "5","4","3","2","1"

请注意,元素按降序打印：这是因为java.util.Stack的实现方式.它从Vector的末尾推送并弹出.你不需要知道这个;你不应该知道这一点;但这些都是事实.

使用适当的数据结构

根据您尝试完成的内容,TreeSet可能是适当的数据结构.它是Set,所以它不允许重复元素.

NavigableSet<Integer> nums = new TreeSet<Integer>();
    nums.add(5);
    nums.add(3);
    nums.add(1);
    nums.add(2);
    nums.add(6);

    System.out.println(nums.pollFirst()); // prints "1"
    System.out.println(nums.pollFirst()); // prints "2"
    nums.add(4);
    System.out.println(nums.pollFirst()); // prints "3"
    System.out.println(nums.pollFirst()); // prints "4"