// Implement K stacks of integers that can contain not more than N elements in total.

// The memory used should not exceed C1*K + C2*N. Each method (except constructor)

// should take fixed time (not dependent on K or N) and should not allocate new memory.

using System;

​

public class Stacks

{

    private int[] content;  // contains N elements

    private int[] next;     // links between elements used either for stacks or free space

                            // there is an arrow from i to j if Next[i]=j or 0 if there are none from i 

    private int nextFree;   // points to free space stack (-1 means no free space)

​

    private int[] top;      // of size K. points to the top of correspondent stack

    public Stacks(int K, int N)

    {

        content = new int[N];

        next = new int[N];

        for(int i=0; i < next.Length; i++)

            next[i] = i+1;

        next[next.Length-1] = -1;

        nextFree = 0;

        top = new int[K];

        for (int i = 0; i < top.Length; ++i) 

        {

            top[i] = -1;

        }

    }

​

    public void Push(int stackIndex, int element)

    {

        if(nextFree < 0)

            throw new ApplicationException("Container is full");

        int i = nextFree;

        nextFree = next[i];

        next[i] = top[stackIndex];

        top[stackIndex] = i;

        content[i] = element;

    }

    public int Pop(int stackIndex)

    {

        int stackTop = top[stackIndex];

        if(stackTop < 0)

            throw new ApplicationException(string.Format("Stack{0} underflow", stackIndex));

​

        int v = content[stackTop];

        top[stackIndex] = next[stackTop];

        next[stackTop] = nextFree;

        nextFree = stackTop;

        return v;

    }

​

    public bool IsEmpty(int stackIndex)

    {

        return top[stackIndex] == -1;

    }

}

​

public class Program 

{   

    public static void Main()

    {

        Stacks s = new Stacks(3, 15);

        TestPush(s, 0,2);

        TestPush(s, 0,-5);

        TestPush(s, 0,11);

        TestPush(s, 0,-7);

        TestPush(s, 0,13);

        TestPush(s, 1,-41);

        TestPush(s, 0,-17);

        TestPush(s, 1,52);

        TestPush(s, 0,-13);

        TestPush(s, 1,6);

        TestPush(s, 2,35);

        TestPush(s, 1,-8);

        TestPush(s, 1,15);

        TestPush(s, 1,-2);

        TestPush(s, 2,23);

        TestPop(s, 0);

        TestPop(s, 1);

        TestPop(s, 2);

        TestPop(s, 2);

        TestPop(s, 1);

        TestPop(s, 0);

    }

    private static void TestPush(Stacks s, int index, int v)

    {

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

        s.Push(index, v);

    }

​

    private static void TestPop(Stacks s, int index)

    {

        int v = s.Pop(index);

        Console.WriteLine("Pop{0} -> {1}", index, v);

    }

}