Search This Blog

Thursday, May 24, 2012

Implement stack from two que

class StackFromQue
    {
        private Queue<int> a = new Queue<int>();
        private Queue<int> b = new Queue<int>();

        //Optimize for Push operation
        public void Push(int value)
        {
            a.Enqueue(value);
        }

        public int Pop()
        {
            if (a.Count.Equals(0) && b.Count.Equals(0))
            {
                throw new InvalidOperationException("Empty stack");
            }

            if (a.Count > 0)
            {
                return PopOperation(a, b);
            }
            else
            {
                return PopOperation(b, a);
            }
        }

        private int PopOperation(Queue<int> first, Queue<int> second)
        {
            while (first.Count > 1)
            {
                second.Enqueue(first.Dequeue());
            }

            return first.Dequeue();
        }
    }

Explanation:

1. For Push operation, Enque all the values in Que 1.

2. For Pop opeartion, deque all the values from the current que into the next que until there is only one value in the current que. Return the last value and deque them. For the next value swap the ques.

Note: This is optimized for Push operation. It can be optimized for Pop operation in the reverse manner.

No comments:

Post a Comment