Queue using Stacks.cpp

// 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; 
} 

/*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.*/