Sort a Stack using another stack

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm programs.
In this post,  we will see how to sort a stack using another stack.

Problem :

Given a Stack,  you need to sort it with the help of temporary stack.

Solution :

  • Let's say,  you have two stacks,  stack  and tempStack. 
  • Pop an element from stack and compare it with head of tempStack. 
  • If element it greater, push it to tempStack. 
  • If element is lesser than  head of tempStack, pop the element from tempStack and push it to stack until you get the element which is greater than head of tempStack. 
  • In the end,  tempStack will be sorted stack. 

Java code:

public static StackCustom sortStack(StackCustom stack)
 {
  StackCustom tempStack = new StackCustom(10);
  while(!stack.isEmpty())
  {
   int currentData=stack.pop();
   while(!tempStack.isEmpty() && tempStack.peek() > currentData) {
    stack.push(tempStack.pop());
         }
   tempStack.push(currentData);
  }
  return tempStack;
 }

Complete Java program to sort a stack using addition stack:

package org.arpit.java2blog;
/**
 * @author Arpit Mandliya
 */
public class StackCustom {
 int size;
 int arr[];
 int top;

 StackCustom(int size) {
  this.size = size;
  this.arr = new int[size];
  this.top = -1;
 }

 public void push(int pushedElement) {
  if (!isFull()) {
   top++;
   arr[top] = pushedElement;
  } else {
   System.out.println("Stack is full !");
  }
 }

 public int pop() {
  if (!isEmpty()) {
   int returnedTop = top;
   top--;
   return arr[returnedTop];

  } else {
   System.out.println("Stack is empty !");
   return -1;
  }
 }

 public int peek() {
  return arr[top];
 }

 public boolean isEmpty() {
  return (top == -1);
 }

 public boolean isFull() {
  return (size - 1 == top);
 }

 public static void main(String[] args) {
  StackCustom stackCustom = new StackCustom(10);
  System.out.println("=================");
  stackCustom.push(10);
  stackCustom.push(30);
  stackCustom.push(50);
  stackCustom.push(40);
  stackCustom.printStack(stackCustom);
  StackCustom sortedStack=sortStack(stackCustom);
  System.out.println("=================");
  System.out.println("After Sorting :");
  System.out.println("=================");
  sortedStack.printStack(sortedStack);
  
 }

// Sort a stack using another stack 
public static StackCustom sortStack(StackCustom stack)
 {
  StackCustom tempStack = new StackCustom(10);
  while(!stack.isEmpty())
  {
   int currentData=stack.pop();
   while(!tempStack.isEmpty() && tempStack.peek() > currentData) {
    stack.push(tempStack.pop());
         }
   tempStack.push(currentData);
  }
  return tempStack;
 }
 
 public  void printStack(StackCustom stack)
 {
 if(top>=0)
 {
  System.out.println("Elements of stacks are:");
  for (int i = 0; i <= top; i++) {
   System.out.println(arr[i]);
  }
 }
 
 }
}
When you run above program, you will get below output
=================
Elements of stacks are:
10
30
50
40
=================
After Sorting :
=================
Elements of stacks are:
10
30
40
50

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012