You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).
A. O(m)
B. O(n)
C. O(m*n)
D. Data is insufficient
Answer:A
You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).
A. O(m) B. O(n) C. O(m*n) D. Data is insufficient
Explanation: You must pop each element from the first stack and push it into the second stack to perform the deQueue process. In this scenario, you must pop ‘m’ times and execute ‘m’ times of push operations. Then you pop the first element from the second stack (at a constant rate) and move all of the elements to the first stack (as before) (‘m-1′ times). As a result, the time complexity is O. (m).