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

Метод Count

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

public int Count
{
get
{
return _items.Count;
}
}
Пример: реализация стека
Двусторонняя очередь часто используется для реализации других структур данных. Давайте посмотрим на пример реализации стека с ее помощью.
У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.
Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.
Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:
public class Stack
{
Deque _items = new Deque();

public void Push(T value)

{
_items.EnqueueFirst(value);
}

public T Pop()

{
return _items.DequeueFirst();
}

public T Peek()

{
return _items.PeekFirst();
}

public int Count

{
get
{
return _items.Count;
}
}
}
Заметьте, что вся обработка ошибок теперь лежит на классе Deque, и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.