Given a stack of integers, sort it in ascending order using another temporary stack.
Examples:
Input : [34, 3, 31, 98, 92, 23]
Output : [3, 23, 31, 34, 92, 98]
Input : [3, 5, 1, 4, 2, 8]
Output : [1, 2, 3, 4, 5, 8]
Algorithm:
- Create a temporary stack say tmpStack.
- While input stack is NOT empty do this:
- Pop an element from input stack call it temp
- while temporary stack is NOT empty and top of temporary stack is greater than temp,
pop from temporary stack and push it to the input stack
- push temp in temporary stack
- The sorted numbers are in tmpStack
Here is a dry run of the above pseudo code.
input: [34, 3, 31, 98, 92, 23]
Element taken out: 23
input: [34, 3, 31, 98, 92]
tmpStack: [23]
Element taken out: 92
input: [34, 3, 31, 98]
tmpStack: [23, 92]
Element taken out: 98
input: [34, 3, 31]
tmpStack: [23, 92, 98]
Element taken out: 31
input: [34, 3, 98, 92]
tmpStack: [23, 31]
Element taken out: 92
input: [34, 3, 98]
tmpStack: [23, 31, 92]
Element taken out: 98
input: [34, 3]
tmpStack: [23, 31, 92, 98]
Element taken out: 3
input: [34, 98, 92, 31, 23]
tmpStack: [3]
Element taken out: 23
input: [34, 98, 92, 31]
tmpStack: [3, 23]
Element taken out: 31
input: [34, 98, 92]
tmpStack: [3, 23, 31]
Element taken out: 92
input: [34, 98]
tmpStack: [3, 23, 31, 92]
Element taken out: 98
input: [34]
tmpStack: [3, 23, 31, 92, 98]
Element taken out: 34
input: [98, 92]
tmpStack: [3, 23, 31, 34]
Element taken out: 92
input: [98]
tmpStack: [3, 23, 31, 34, 92]
Element taken out: 98
input: []
tmpStack: [3, 23, 31, 34, 92, 98]
final sorted list: [3, 23, 31, 34, 92, 98]
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
stack<int> sortStack(stack<int> &input)
{
stack<int> tmpStack;
while (!input.empty())
{
int tmp = input.top();
input.pop();
while (!tmpStack.empty() && tmpStack.top() < tmp)
{
input.push(tmpStack.top());
tmpStack.pop();
}
tmpStack.push(tmp);
}
return tmpStack;
}
int main()
{
stack<int> input;
input.push(34);
input.push(3);
input.push(31);
input.push(98);
input.push(92);
input.push(23);
stack<int> tmpStack = sortStack(input);
cout << "Sorted numbers are:\n";
while (!tmpStack.empty())
{
cout << tmpStack.top()<< " ";
tmpStack.pop();
}
}
|
Java
import java.util.*;
class SortStack
{
public static Stack<Integer> sortstack(Stack<Integer>
input)
{
Stack<Integer> tmpStack = new Stack<Integer>();
while(!input.isEmpty())
{
int tmp = input.pop();
while(!tmpStack.isEmpty() && tmpStack.peek()
< tmp)
{
input.push(tmpStack.pop());
}
tmpStack.push(tmp);
}
return tmpStack;
}
public static void main(String args[])
{
Stack<Integer> input = new Stack<Integer>();
input.add(34);
input.add(3);
input.add(31);
input.add(98);
input.add(92);
input.add(23);
Stack<Integer> tmpStack=sortstack(input);
System.out.println("Sorted numbers are:");
while (!tmpStack.empty())
{
System.out.print(tmpStack.pop()+" ");
}
}
}
|
Python3
def sortStack ( stack ):
tmpStack = createStack()
while(isEmpty(stack) == False):
tmp = top(stack)
pop(stack)
while(isEmpty(tmpStack) == False and
int(top(tmpStack)) < int(tmp)):
push(stack,top(tmpStack))
pop(tmpStack)
push(tmpStack,tmp)
return tmpStack
def createStack():
stack = []
return stack
def isEmpty( stack ):
return len(stack) == 0
def push( stack, item ):
stack.append( item )
def top( stack ):
p = len(stack)
return stack[p-1]
def pop( stack ):
if(isEmpty( stack )):
print("Stack Underflow ")
exit(1)
return stack.pop()
def prints(stack):
for i in range(len(stack)-1, -1, -1):
print(stack[i], end = ' ')
print()
stack = createStack()
push( stack, str(34) )
push( stack, str(3) )
push( stack, str(31) )
push( stack, str(98) )
push( stack, str(92) )
push( stack, str(23) )
print("Sorted numbers are: ")
sortedst = sortStack ( stack )
prints(sortedst)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static Stack<int> sortstack(Stack<int> input)
{
Stack<int> tmpStack = new Stack<int>();
while (input.Count > 0)
{
int tmp = input.Pop();
while (tmpStack.Count > 0 && tmpStack.Peek() < tmp)
{
input.Push(tmpStack.Pop());
}
tmpStack.Push(tmp);
}
return tmpStack;
}
public static void Main(string[] args)
{
Stack<int> input = new Stack<int>();
input.Push(34);
input.Push(3);
input.Push(31);
input.Push(98);
input.Push(92);
input.Push(23);
Stack<int> tmpStack = sortstack(input);
Console.WriteLine("Sorted numbers are:");
while (tmpStack.Count > 0)
{
Console.Write(tmpStack.Pop() + " ");
}
}
}
|
Javascript
<script>
function sortstack(input)
{
let tmpStack = [];
while (input.length > 0)
{
let tmp = input.pop();
while (tmpStack.length > 0 && tmpStack[tmpStack.length - 1] < tmp)
{
input.push(tmpStack[tmpStack.length - 1]);
tmpStack.pop()
}
tmpStack.push(tmp);
}
return tmpStack;
}
let input = [];
input.push(34);
input.push(3);
input.push(31);
input.push(98);
input.push(92);
input.push(23);
let tmpStack = sortstack(input);
document.write("Sorted numbers are:" + "</br>");
while (tmpStack.length > 0)
{
document.write(tmpStack[tmpStack.length - 1] + " ");
tmpStack.pop();
}
</script>
|
Output
Sorted numbers are:
3 23 31 34 92 98
Time Complexity: O(n2) where n is the total number of integers in the given stack.
Auxiliary Space: O(n)
Microsoft
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!