stack using recursion

Reverse a stack using recursion

You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:
isEmpty(S)
push(S)
pop(S)
Solution:
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.
For example, let the input stack be
    1  <-- top
    2
    3
    4   

First 4 is inserted at the bottom.
    4 <-- top

Then 3 is inserted at the bottom
    4 <-- top    
    3

Then 2 is inserted at the bottom
    4 <-- top    
    3 
    2
     
Then 1 is inserted at the bottom
    4 <-- top    
    3 
    2
    1
So we need a function that inserts at the bottom of a stack using the above given basic stack function.
void insertAtBottom((): First pops all stack items and stores the popped item in function call stack using recursion. And when stack becomes empty, pushes new item and all items stored in call stack.
void reverse(): This function mainly uses insertAtBottom() to pop all items one by one and insert the popped items at the bottom.
// Below is a recursive function that inserts an element
// at the bottom of a stack.
void insertAtBottom(struct sNode** top_ref, int item)
{
    if (isEmpty(*top_ref))
        push(top_ref, item);
    else
    {
 
        /* Hold all items in Function Call Stack until we
           reach end of the stack. When the stack becomes
           empty, the isEmpty(*top_ref)becomes true, the
           above if part is executed and the item is inserted
           at the bottom */
        int temp = pop(top_ref);
        insertAtBottom(top_ref, item);
 
        /* Once the item is inserted at the bottom, push all
           the items held in Function Call Stack */
        push(top_ref, temp);
    }
}
 
// Below is the function that reverses the given stack using
// insertAtBottom()
void reverse(struct sNode** top_ref)
{
    if (!isEmpty(*top_ref))
    {
        /* Hold all items in Function Call Stack until we
           reach end of the stack */
        int temp = pop(top_ref);
        reverse(top_ref);
 
        /* Insert all the items (held in Function Call Stack)
           one by one from the bottom to top. Every item is
           inserted at the bottom */
        insertAtBottom(top_ref, temp);
    }
}
Output:
 Original Stack 
 1  2  3  4 
 Reversed Stack 
 4  3  2  1

Comments

Post a Comment

Popular posts from this blog

Number theory Part-2

Image
Introduction Problems in competitive programming which involve Mathematics are are usually about number theory, or geometry. If you know number theory, that increases your ammo heavily in solving a lot of tougher problems, and helps you in getting a strong hold on a lot of other problems, too. Problems in competitive programming require insight, so just knowing some topics is not enough at all. All of the problems requires more or less math tough. For instance, solving large systems of equations and approximating solutions to differential equations.  Set Theory Before we proceed, let us get through the some common set operations. Q.) What is a Set? -In mathematics, a set is a collection of distinct objects, considered as an object in its own right. For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6}. Sets are one of the most fundamental con...
Read more

Number Theory Part-1

Image
Introduction: Problems in competitive programming which involve Mathematics are are usually about number theory, or geometry. If you know number theory, that increases your ammo heavily in solving a lot of tougher problems, and helps you in getting a strong hold on a lot of other problems, too. Problems in competitive programming require insight, so just knowing some topics is not enough at all. All of the problems requires more or less math tough. For instance, solving large systems of equations and approximating solutions to differential equations. Modulo: Modulo operation gives the remainder after division, when one number is divided by another. It is denoted by % sign. Example: We have two numbers 5 and 2, then 5%2 is 1 as when 5 is divided by 2, it leaves 1 as remainder. Properties: Some of the properties of modulo are: (a+b)%c = (a%c + b%c )%c. (a * b)%c = ((a%c) * (b%c))%c. Example: Let’s say a = 5, b = 3, c = 2. Then: 1) (5+3)%2 = 8%2 = 0. Similarly (5%2 ...
Read more
HOT UPDATE: Added tricks about REGEX, Raw Strings, User-defined Literals. As a whole new section! WARNING: Many of these things belong to C++11 so use C++11 in order to test anything here :) I just write a short version for this article, because it's now in the main page. I recommend you to click on "Read more »" and read more :) Here is a short trick for the short version: I see lots of programmers write code like this one: pair < int , int > p ; vector <int> v ; // ... p = make_pair ( 3 , 4 ); v . push_back ( 4 ); v . push_back ( 5 ); while you can just do this: pair < int , int > p ; vector <int> v ; // ... p = { 3 , 4 }; v = { 4 , 5 }; 1. Assign value by a pair of {} to a container I see lots of programmers write code like this one: pair < int , int > p ; // ... p = make_pair ( 3 , 4 ); while you can just do this: pair < int , int > p ; // ... p = { 3 , 4 }; even a more complex ...
Read more