{"id":9631,"date":"2022-09-21T06:22:24","date_gmt":"2022-09-21T06:22:24","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9631"},"modified":"2022-10-03T03:56:41","modified_gmt":"2022-10-03T03:56:41","slug":"how-to-sort-a-stack-using-recursion","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/how-to-sort-a-stack-using-recursion\/","title":{"rendered":"How to Sort a Stack using Recursion"},"content":{"rendered":"

\"\"<\/p>\n

First we\u2019ll discuss what is Stack:<\/h3>\n

Stack follows the principle of LIFO (Last in First out) i.e. element which is inserted at last will be removed first. The operation for insertion of elements in stack is known as Push operation and the operation for deletion of element in stack<\/a> is known as Pop operation.<\/p>\n

\"\"<\/p>\n

Examples 1:<\/strong>
\nInput: <\/strong>11 17 -2 5 1<\/p>\n

\"\"<\/p>\n

Output:<\/strong> 17 11 5 1 -2<\/p>\n

Explanation:<\/strong> The Sorted stack contains elements in descending order from top to bottom of the stack.<\/p>\n

Examples 2:<\/strong>
\nInput: 1 2 3 4
\nOutput: 4 3 2 1<\/p>\n

The Recursion uses the stack to complete its task. The stack is a linear data structure that follows a particular order i.e. Last in First Out also known as LIFO. <\/p>\n

Algorithm to Sort a Stack using recursion<\/h3>\n

The idea is quite easy. <\/p>\n

    \n
  1. Firstly, We will pop out the top element of the stack and pass the remaining stack to the same function i.e (recursive call).<\/li>\n
  2. Continue the above process until the stack becomes empty. <\/li>\n
  3. The moment the stack becomes empty we will call an insert function to insert the elements again in the stack in sorted order.<\/li>\n
  4. Insert function inserts the elements at their correct place recursively.<\/li>\n<\/ol>\n

    Code:<\/p>\n

    C++ Implementation<\/h3>\n\t\t\t\t\t\t