Friday 21 February 2014

Sort a stack using recursion in Java

Question : 

Sorting a Stack using push,pop,isEmpty and peek.

Code :

 package SortingTechniques;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 11:02 AM
 */
public class StackSort {

    public void sortStack(Stack<Integer> stack){

        int no = stack.pop();
        if(stack.size() != 1){
            sortStack(stack);
        }
        insert(stack,no);
    }

    private void insert(Stack<Integer> stack, int no){

        if(stack.size() == 0){
            stack.push(no);
        }
        else{
            int newPeakedNo = stack.peek();
            if(no >= newPeakedNo){
                stack.push(no);
            }
            else{
                int newPoppedNo = stack.pop();
                insert(stack, no);
                stack.push(newPoppedNo);
            }
        }
    }

    public static void main(String args[]){

        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println("Stack Before Sort : " + Arrays.toString(stack.toArray()));
        new StackSort().sortStack(stack);
        System.out.println("Stack After Sort : " + Arrays.toString(stack.toArray()));

    }

}



Output :

Stack Before Sort : [5, 4, 3, 2, 1]
Stack After Sort : [1, 2, 3, 4, 5]


Note :

A similar question was solver in previous post about how to reverse a Stack in Java. It has similar logic. 

No comments:

Post a Comment

t> UA-39527780-1 back to top