关于排序算法应用于堆栈和队列 [英] About Sorting Algorithms applied to Stacks and Queues
问题描述
堆栈和队列是具有自己意义的抽象数据类型对于队列，堆栈和FIFO（先进先出）的顺序，即LIFO（先进先出）。因此，采取队列/堆栈并重新排列元素是没有意义的。
维基百科参考文献
堆栈与矢量
您可能会注意到在Java中， java.util .stack extends java.util.Vector ，因为排序矢量，或许排序一个 Stack 也是有意义的。但情况并非如此;事实上， Stack扩展Vector 实际上是一种设计错误。
相关问题
在<$ c $上使用 Collections.sort c> java.util.Stack
尽管在栈上使用快速排序没有意义， 可以实际使用 Collections.sort 在 java.util.Stack 上。为什么？因为， 由于设计错误 （这不足够强调！），一个 java.util.Stack 是一个 java.util.Vector ，其中实现java.util.List ，您当然可以排序列表。这里有一个例子：
堆栈<整数> stack = new Stack< Integer>（）;
stack.push（1）;
stack.push（3）;
stack.push（5）;
stack.push（2）;
stack.push（4）;
Collections.sort（stack）; //凭借设计错误!!!
System.out.println（stack）; //打印[1，2，3，4，5]
while（！stack.isEmpty（））{
System.out.println（stack.pop（））;
} //打印5，4，3，2，1
请注意，元素按降序打印：这是因为实现了 java.util.Stack 。它从 Vector 的末尾推入并弹出。你不需要知道这一点;你不应该知道这个;但是这些是事实。
使用适当的数据结构
根据您要完成的内容， TreeSet 可能是适当的数据结构。它是一个 设置 ，所以它不允许重复的元素。
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（））; //打印1
System.out.println（nums.pollFirst（））; //打印2
nums.add（4）;
System.out.println（nums.pollFirst（））; //打印3
System.out.println（nums.pollFirst（））; //打印4
I want to know why we always use Sorting algorithm like (Insertion Sort or Merge Sort,...) just for lists and arrays? And why we do not use these algorithms for stack or queue?
Stacks and queues are abstract data types that have their own sense of order, i.e. LIFO (Last In First Out) for stacks and FIFO (First In First Out) for queues. As such, it does not make sense to take a queue/stack and reorder their elements around.
Wikipedia references
On Stack vs Vector
You may notice that in Java, java.util.Stackextendsjava.util.Vector, and since it makes sense to sort a Vector, perhaps it also makes sense to sort a Stack. This is not the case however; the fact that Stack extends Vector is in fact a design blunder. A stack is NOT a vector.
Related questions
On using Collections.sort on java.util.Stack
Despite the fact that it doesn't make sense to use, say, quicksort on a stack, you CAN actually use Collections.sort on a java.util.Stack. Why? Because, by virtue of design error (this can't be emphasized enough!), a java.util.Stack is a java.util.Vector, which implements java.util.List, and you certainly can sort a List. Here's an example:
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"
Note that the elements are printed in descending order: this is because of how java.util.Stack is implemented. It pushes to and pops from the end of the Vector. You don't need to know this; you shouldn't have known this; but these are the facts.
On using an appropriate data structure
Depending on what it is that you're trying to accomplish, a TreeSet may be the appropriate data structure. It is a Set, so it does not permit duplicate elements.
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"
这篇关于关于排序算法应用于堆栈和队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
