Implement a queue using stacks (efficient enqueue and dequeue)?

public class MyQueue {

private Stack<int> stackIn = new Stack<int>();

private Stack<int> stackOut = new Stack<int>();

// Enqueue: push into stackIn (O(1))

public void Enqueue(int x) {

stackIn.Push(x);

// Dequeue: if stackOut empty, pour all from stackIn to

stackOut, then pop (amortized O(1))

public int Dequeue() {

if (stackOut.Count == 0) {

while (stackIn.Count > 0) {

stackOut.Push(stackIn.Pop());

return stackOut.Pop();

public int Peek() {

if (stackOut.Count == 0) {

while (stackIn.Count > 0) {

stackOut.Push(stackIn.Pop());

return stackOut.Peek();

public bool IsEmpty() {

return stackIn.Count == 0 && stackOut.Count == 0;

Follow on:

Explanation:

Two stacks are used: stackIn for enqueue, stackOut for dequeue. Elements are

transferred only when needed, making both operations amortized O(1).