Sort a Stack using another stack

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

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 currentData from stack and compare it with head of tempStack.
• If currentData it greater, push it to tempStack.
• If currentData is lesser than  head of tempStack, pop an element from tempStack and push it to stack until you get the element which is greater than currentData
• In the end, tempStack will be sorted 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;
} 

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

That's all about how to sort a Stack using another stack