About Sorting Algorithms applied to Stacks and Queues

Question

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?

Answer 1

That's because the order of a stack or a queue is part of the definition of these data structures. If we sorted them, they wouldn't be stacks or queues.

Answer 2

A Stack or Queue are concepts which differ from Sequences. Arrays and Linked Lists represent Sequences, on which you can think of them as sorted or unsorted.

Answer 3

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

• Stack (data structure)
• Queue (data structure)

---

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

• Java Stack class inherit Vector Class

---

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"

Answer 4

As others noted, in general it doesn't make sense to order stacks and queues. Just to make the picture full, there is an exception: PriorityQueue, which keeps its elements ordered.

Answer 5

Stack and Queue have their own unique structure. Stack is a structure that applies Last In First Out(LIFO). If you ordered a Stack, then it would violate LIFO. Think that I add 7, 3, 5, 4 to a stack. As you know, stack can only retrieve the last added element. Whenever, we call pop() method, it will retrieve 4. However, think that you now sort it. It becomes 3, 4, 5, 7 and when we pop(), it will retrieve 7 which was the first element that we added. This violates LIFO rule.

The same is valid for Queue, because Queue structure applies First in First Out. If you have any question, please don't hesitate to ask.

Answer 6

First of all Stack and Queues are also list but having some special characteristics. Since they are list you can always sort them but if you do that you might alter properties of these data structures.

Then there will be no point to using these data structure throughout your code and at some point sort them to loose their property for which we were using them.