However, in a sequence of dequeue operations, the worst case will not occur frequently: Some dequeue operations will be O(1), and some will be O(n). So time complexity of dequeue operation is O(n), which is the worst-case scenario. Total stack operations = n + n + 1 = 2n + 1. When tempStack is empty: Above algorithm pop n elements from mainStack, then push n elements to tempStack and finally pop the top element from tempStack (n is the queue size). So time complexity of dequeue operation is O(1), which is the best-case scenario. When tempStack is not empty: Above algorithm performs only one pop operation. Public class QueueUsingStack Time and space complexity of dequeue operation ![]() Otherwise, pop the top element from mainStack and return it. If mainStack is empty, throw an empty error and return. Note: Assume that the size of each stack is unlimited. Suppose we use mainStack and tempStack to simulate queue process. Our queue model will use two stacks: one for dequeue operation and two for enqueue operation. In other words, the oldest element will be on the top of main stack, which will come first during dequeue operation.ĭequeue operation idea: We simply remove elements from the top of main stack. Step 3: Again transfer all auxiliary stack elements to main stack.Īfter this process, new element will go to the bottom of main stack, which will come last during the dequeue operation. Step 2: Now push new element on top of auxiliary stack. Step1: First transfer stack elements to auxiliary stack. For this, we can use another auxiliary stack to maintain the oder of elements. If we pop stack elements, they will come out in queue order: 1, 2, 3, 4, 5.Įnqueue operation idea: For enqueue operation, we need to insert new element at the bottom of stack. The final order of elements in the stack will be 5, 4, 3, 2, 1. Based on above strategy, the most recent element 5 will be at the bottom and the oldest element 1 will be at the top. Suppose we push 1, 2, 3, 4, 5 into stack. In other words, we can keep the oldest element at the top of stack. One idea would be to keep newly arrived element at the bottom of stack during push operation. So before popping elements from stack, if we reverse the order of elements, we will get popped output in queue order. Here 5 is the last inserted element that is coming last, and 1 is the first inserted element that is coming first.įrom above observation, the final stack output (5, 4, 3, 2, 1) is in the reverse order of the final queue output (1, 2, 3, 4, 5). The order of dequeued output will be 1, 2, 3, 4, 5. Understanding queue order: Suppose we first enqueue 1, 2, 3, 4, 5 into queue and dequeue them one by one. Here 5 is the last inserted element that is coming first, and 1 is the first inserted element that is coming last. The order of popped output will be 5, 4, 3, 2, 1. Understanding stack order: Suppose we first push 1, 2, 3, 4, 5 into stack and pop them one by one. Let's visualize difference between order of elements in stack and queue. Using two stacks: dequeue O(1) and enqueue O(n) Using two stacks: enqueue O(1) and dequeue O(1) average.Using two stacks: dequeue O(1) and enqueue O(n).We must use only standard stack operations like push(x), pop(), top(), size(), and isEmpty() for implementing queue.In contrast, queue is a first-in-first-out (FIFO) data structure, where elements are added from the back end and removed from the front end. Stack is last-in-first-out (LIFO) data structure, in which elements are added and removed from the same end, called top.int dequeue(): Remove an element from the front of queue. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |