Interview Question Categories

Stacks using Queues

Stacks using Queues


namespace StackUsingQueues
{
    //Implementation which supports efficient Push and 
    //innefficient Pop
    class StackWithEfficientPush
    {
        Queue<int> Q1 = null;
        Queue<int> Q2 = null;

        public StackWithEfficientPush()
        {
            Q1 = new Queue<int>();
            Q2 = new Queue<int>();
        }

        public void Push(int val)
        {
            Q1.Enqueue(val);
        }

        public int Pop()
        {
            while (Q1.Count > 1)
            {
                Q2.Enqueue(Q1.Dequeue());
            }

            int itemToReturn = Q1.Dequeue();
            Q1 = Q2;
            Q2 = new Queue<int>();
            return itemToReturn;
        }
    }

    //Implementation which supports efficient Pop and 
    //innefficient Push
    class StackWithEfficientPop
    {
        Queue<int> Q1 = null;
        Queue<int> Q2 = null;

        public StackWithEfficientPop()
        {
            Q1 = new Queue<int>();
            Q2 = new Queue<int>();
        }

        public void Push(int val)
        {
            Q1.Enqueue(val);

            while (Q2.Count > 0)
            {
                Q1.Enqueue(Q2.Dequeue());
            }
            Q2 = Q1;
            Q1 = new Queue<int>();
        }

        public int Pop()
        {
            return Q2.Dequeue();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StackWithEfficientPush S = new StackWithEfficientPush();
            S.Push(10);
            S.Push(20);
            S.Push(30);
            S.Push(40);
            S.Push(50);
            Console.WriteLine(S.Pop());
            S.Push(60);
            S.Push(70);
            S.Push(80);
            Console.WriteLine(S.Pop());
            Console.WriteLine(S.Pop());
            Console.WriteLine(S.Pop());
        }
    }
}

No comments:

Post a Comment

Post a Comment