Question 44 : Sort an stack using another stack

 You need to sort an stack using another stack. You can use push and pop operation of stack to do so,

Queue

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.

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:

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

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest