Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица - Класс System.Collections.Queue

Класс System.Collections.Queue

Функциональность, которую мы только что описали - добавление и удаление элементов из буфера в порядке FCFS при максимальной оптимизации используемого объема памяти - предоставляется стандартной структурой данных - Очередью. Библиотека классов .NET Framework Base содержит встроенный класс System.Collections.Queue. Аналогично тому, как мы использовали выше в написанном нами коде методы AddJob() и GetNextJob(), класс Queue cпредоставляет соответствующую функциональность в виде методов Enqueue() и Dequeue() соответственно.

За кулисами, класс Queue использует внутренний циклический массив элементов типа object и две переменные, служащих в качестве маркеров начала и конца циклического массива: head (голова) и tail (хвост). По умолчанию начальный размер очереди равен 32 элементам, хотя эту величину можно настроить при вызове конструктора очереди. Поскольку очередь для хранения данных использует массив object-ов, в ней можно хранить переменные любых типов.

Метод Enqueue() определяет, достаточно ли места для добавления нового элемента в очередь. Если да, то элемент просто записывается в ячейку массива с индексом tail, после чего значение tail "инкрементируется" (т.е. увеличивается на единицу и от результата берется остаток от деления его на длину массива). Елси места недостаточно, размер массива увеличивается в n раз. Число n называется growth factor - фактор роста. По умолчанию его значение равно 2.0, а значит, по умолчанию размер массива удваивается. Отметим, что фактор роста вы также можете задавать в конструкторе класса Queue.

Метод Dequeue() возвращает элемент, который находится в ячейке массива с индексом head. После этого он присваивает элементу head значение null и "инкрементирует" head. Для тех случаев, когда вы желаете лишь прочесть значение элемента из головы очереди, но приэтом не удалять его оттуда, класс Queue предлагает метод Peek().

Важно понимать то, что при работе с очередью, в отличие от ArrayList-а, вы не имеете доступа к ее произвольному элементу. Например, вы не можете посмотреть третий элемент очереди, не удалив из нее первые 2 элемента. (Отметим, однако, что класс Queue имеет метод Contains(), используя который вы можете определить, содержит ли очередь тот или иной конкретный элемент). Если вы точно уверены, что вам необходим произвольный доступ (random access), то структура данных "очередь" не для вас - используйте лучше ArrayList. Безусловно, очередь является идеальным выбором в ситуациях, когда вам необходимо выполнять обработку элементов данных точно в порядке их поступления.

Примечание Очереди также часто называют структурами данных типа FIFO - First In, First Out. Смысл этой аббревиатуры аналогичен FCFS и по-русски звучит примерно, как "первым вошел, первым вышел".