Sort stack

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.

  1. Create a temporary stack say tmpStack.
  2. While input stack is NOT empty do this:
  3. Pop an element from input stack call it temp
  4. 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 ):

  1. The key is to store all values in function call stack.
  2. 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 
#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



						 
#define ll long long
// C++ program to sort a stack using an 
// auxiliary stack. 
#include  
using namespace std; 
// This function return the sorted stack 
stack sortStack(stack &input) 
{ 
    stack 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 input;
    for(int i=0;i>x;
      input.push(x);

    }

  // This is the temporary stack 
  stack 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 stack = new Stack();
          for(int i=0;i it = stack.iterator();
          Stack sortedStack = sortStack(stack);
          it = sortedStack.iterator();
          while(it.hasNext()) {
              System.out.print(it.next()+" ");
          }
        System.out.print("\n");
        }
 }
 public static Stack sortStack(Stack stack) {
      Stack newStack = new Stack();
      while (!stack.isEmpty()) {
         int tmp = stack.pop();
          while (!newStack.isEmpty() && newStack.peek() > tmp) {
            stack.push(newStack.pop());
          }
          newStack.push(tmp);
      }
      return newStack;
     }

}
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.

Leave a Reply

Your email address will not be published. Required fields are marked *