#include <iostream>
#include <stack>
#include <stdexcept>
/*
Queue implemented using two stacks.
Core idea:
- stack_in : receives all new elements (enqueue)
- stack_out : serves elements in correct queue order (dequeue)
When stack_out is empty and we need to dequeue or peek:
- Move all elements from stack_in to stack_out
This reverses the order, making the oldest element accessible.
This approach provides:
- Clean structure
- Amortized O(1) operations
- Clear separation of responsibilities
*/
class QueueUsingStacks {
private:
std::stack<int> stack_in; // holds newly added elements
std::stack<int> stack_out; // holds elements in queue order
// Move elements from stack_in to stack_out when needed
void transferIfNeeded() {
if (stack_out.empty()) {
while (!stack_in.empty()) {
stack_out.push(stack_in.top());
stack_in.pop();
}
}
}
public:
// Add an element to the queue
void enqueue(int value) {
stack_in.push(value);
}
// Remove and return the front element
int dequeue() {
transferIfNeeded();
if (stack_out.empty()) {
throw std::runtime_error("Queue is empty");
}
int value = stack_out.top();
stack_out.pop();
return value;
}
// Return the front element without removing it
int front() {
transferIfNeeded();
if (stack_out.empty()) {
throw std::runtime_error("Queue is empty");
}
return stack_out.top();
}
// Check if the queue is empty
bool empty() const {
return stack_in.empty() && stack_out.empty();
}
};
int main() {
QueueUsingStacks q;
// Add to stack_in
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
std::cout << "Front element: " << q.front() << "\n"; // should be 10 // stack_out
std::cout << "Dequeued: " << q.dequeue() << "\n"; // removes 10 // stack_out
std::cout << "Dequeued: " << q.dequeue() << "\n"; // removes 20 // stack_out
q.enqueue(40);
std::cout << "Front element: " << q.front() << "\n"; // should be 30 // stack_out
std::cout << "Dequeued: " << q.dequeue() << "\n"; // removes 30
std::cout << "Dequeued: " << q.dequeue() << "\n"; // removes 40
std::cout << "Queue empty: " << std::boolalpha << q.empty() << "\n";
}
/*
run:
Front element: 10
Dequeued: 10
Dequeued: 20
Front element: 30
Dequeued: 30
Dequeued: 40
Queue empty: true
*/
