Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Approach 1: space complexity will be O(N) due to recursive call and Time complexity will be O(N^2)
- insert function pushes the element at the bottom of the stack everytime.
- reverseStack function does nothing, just popping elements one by one till the stack is empty
- and then push the elements one by one from bottom using the insert function which pushes the element at bottom.
- Implementation of above approach is below
- */
- /*
- Approach 2:
- 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
- without using extra space.
- */
- void insert(stack <int> &st,int ele){
- if(st.size()==0){st.push(ele); return;}
- int temp=st.top();
- st.pop();
- insert(st,ele);
- st.push(temp);
- return;
- }
- void reverseStack(stack<int> &st) { //This
- if(st.size()==0) return; //
- if(st.size()==1) return; //
- int temp=st.top();
- st.pop();
- reverseStack(st);
- insert(st,temp);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement