Sort a stack using temporary stack and recursion

There are two different methods to sort a stack. They are

  • Method 1: In this approach, a stack is sorted using another temporary stack.
  • Method 2:  In this approach, a stack is sorted using recursion.

Method 1 to sort a stack using a temporary stack

 The push and pop operations are carried out between the input_stack and the temporary_stack in such a way that the temporary stack contains the sorted input stack. The algorithm to sort a stack using another temporary stack is discussed below.

Algorithm

  1. Create a temporary stack say temp_stack.
  2. Repeat until the input_stack is not empty
  3. Pop an element from input_stack call it temp.
  4. While temp_stack is not empty and top of the temp_stack > temp, pop data from temp_stack and push it to the input_stack
  5. Push temp to the temp_stack
  6. Print the temp_stack.
#include <bits/stdc++.h>
using namespace std;
stack<int> sort_stack(stack<int> &stack1)
{
    stack<int> stack2;
    while(!stack1.empty())
    {
        int temp = stack1.top();
        stack1.pop();
        while(!stack2.empty() && stack2.top() > temp)
        {
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack2.push(temp);
    }
    return stack2;
}
int main()
{
    stack<int> stack1;
    int n;
    cout << "\nEnter the number of elements to be pushed to the stack : ";
    cin >> n;
    cout << "\nEnter the stack elements : ";
    for(int i = 0; i < n; i++)
    {
        int data;
        cin >> data;
        stack1.push(data);
    }
    stack<int> stack2 = sort_stack(stack1);
    cout <<"\nSorted Stack : ";
    while(!stack2.empty())
    {
        cout << stack2.top()<< " ";
        stack2.pop();
    }
    cout << endl;
    return 0;
}

Method 2 to sort a stack using recursion

The algorithm given below describes how to sort a stack using recursion.

Algorithm

sort_stack(stack)

  1. If the stack is not empty,
  • Pop element from the stack and store it in a temporary variable say temp.
  • Sort_and_insert(stack, temp)

sort_and_insert(stack, temp)

  • If the stack is empty or temp > stack.top()
  • Push temp to the top of the stack.
  • else,
  • Pop data from stack and store it in temp2.
  • sort_and_insert(stack, temp)
  • push(stack, temp2)
#include <stdio.h>
#include <stdlib.h>
struct stack
{
    int data;
  struct stack *ptr;
};

void create(struct stack **s)
{
     *s = NULL;
}

int isEmpty(struct stack *s)
{
     if (s == NULL)
            return 1;
     return 0;
}

void push(struct stack **s, int data)
{
  struct stack *temp = (struct stack *)malloc(sizeof(*temp));
  if (temp == NULL)
  {
      return;
  }
  temp->data = data;
  temp->ptr = *s;
  *s = temp;
}

int pop(struct stack **s)
{
  int data;
   struct stack *temp;
  data = (*s)->data;
   temp = *s;
  (*s) = (*s)->ptr;
free(temp);
  return data;
}

int top(struct stack *s)
{
  return (s->data);
}

void sort_stack_and_insert(struct stack **s, int data)
{
  if (isEmpty(*s) || data > top(*s))
  {
     push(s, data);
     return;
 }
  int temp = pop(s);
  sort_stack_and_insert(s, data);
  push(s, temp);
}

void sort_stack(struct stack **s)
{
   if (!isEmpty(*s))
  {
    int data = pop(s);
    sort_stack(s);
    sort_stack_and_insert(s, data);
  }
}

void display_stack(struct stack *s)
{
 while (s)
  {
      printf("%d ", s->data);
      s = s->ptr;
 }
 printf("\n");
}

int main(void)
{
struct stack *top;
 create(&top);
 int n;
 printf("\nEnter the number of elements to be pushed to the stack : ");
 scanf("%d",&n);
  int i,data;
  printf("\nInput the stack elements : ");
  for(i = 0; i < n; i++)
    {
        scanf("%d",&data);
        push(&top, data);
    }
printf("\n");
sort_stack(&top);
printf("Sorted Stack : ");
display_stack(top);
return 0;

 

#include <bits/stdc++.h>
#include <stdlib.h>
# define MAX 5
using namespace std;
stack <int> stack1;
int arr[MAX], i = 0;
void sort_stack()
{
    if (!stack1.empty())
    {
      int data = stack1.top();
      arr[i] = stack1.top();
      stack1.pop();
      i++;
     sort_stack();
    }
}
void display_stack()
{
    sort(arr,arr+MAX);
    for(int i = MAX-1; i >=0; i--)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main()
{
 int i,data;
 cout << "\nInput the stack elements : ";
 for(i = 0; i < MAX; i++)
    {
        cin >> data;
        stack1.push(data);
    }
   cout << endl;
   sort_stack();
   printf("Sorted Stack : ");
   display_stack();
   return 0;
}

 

 

 

 

 

 

 

 

Test case : 

  • Input: 10 2 1 6 19
  • Output: 19 10 6 2 1