Алгоритмы и структуры данных для начинающих: стеки и очереди

Алгоритм роста
Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).
Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».
private void allocateNewArray(int startingIndex)
{
int newLength = (_size == 0) ? 4 : _size * 2;

T[] newArray = new T[newLength];

if (_size > 0)

{
int targetIndex = startingIndex;

// Копируем содержимое...

// Если массив не закольцован, просто копируем элементы.
// В противном случае, копирует от head до конца,
// а затем от начала массива до tail.

// Если tail меньше, чем head, переходим в начало.

if (_tail < _head)
{
// Копируем _items[head].._items[end] в newArray[0]..newArray[N].
for (int index = _head; index < _items.Length; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}

// Копируем _items[0].._items[tail] в newArray[N+1]..

for (int index = 0; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
else
{
// Копируем _items[head].._items[tail] в newArray[0]..newArray[N]
for (int index = _head; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
_head = startingIndex;
_tail = targetIndex - 1;
}
else
{
// Массив пуст.
_head = 0;
_tail = -1;
}

_items = newArray;

}
Метод EnqueueFirst

• 
  Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst.
  
• 
  Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.
  

public void EnqueueFirst(T item)
{
// Проверим, необходимо ли увеличение массива:
if (_items.Length == _size)
{
allocateNewArray(1);
}

// Так как массив не заполнен и _head больше 0,

// мы знаем, что есть место в начале массива.
if (_head > 0)
{
_head--;
}
else
{
// В противном случае мы должны закольцеваться.
_head = _items.Length - 1;
}

_items[_head] = item;

_size++;

if (_size == 1)

{
// Если мы добавили первый элемент в пустую
// очередь, он же будет и последним, поэтому
// нужно обновить и _tail.
_tail = _head;
}
}