Java – about sorting algorithms applied to stacks and queues

I wonder why we always use sorting algorithms (such as insert sorting or merge sorting,...) only for lists and arrays? Why don't we use these algorithms for stacks or queues?

Solution

Stack and queue are abstract data types with their own sense of order, that is, LIFO (last in first out) of stack and FIFO (first in first out) of queue Therefore, it makes no sense to take the queue / stack and reorder its elements

Wikipedia reference

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

On the stack of infectious agents

You may notice that in Java, Java util. Stackextendsjava. util. Vector, and since sorting vectors makes sense, sorting the stack may make sense This is not the case; The fact that stack extends vector is actually a design error Stack is not a vector

Related issues

> Java Stack class inherit Vector Class

In Java util. Using collections. On stack sort

Although it doesn't make sense to use quick sort on the stack, you can actually use it in Java util. Using collections. On stack sort. Why? Because, due to design errors (this is not enough to emphasize!), java. util. Stack is a Java util. Vector, which implements Java util. List, of course you can sort the list Here is 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"

Notice that the elements are printed in descending order: This is because of Java util. Stack implementation It pushes and pops from the end of the vector You don't need to know this; You shouldn't know that; But these are facts

Use appropriate data structures

Depending on what you are trying to accomplish, TreeSet may be the appropriate data structure It is a set, so it does not allow 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"