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 5using 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

Output: