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

Question

我想知道为什么我们总是使用排序算法(如插入排序或合并排序,...)仅用于列表和数组？为什么我们不将这些算法用于堆栈或队列？

Answer 1

堆栈和队列是具有自己的顺序感的抽象数据类型,即堆栈的LIFO(后进先出)和队列的FIFO(先进先出).因此,采取队列/堆栈并重新排序其元素是没有意义的.

维基百科参考

• 堆栈(数据结构)
• 队列(数据结构)

在堆栈对传染媒介

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

相关问题

• Java Stack类继承Vector Class

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

尽管它没有意义的使用,比如说,快速排序在堆栈上,你CAN实际使用Collections.sort上java.util.Stack.为什么？因为,由于设计错误(这不能强调得足够!),a java.util.Stack是一个java.util.Vector,哪个implements 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可能是适当的数据结构.它是a 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"

Answer 2

这是因为堆栈或队列的顺序是这些数据结构定义的一部分.如果我们对它们进行排序,它们就不会是堆栈或队列.