Last Updated on March 30, 2022 by Ria Pathak
Concepts Used:
Stacks
Difficulty Level:
Easy.
Problem Statement :
Given a stack of integers, sort it in ascending order using another temporary stack.
See original problem statement here
Solving Approach:
Approach 1 ( Using temporary stack ):
We follow this 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.
Approach 2 ( Using recursion ):
- The key is to store all values in function call stack.
- When the stack becomes empty ,insert the values stored in sorted order.
Psuedo code:
sort(stack s)
{
if (!s.empty())
{
temp=s.pop();
sort(s);
insert(s,temp);
}
}
insert(stack s, element){
if (s.empty()||element>s.top())
s.push(element);
else
{
temp = s.pop();
insert(s, element);
s.push(temp);
}
}Solutions:
#include <stdio.h>
#define ll long long
void sortStack(int input[],int size)
{
int tmpStack[size];
int top=-1;
while (size>=0)
{
int tmp = input[size];
size--;
// while temporary stack is not empty and top
// of stack is greater than temp
while (top>=0 && tmpStack[top] < tmp)
{
// pop from temporary stack and push
// it to the input stack
input[++size]=tmpStack[top];
top--;
}
// push temp in tempory of stack
tmpStack[++top]=(tmp);
}
while (top>=0)
{
printf("%d ",tmpStack[top]);
top--;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,x;
scanf("%d",&n);
int input[n];int top=-1;
for(int i=0;i<n;i++){
scanf("%d",&x);
input[++top]=x;
}
// This is the temporary stack
sortStack(input,top);
printf("\n");
}
return 0;
}
#define ll long long
// C++ program to sort a stack using an
// auxiliary stack.
#include <bits stdc++.h="">
using namespace std;
// This function return the sorted stack
stack<int> sortStack(stack<int> &input)
{
stack<int> tmpStack;
while (!input.empty())
{
// pop out the first element
int tmp = input.top();
input.pop();
// while temporary stack is not empty and top
// of stack is greater than temp
while (!tmpStack.empty() && tmpStack.top() < tmp)
{
// pop from temporary stack and push
// it to the input stack
input.push(tmpStack.top());
tmpStack.pop();
}
// push temp in tempory of stack
tmpStack.push(tmp);
}
return tmpStack;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,x;
cin>>n;
stack<int> input;
for(int i=0;i<n;i++){ cin="">>x;
input.push(x);
}
// This is the temporary stack
stack<int> tmpStack = sortStack(input);
while (!tmpStack.empty())
{
cout << tmpStack.top()<< " ";
tmpStack.pop();
}
}
}
import java.util.Iterator;
import java.util.*;
import java.io.*;
import java.util.Stack;
class SortingStackExample {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
Stack<integer> stack = new Stack<integer>();
for(int i=0;i<n;i++) {="" int="" x="sc.nextInt();" stack.addelement(x);="" }="" iterator<integer=""> it = stack.iterator();
Stack<integer> sortedStack = sortStack(stack);
it = sortedStack.iterator();
while(it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.print("\n");
}
}
public static Stack<integer> sortStack(Stack<integer> stack) {
Stack<integer> newStack = new Stack<integer>();
while (!stack.isEmpty()) {
int tmp = stack.pop();
while (!newStack.isEmpty() && newStack.peek() > tmp) {
stack.push(newStack.pop());
}
newStack.push(tmp);
}
return newStack;
}
}
# your code goes here
def sortStack(input_):
tmpStack = []
while (len(input_)):
tmp = input_[-1]
input_.pop()
while (len(tmpStack) and tmpStack[-1] < tmp):
input_.append(tmpStack[-1])
tmpStack.pop()
tmpStack.append(tmp)
return tmpStack
for _ in range(int(input())):
n = int(input())
stack = list(map(int,input().split()))
tmpStack = sortStack(stack)
while len(tmpStack):
print(tmpStack[-1], end = " ")
tmpStack.pop()
print()
[forminator_quiz id="2004"]
This article tried to discuss the concept of stack. Hope this blog helps you understand and solve the problem. To practice more problems on stack you can check out MYCODE | Competitive Programming.