Очередь (queue) — это структура данных, представляющая собой специализированным образом организованный список элементов. Доступ к элементам стека осуществляется по принципу FIFO (First In First Out) — первым пришел, первым вышел. Принцип работы данной структуры данных схож с обычной живой очередью в больнице. Кто раньше пришел, тот раньше зайдет на прием. Все новые пациенты выстраиваются в конец очереди по мере поступления. Давайте рассмотрим пример реализации очереди на языке C#.

На рисунке ниже представлена схематическая структура очереди.

Queue

Queue

Произвольный доступ к элементам очереди, как и у стека, не возможен. Новые элементы всегда добавляются в конец очереди. Элемент в начале очереди можно либо получить с удалением, либо прочитать без удаления. Соответственно существуют три основные операции:

  • Enqueue — добавлений
  • Dequeue — получение с удалением
  • Peek — чтение без удаления

Теперь приступим к реализации данного класса. Мы будем использовать обобщенный класс. Для хранения данных воспользуемся списком. Данная реализация является весьма примитивной, но позволяет разобраться со структурой и алгоритмом работы данного типа данных.

Очередь

Вызов

Заключение

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Queue. Исходный код доступен в репозитории github https://github.com/shwanoff/Queue.

 
×
%d такие блоггеры, как: