Home Misc Given a stack, how will you reverse it using only stack operations PUSH and POP?

Given a stack, how will you reverse it using only stack operations PUSH and POP?

by nikoo28
0 comments 1 minutes read

Question: You are given a stack and you have to reverse it, using only stack operations push and pop.

The algorithm for the above problem can be given in this way:-

  • First POP all elements of the stack till it becomes empty
  • Now for each upward step in the recursion, push the elements at the bottom of the stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void reverseStack(struct stackNode * top)
{
    int data;
 
    if(isStackEmpty(top))
        return;
 
    //get the top data
    data = POP(top);
 
    //recursive call for the next top element
    reverseStack(top);
 
    //after the recursion ends, we need to insert the numbers at the Bottom
    insertAtBottom(top, data);
}
 
void insertAtBottom(struct stackNode * top, int data)
{
    int temp;
 
    //check for terminating condition of recursive call
    if(isStackEmpty(top))
    {
        //when the stack is empty, just add the data
        //this will be the last data of original stack
        top = push(top,data);
        return;
    }
 
    //again we get the top elements one by one
    temp = POP(top);
 
    //a recursive call
    insertAtBottom(top, data);
 
    top = push(top, temp);
}

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More