If you want to practice data structure and algorithm programs, you can go through 100+ 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 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
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
Elements of stacks are:
10
30
50
40
=================
After Sorting :
=================
Elements of stacks are:
10
30
40
50
That’s all about how to sort a Stack using another stack
