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