Implement Queue with 2 Stacks

In this approach, newStack has the newest elements on top and oldStack has the oldest elements on top. When we dequeue an element, we want to remove the oldest element first, and so we dequeue from oldStack. If oldStack is empty, then we want to transfer all elements from newStack into this old stack in reverse order.To insert an element, we push onto stackNewest, since it has the newest
elements on top.

Below is the code, this implements generic interface

    /// <summary>
    /// My Queue Interface
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IMyQueue<T>
    {
        /// <summary>
        /// Adds the specified element.
        /// </summary>
        /// <param name="element">The element.</param>
        void Add(T element);
        /// <summary>
        /// Peeks this instance.
        /// </summary>
        /// <returns></returns>
        T Peek();
        /// <summary>
        /// Removes this instance.
        /// </summary>
        /// <returns></returns>
        T Remove();
    }

    /// <summary>
    /// 
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <seealso cref="TwoStacksAndQueues.IMyQueue{T}" />
    public class MyQueue<T> : IMyQueue<T>
    {
        private Stack<T> oldStack;
        private Stack<T> newStack;
        public MyQueue()
        {
            oldStack = new Stack<T>();
            newStack = new Stack<T>();
        }

        /// <summary>
        /// Adds the specified element.
        /// </summary>
        /// <param name="element">The element.</param>
        public void Add(T element)
        {
            newStack.Push(element);
        }

        /// <summary>
        /// Peeks this instance.
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            T element;
            while (newStack.Count > 0)
            {
                oldStack.Push(newStack.Pop());
            }
            element = oldStack.Peek();
            return element;
        }

        /// <summary>
        /// Removes this instance.
        /// </summary>
        /// <returns></returns>
        /// <exception cref="System.InvalidOperationException">No Element Exists to remove</exception>
        public T Remove()
        {
            T element;
            if (oldStack.Count == 0)
            {
                while (newStack.Count > 0)
                {
                    oldStack.Push(newStack.Pop());
                }
            }

            if (oldStack.Count > 0)
            {
                element = oldStack.Pop();
            }
            else
            {
                throw new InvalidOperationException("No Element Exists to remove");
            }
            return element;
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s