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 by referring some best sites to learn programming languages.

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

}
Previous post Remove all adjacent duplicates
Next post Maximum Edges

Leave a Reply

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