Program to reverse a Stack

Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics and Stack Implementation.

Let’s look into basic class definition of a Stack.

class Stack
{
    private:
        int size;
        int top;
        int* elements;

    public:
        Stack (int sz);
        ~Stack ();
        bool push (int value);
        int pop ();
        bool isEmpty ();
        int maxSize ();
        int entries ();
        int atTop ();
        void printContent ()
        {
            cout << "Stack contents: " ;
            for (int i = 0; i < top; i++)
                cout << elements[i] << " ";
            cout << endl;
        }
};

Reversing a Stack

Here we have to reverse the order of elements present in the Stack which means top elements should go to end of stack and vice-versa. Let’s look into an example to understand it better.

As shown in above example, left side Stack is the given stack and right side stack is the final stack in which elements are reversed.

Algorithm

• Start from the top element in Stack.
• For every element in Stack.
  • POP the element.
  • Call the function again in recursive manner.
  • If Stack is empty then PUSH the earlier POPPED data into the Stack.
  • else POP the Stack till it’s become empty and PUSH the POPPED data into the Stack.

Few of the functions used below are explained in Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.

void insert_at_bottom (Stack* s, int data)
{
    if (s -> isEmpty ())
    {
        s -> push (data);
        return;
    }
    int temp = s -> pop ();
    insert_at_bottom (s, data);
    s -> push (temp);
}

void reverse_stack_data (Stack* s)
{
    if (s->isEmpty ())
        return;
    int data = s -> pop ();
    reverse_stack_data (s);
    insert_at_bottom (s, data);
}

Let’s define a main function to use above methods.

int main ()
{
    Stack s (20);
    s.push (5);
    s.push (8);
    s.push (4);
    s.push (7);
    s.push (3);
    s.push (9);
    s.push (2);
    s.push (12);
    s.push (1);
    s.printContent ();

    reverse_stack_data (&s);
    s.printContent ();
}

Let’s analyze the output of this main function.

Stack contents: 5 8 4 7 3 9 2 12 1 
Stack contents: 1 12 2 9 3 7 4 8 5