Method 1 (By making enQueue operation costly) This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.enQueue(q, x):. While stack1 is not empty, push everything from stack1 to stack2. Push x to stack1 (assuming size of stacks is unlimited). Push everything back to stack1.Here time complexity will be O(n)deQueue(q):. If stack1 is empty then error. Pop an item from stack1 and return itHere time complexity will be O(1)Below is the implementation of the above approach.
C Program To Implement Stack Using Two Queues Examples
FilternoneOutput: 123Method 2 (By making deQueue operation costly)In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned. EnQueue(q, x)1) Push x to stack1 (assuming size of stacks is unlimited).Here time complexity will be O(1)deQueue(q)1) If both stacks are empty then error.2) If stack2 is emptyWhile stack1 is not empty, push everything from stack1 to stack2.3) Pop the element from stack2 and return it.Here time complexity will be O(n)Method 2 is definitely better than method 1.Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty. So, the amortized complexity of the dequeue operation becomes.Implementation of method 2. FilternoneOutput: 1 2 3Queue can also be implemented using one user stack and one Function Call Stack. Below is modified Method 2 where recursion (or Function Call Stack) is used to implement queue using only one user defined stack. EnQueue(x)1) Push x to stack1.deQueue:1) If stack1 is empty then error.2) If stack1 has only one element then return it.3) Recursively pop everything from the stack1, store the popped itemin a variable res, push the res back to stack1 and return resThe step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in deQueue and all other items are pushed back in step3.
C Program To Implement Stack Using 2 Queues
Implementation of method 2 using Function Call Stack.