Build a queue using 2 stacks

queue_2_stacks

using System;
using System.Collections.Generic;

// Implement a queue using two stacks

namespace QueueUsingStacks
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Queue queue = new Queue();
            queue.Enqueue(1);
            Console.WriteLine("Enqueue 1");
            
            queue.Enqueue(2);
            Console.WriteLine("Enqueue 2");
            
            queue.Enqueue(3);
            Console.WriteLine("Enqueue 3");
            
            test(queue.Dequeue(), 1);
            
            queue.Enqueue(4);
            Console.WriteLine("Enqueue 4");
            
            queue.Enqueue(5);
            Console.WriteLine("Enqueue 5");
            
            test(queue.Dequeue(), 2);
        }
        
        static void test(int val, int expected) {
            Console.WriteLine("Dequeued value is {0}, expected {1}", val, expected);
        }
    }
    
    class Queue {
        
        Stack<int> inStack;
        Stack<int> outStack;
        
        public Queue() {
             inStack = new Stack<int>();
             outStack = new Stack<int>();
        }
        
        // O(1)
        public void Enqueue(int value) {
            inStack.Push(value);
        }

        // Amortized O(n) for n items in queue
        public int Dequeue() {
            if (outStack.Count == 0) {
                while (inStack.Count > 0) {
                    outStack.Push(inStack.Pop());
                }
            }
            
            return outStack.Pop();
        }
    }
}