class SafeStackItem<T> {
    public T Value;
    public Int32 Next;
  }

  class SafeStack<T> where T : class {
    private Int32 head;
    private Int32 count;
    private SafeStackItem<T>[] array;

    public SafeStack(SafeStackItem<T>[] array, int pushFrom, int pushCount) {
      this.head = -1;
      this.array = array;

      count = pushCount;

      head = pushFrom;
      for (int i = 0; i < pushCount - 1; i++)
        array[i + pushFrom].Next = pushFrom + i + 1;
      array[pushFrom + pushCount - 1].Next = -1;
    }

    public Int32 Pop() {
      while (count > 1) {
        Int32 oldHead = head;
        Int32 oldHeadNext = Interlocked.Exchange(ref array[oldHead].Next, -1);

        if (oldHeadNext >= 0) {
          if (Interlocked.CompareExchange(ref head, oldHeadNext, oldHead) == oldHead) {
            Interlocked.Decrement(ref count);
            return oldHead;
          }
          else

            Interlocked.Exchange(ref array[oldHead].Next, oldHeadNext);
        }
      }

      return -1;
    }

    public void Push(Int32 index) {
      Int32 oldHead;
      do {
        oldHead = head;
        array[index].Next = oldHead;
      } while (oldHead != Interlocked.CompareExchange(ref head, index, oldHead));

      Interlocked.Increment(ref count);
    }
  }