Advertisement
imashutosh51

Reverse stack without using extra space

Jul 22nd, 2022 (edited)
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. /*
  2. Approach 1: space complexity will be O(N) due to recursive call and Time complexity will be O(N^2)
  3. insert function pushes the element at the bottom of the stack everytime.
  4.  
  5. reverseStack function does nothing, just popping elements one by one till the stack is empty
  6. and then push the elements one by one from bottom using the insert function which pushes the element at bottom.
  7. Implementation of above approach is below
  8. */
  9.  
  10. /*
  11. Approach 2:
  12. We can use a linked list for the stack where push and pop will be in O(1) time and reverse will be in O(n) time
  13. without using extra space.
  14. */
  15. void insert(stack <int> &st,int ele){  
  16.     if(st.size()==0){st.push(ele); return;}
  17.     int temp=st.top();
  18.     st.pop();
  19.     insert(st,ele);
  20.     st.push(temp);
  21.     return;
  22. }
  23. void reverseStack(stack<int> &st) {   //This
  24.     if(st.size()==0) return;         //
  25.     if(st.size()==1) return;         //
  26.     int temp=st.top();
  27.     st.pop();
  28.     reverseStack(st);
  29.     insert(st,temp);
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement