Очереди Queue<T>

Очередь Queue<T> представляет собой динамическую типизированную коллекцию, в которой элементы обслуживаются по принципу “первым пришел, первым вышел” (FIFO). Это значит, что сколько бы мы ни добавляли элементов в очередь, первым будет обслужен тот, который раньше всех добавлен в очередь, а новые элементы будут помещаться в конец очереди.

Порядок обслуживания элементов очереди
Порядок обслуживания элементов очереди

Параметр T представляет собой тип элементов, которые будут храниться в очереди.


Создание очереди

Класс Queue<T>, представляющий в C# функциональность очередей, может создаваться при помощи следующих конструкторов:

Queue<T>()Создает новый объект класса Queue<T> с емкостью по умолчанию
Queue<T>( IEnumerable<T> enumerable )Создает новый объект класса Queue<T> и заполняет ее элементами из enumerable
Queue<T>( Int32 capacity )Создает новый объект класса Queue<T> с емкостью равной capacity

Методы для работы с очередью

Класс Queue<T> имеет следующие основные методы для работы с очередью:

Enqueue(T)Добавляет новый элемент в конец очереди.
Dequeue()Удаляет элемент, который находится в начале очереди, при этом возвращает элемент, удаленный из очереди элемент.
Clear()Удаляет из очереди все элементы, при этом емкость очереди не изменяется.
Peek()Возвращает элемент, который находится в начале очереди, при этом сам элемент не удаляется из очереди.
TrimExcess()Устанавливает емкость очереди равной количеству элементов очереди, но только в том случае, если количество элементов очереди занимает менее 90 процентов емкости.
Contains(T)Определяет, содержит ли очередь элемент, переданный в качестве аргумента.

В следующем примере показано использование методов для добавления элементов в очередь и удаления их из нее:

public class Program {
    static void Main( string[] args ) {
        Queue<string> queue = new Queue<string>();

        // Добавление элементов в очередь
        queue.Enqueue( "One" );
        queue.Enqueue( "Two" );

        // Получение количества элементов очереди
        Console.WriteLine( "Число элементов в очереди: " 
            + queue.Count );
        Console.WriteLine();

        // Просмотр элементов очереди
        foreach( var item in queue )
            Console.WriteLine( item );

        Console.WriteLine();

        // Удаление одного элемента очереди
        Console.WriteLine( "Удаляем элемент из очереди: " 
            + queue.Dequeue() );
        Console.WriteLine();

        // Просмотр элементов очереди
        foreach ( var item in queue )
            Console.WriteLine( item );

        Console.ReadKey();
    }
}

Вывод программы:

Вывод программы
Вывод программы

Перечисление элементов очереди

В предыдущем примере был показан способ перечисления элементов очереди внутри оператора foreach:

Queue<string> queue = new Queue<string>();
queue.Enqueue( "One" );
queue.Enqueue( "Two" );

foreach ( var item in queue ) // Перечисление элементов очереди
    Console.WriteLine( item );

Такое перечисление элементов коллекции возможно благодаря тому, что очереди в C# реализуют интерфейс IEnumerable<T>.


Под капотом у очереди

В основе очереди лежит обычный одномерный массив. Размер этого массива определяет емкость очереди. Емкость очереди по умолчанию равна 4 элементам. Если количество добавляемых элементов превышает это число, емкость очереди автоматически увеличивается. Для этого создается новый массив большего размера, а элементы старого массива копируются в новый. Этот момент можно проследить по следующему коду из исходников .net Framework:

private const int _MinimumGrow = 4; // минимальный прирост емкости
private const int _GrowFactor = 200; // double each time
private const int _DefaultCapacity = 4; // емкость по умолчанию

public void Enqueue(T item) {
    if (_size == _array.Length) {
        int newcapacity = 
            (int)((long)_array.Length * (long)_GrowFactor / 100);
        if (newcapacity < _array.Length + _MinimumGrow) {
            newcapacity = _array.Length + _MinimumGrow;
        }
        SetCapacity(newcapacity); // установка новой емкости
    }
}
avatar
5000
  Подписаться  
Уведомление о