Stack extended with Min Value – Generic Stack

Stack which, in addition to push and pop, also has a
function min which returns the minimum element. Push, pop and min
operate in 0(1) time

To solve this we use 2 stack

• superStack
• stackWithMin

superStack behaves like a normal stack and stackWithMin keeps track of minimum values.

Below is code snippet for the class with generic implementation.

    public class StackWithMin<T> where T : IComparable
    {
        private Stack<T> superStack;
        private Stack<T> stackWithMin;

        public StackWithMin()
        {
            this.superStack = new Stack<T>();
            this.stackWithMin = new Stack<T>();
        }
        public T Pop()
        {
            if (this.superStack.Count <= 0)
                throw new InvalidOperationException("Stack Empty.");

            T lastPopedElement = this.superStack.Pop();
            T element = this.stackWithMin.Peek();
            if (element.CompareTo(lastPopedElement) == 0)
            {
                this.stackWithMin.Pop();
            }
            return lastPopedElement;
        }

        public void Push(T element)
        {
            if (this.superStack.Count == 0)
            {
                this.stackWithMin.Push(element);
                this.superStack.Push(element);
                return;
            }

            if (element.CompareTo(this.Min()) <= 0)
            {
                this.stackWithMin.Push(element);
            }
            this.superStack.Push(element);
        }

        public T Min()
        {
            if (this.superStack.Count <= 0)
                throw new InvalidOperationException("Stack Empty.");

            return this.stackWithMin.Peek();
        }
    }

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;
        }
    }