Reverse a Stack

Reverse a stack using standard stack operations like push(), pop(), isEmpty().

Comments

  1. we can easily do this using 2 extra stacks.
    Are we required to do this without using any extra space?

    ReplyDelete
  2. You can use the system stack,but no external extra space.Try using recursion.

    ReplyDelete
  3. // first count the no. of items.Then the idea is to store the top item in a temporary variable and then pop all the items recursively,push the stored item first and then all the items in the stack frame(recursively). Now, pop one item as it is the same as the bottommost item and decrement the counter as we have to reverse n-1 items only this time. Follow the recursive approach back again and so on...

    // this function counts the no. of items
    int noOfItems(stack &s){
    static int c=0;
    if(s.isEmpty())return c;
    item t=s.pop();
    c++;
    noOfItems(s);
    s.push(t);
    return c;
    }

    // this function fixes one item at its appropriate position in the reverse order.

    void iteration(stack &s,int count,int i,int r){
    static int setr=1;
    setr=r;
    if(i){
    item fix=s.pop(); //assuming that s.pop() returns //the item popped
    s.push(fix);
    i=0;
    }

    if(count){
    item t=s.pop();
    iteration(s,count-1,0,1);
    if(setr){
    s.push(fix)
    setr=0;
    }
    s.push(t);
    }

    }


    void reverse(stack &s){
    static int c=noOfItems(&s);
    while(c--){
    iteration(s,c+1,1,1);
    s.pop();
    }
    }

    ReplyDelete
  4. the above approach takes O(n^2) with space complexity of O(n). can we do better?

    ReplyDelete
  5. 1. Have a utility function , which initially passes the source stack and an empty destination stack.

    2. At each stage , pop the element from the source and push it into destination. The point to note, pass the reference during the recursion.

    3. Each the source is empty , assign the source label to the destination and return.

    Space Complexity : O(1)
    Time Complexity : O(n)

    ReplyDelete

Post a Comment

Popular posts from this blog