It Is Possible to Implement multiple stack in queue if yes. 1-Is There any limit On the Number of stacks that can be implemented in a queue.

 The problem is opposite of this post. We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

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 it

Here time complexity will be O(1)

// CPP program to implement Queue using // two stacks with costly enQueue() #include <bits/stdc++.h> using namespace std;   struct Queue { stack<int> s1, s2;   void enQueue(int x) { // Move all elements from s1 to s2 while (!s1.empty()) { s2.push(s1.top()); s1.pop(); }   // Push item into s1 s1.push(x);   // Push everything back to s1 while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } }   // Dequeue an item from the queue int deQueue() { // if first stack is empty if (s1.empty()) { cout << "Q is Empty"; exit(0); }   // Return top of s1 int x = s1.top(); s1.pop(); return x; } };   // Driver code int main() { Queue q; q.enQueue(1); q.enQueue(2); q.enQueue(3);   cout << q.deQueue() << '\n'; cout << q.deQueue() << '\n'; cout << q.deQueue() << '\n';   return 0; }



Output:

1
2
3

 
Complexity Analysis:

• Time Complexity:
  • Push operation: O(N).
    In the worst case we have empty whole of stack 1 into stack 2.
  • Pop operation: O(1).
    Same as pop operation in stack.
• Auxiliary Space: O(N).
  Use of stack for storing values.