CC-18 : Implement Stack sort.

Description:

: Given a stack with integer elements, sort the integers in descending order and return the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
Stack nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28 <-	Stack nodes: 34 <- 28 <- 21 <- 17 <- 14 <- 9 <-
Stack nodes: 9 <- 14 <- 17 <- 3 <- 21 <- 5 <- 1 <-	Stack nodes: 21 <- 17 <- 14 <- 9 <- 5 <- 3 <- 1 <-

Pseudocode:

Initialize a Deque stack named sortedStack for storing the sorted elements.

For all elements in input stack:

While sorted stack size is not zero:

If top element of sortedStack is greater than current element of input stack:

Add top element of sortedStack to input stack.

Else break out of current loop.

Add current element of input stack to sortedStack.

At end of above loop, sortedStack contains the elements in descending sort. Return sortedStack.

Code:

public Deque<Integer> sort(Deque<Integer> stack) throws Exception{
	Deque<Integer> sortedStack=new LinkedList<Integer>();
	int num;	
	while (stack.size() != 0) {
		num=(int) stack.pollFirst();		
		while (sortedStack.size() != 0) {
			if (num < (int) sortedStack.peekFirst()){
				stack.offerFirst(sortedStack.pollFirst());
			}else {
				break;
			}
		}
		sortedStack.offerFirst(num);
	}
	return sortedStack;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class StackSort {

public Deque<Integer> sort(Deque<Integer> stack) throws Exception{
	Deque<Integer> sortedStack=new LinkedList<Integer>();
	int num;	
	while (stack.size() != 0) {
		num=(int) stack.pollFirst();		
		while (sortedStack.size() != 0) {
			if (num < (int) sortedStack.peekFirst()){
				stack.offerFirst(sortedStack.pollFirst());
			}else {
				break;
			}
		}
		sortedStack.offerFirst(num);
	}
	return sortedStack;
}

public static void printQueue(Queue<Integer> queue) throws Exception   {
    if (queue.size() == 0) { System.out.println("Queue empty"); return; }
    System.out.println();
	System.out.println("*********************************************************************");
	System.out.print("Queue nodes: ");
	Iterator itr=queue.iterator();
	while (itr.hasNext())  {
	    System.out.print(itr.next());
	    System.out.print(" <- ");
	} 
	System.out.println();
	System.out.println("*********************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}
 	
public static void main(String[] args) {
	/***********************
 	Test cases given below:
	 **********************/
	try {
	Deque<Integer> queue=new LinkedList<Integer>();
	System.out.print("Add to stack");
	queue.add(9);
	queue.add(14);
	queue.add(17);
	queue.add(34);
	queue.add(21);
	queue.add(28);
	printQueue(queue);
	StackSort ss=new StackSort();
	System.out.println("Sorted:");
	queue=ss.sort(queue);
	printQueue(queue);	
	
	queue=new LinkedList<Integer>();
	System.out.print("Add to stack");
	queue.add(9);
	queue.add(14);
	queue.add(17);
	queue.add(3);
	queue.add(21);
	queue.add(5);
	queue.add(1);
	printQueue(queue);
	System.out.println("Reversed:");
	queue=ss.sort(queue);
	printQueue(queue);	
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
	
}
	
}