4 votes 4 votes In implementation of queue using stack, deletion of second element from front take Ο(1) time, when insertion take Ο(n) time. Which of the following is correct ? True / False DS data-structures queue time-complexity true-false + – Hemant Parihar asked Jan 20, 2018 retagged Jul 7, 2022 by Lakshman Bhaiya Hemant Parihar 1.5k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Hemant Parihar commented Jan 20, 2018 reply Follow Share One more implementation I know, where we use only 1 stack. But along with the PUSH, POP, we require a special operation REVERSE (which can reverse the elements of the stack). In that case, I know we can perform insertion in O(1) times simply push it into the stack. And deletion by first reversing the element of the stack, the perform pop, and then again reverse it. So deletion takes O(n) time. We can also perform deletion in it in O(1), simply pop it. But insertion take O(n) time, as for insertion we first reverse the elements of the stack, the push it, and then again reverse it. But here in the question no where mention the revere operation. 0 votes 0 votes Hemant Parihar commented Jan 20, 2018 reply Follow Share Oh, to perform the REVERSE operation we can use another stack, so no need to explicitly mention it. Thank you. 1 votes 1 votes MIRIYALA JEEVAN KUMA commented Jan 21, 2018 reply Follow Share Since there are two implementations it completely depends on the implementation? 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes By this approach it wil be true-- enQueue(q, x) 1) While stack1 is not empty, push everything from satck1 to stack2. 2) Push x to stack1 . 3) Push everything back to stack1. dnQueue(q) 1) If stack1 is empty then error 2) Pop an item from stack1 and return it Gaurav Upreti answered Jan 20, 2018 selected Jan 20, 2018 by Hemant Parihar Gaurav Upreti comment Share Follow See all 0 reply Please log in or register to add a comment.