// Implement stack of integers of fixed maximum size 

// that is able to publish the maximum of its elements spending O(1)

using System;

​

public class Program

{   

    public static void Main(string[] args)

    {

        StackWithMax s = new StackWithMax(5); 

        TestPush(s, 5);

        TestPush(s, -3);

        TestPush(s, 13);

        TestPush(s, -8);

        TestPop(s);

        TestPop(s);

        TestPop(s);

    }

    private static void TestPush(StackWithMax s, int v)

    {

        Console.WriteLine("Push({0})", v);

        s.Push(v);

        Console.WriteLine("    Max = {0}", s.MaxValue());

    }

​

    private static void TestPop(StackWithMax s)

    {

        Console.WriteLine("Pop->{0}", s.Pop());

        Console.WriteLine("    Max = {0}", s.MaxValue());

    }

}

​

public class StackWithMax

{

    // two stacks have the same size 

    // each element in stack of maximums keeps the maximum of

    // all elements in stack of numbers with the same or bigger depth

    Stack numbers;

    Stack maximums;

    public StackWithMax(int size)

    {

        numbers = new Stack(size);

        maximums = new Stack(size);

    }

    public void Push(int number) 

    {

        numbers.Push(number);

        maximums.Push(maximums.IsEmpty() ? number : Math.Max(number, maximums.Top()));

    }

    public int Pop()

    {

        maximums.Pop();

        return numbers.Pop();

    }

    public int MaxValue() 

    {

        return maximums.Top();

    }

​

    public bool IsEmpty()

    {

        return numbers.IsEmpty();

    }

​

    public int Top()

    {

        return numbers.Top();

    }

}

​

public class Stack

{

    // stack occupies first count1 elements of array with the bottom at data[0]

    int count;

    int[] data;

    public Stack(int size)

    {

        data = new int[size];

        count = 0;

    }

    public void Push(int v)

    {

        if (count >= data.Length)

           throw new ApplicationException("Stack overflow");

​

        data[count] = v;

        count++;

    }

    public int Pop()

    {

        if (count <= 0)

           throw new ApplicationException("Stack underflow");

​

        count--;

        return data[count];

    }

    public int Top()

    {

        if (count <= 0)

           throw new ApplicationException("Stack underflow");

​

        return data[count-1];

    }

    public bool IsEmpty()

    {

        return count==0;

    }

}

​

​