Guest User

Untitled

a guest
Feb 21st, 2020
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package stacks_queues;
  2.  
  3. import java.util.Stack;
  4.  
  5. public class SortStack {
  6.  
  7.  
  8.     private static Stack<Integer> sort(Stack<Integer> stack) {
  9.         // empty stack is already sorted
  10.         if (stack.empty()) {
  11.             return stack;
  12.         }
  13.  
  14.         // empty stack is  sorted
  15.         Stack<Integer> helperStack = new Stack<>();
  16.  
  17.         // stack with one element is sorted
  18.         helperStack.push(stack.pop());
  19.  
  20.         while (!stack.empty()) {
  21.             // the top element from original stack
  22.             int remembered = stack.peek();
  23.  
  24.             // if the top of the input stack is lesser than top of our helper stack, we can move it to the helper stack
  25.             // and as result the helper stack remains sorted (the higher we are the smaller the element is)
  26.             if (remembered < helperStack.peek()) {
  27.                 helperStack.push(remembered);
  28.             } else {
  29.                 // If the top (remembered) of the input stack is greater than the top of helper stack, we must make an effort to
  30.                 // place the remembered value in the such position in the helper stack that will preserve its order.                
  31.                 // We first move elements lesser than `remembered` to the original stack, then push the remembered value to the helper stack
  32.                 // and finally move all the lesser elements back to the helper stack, therefore preserving the order.
  33.                 while (remembered > helperStack.peek()) {
  34.                     stack.push(helperStack.pop());
  35.                 }
  36.                 helperStack.push(remembered);
  37.  
  38.                 while (stack.peek() != remembered) {
  39.                     helperStack.push(stack.pop());
  40.                 }
  41.             }
  42.             // at this point the `remembered` value is still present at the top of the original stack
  43.             stack.pop();
  44.         }
  45.         return helperStack;
  46.     }
  47.  
  48.     public static void main(String[] args) {
  49.         Stack<Integer> toBeSorted = new Stack<>();
  50.  
  51.         toBeSorted.push(3);
  52.         toBeSorted.push(-2);
  53.         toBeSorted.push(1);
  54.         toBeSorted.push(4);
  55.         toBeSorted.push(0);
  56.         toBeSorted.push(-3);
  57.         toBeSorted.push(-5);
  58.         toBeSorted.push(-2);
  59.         toBeSorted.push(6);
  60.  
  61.         Stack<Integer> sorted = sort(toBeSorted);
  62.  
  63.         System.out.println(sorted);
  64.     }
  65. }
RAW Paste Data