Write a program in java that sorts a stack of integers in descending order with

Question

Write a program in java that sorts a stack of integers in descending order with the smallest item on top. You are allowed to use one stack to hold your data and another stack as an auxiliary data structure. You may not use any other data structures such as array etc. to help you solve the problem. Hint You have push(), pop(), top() and isEmpty() methods to help you solve the problem. Input This program does not need to input any data from the console, instead you create a random number between 0 to 20 and then this number shows you the number of randoms that you should generate as your inputs. Inputs should be between 0 to 50. For example, if the first random number generated is 10, you need to generated 10 more random numbers and push them into the stack for sorting purpose. Output You first print the content of the stack and then print the sorted item. e.g. Random Number = 13 Initial Stack: [4, 7, 18, 39, 42, 8, 35, 23, 50, 0, 23, 11, 6] Sorted Stack: [0, 4, 6, 7, 8, 11, 18, 23, 23, 35, 39, 42, 50]

Explanation / Answer

Please find the required solution:

import java.util.Random;
import java.util.Stack;

public class StackImpl {

   public static void main(String[] args) {
       // declaration of input stack
       Stack<Integer> inputStack = new Stack<Integer>();
       Random rdm = new Random();

       // generate random size for stack(0-20)
       int input = rdm.nextInt(20);

       // push elements to stack
       for (int i = 0; i < input; i++) {
           inputStack.push(rdm.nextInt(50));
       }
       // finally print the input and result
       System.out.println("Input Stack:" + inputStack);
       System.out.println("Sorted Stack:" + sort(inputStack));
   }

   /* Used to sort stack */
   public static Stack<Integer> sort(Stack<Integer> inputStack) {
       // temporary stack
       Stack<Integer> sortedStack = new Stack<Integer>();

       // iterate till input stack is not empty
       while (!inputStack.isEmpty()) {
           // get the top element of input stack
           int tmp = inputStack.pop();
           /**
           * 1. if the sorted stack is empty add the top element of input
           * stack to sorted stack <br>
           * 2.while the element on top of sorted stack is greater than the
           * tmp push to input stack
           */
           while (!sortedStack.isEmpty() && sortedStack.peek() > tmp) {
               inputStack.push(sortedStack.pop());
           }
           sortedStack.push(tmp);
       }
       return sortedStack;
   }
}

Sample Output:

Input Stack:[21, 3, 47, 4, 45, 13, 33, 31, 15, 44, 28, 48, 6, 49, 11, 34, 25, 13, 44]
Sorted Stack:[3, 4, 6, 11, 13, 13, 15, 21, 25, 28, 31, 33, 34, 44, 44, 45, 47, 48, 49]

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.