Sort a stack using a temporary stack
Last Updated :
25 May, 2023
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
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...