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

Метод EnqueueLast

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

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

// Теперь, когда у нас есть подходящий массив,

// если _tail в конце массива, нам надо перейти в начало.
if (_tail == _items.Length - 1)
{
_tail = 0;
}
else
{
_tail++;
}

_items[_tail] = item;

_size++;

if (_size == 1)

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

• 
  Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
  
• 
  Сложность: O(1).
  

public T DequeueFirst()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}

T value = _items[_head];

if (_head == _items.Length - 1)

{
// Если head установлен на последнем индексе,
// переходим к началу массива.
_head = 0;
}
else
{
// Переходим к следующему элементу.
_head++;
}

_size--;

return value;
}
Метод DequeueLast

• 
  Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
  
• 
  Сложность: O(1).
  

public T DequeueLast()
{
if (_size == 0)
{
throw new InvalidOperationException("The deque is empty");
}

T value = _items[_tail];

if (_tail == 0)

{
// Если tail установлен на начало массива, переходим к концу.
_tail = _items.Length - 1;
}
else
{
// Переходим к предыдущему элементу.
_tail--;
}

_size--;

return value;
}