C++ Queue Implementation using Two Stacks | CodingHumans |

 Queue Implementation  using Two Stacks

 Queue implementation usinq two Stacks

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).

Code:

#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(10); 
    q.enQueue(20); 
    q.enQueue(30); 
  
    cout << q.deQueue() << '\n'; 
    cout << q.deQueue() << '\n'; 
    cout << q.deQueue() << '\n'; 
  
    return 0; 
} 

Output:

10

20

30

If you Have Any doubts join the discussions below , our moderators will reach to your doubts .