Table of Contents
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,
stackandtempStack. - Pop an element
currentDatafromstackand compare it with head oftempStack. - If
currentDatait greater, push it totempStack. - If
currentDatais lesser than  head oftempStack, pop an element fromtempStackand push it tostackuntil you get the element which is greater thancurrentData - In the end,
tempStackwill 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]); } } } } |
=================
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
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
