Реализация очереди при помощи массива на языке C#

26.10.2017

Совсем недавно я рассказывал про базовую структуру данных очередь. И, как обещал, от теории переходим к практике. Сегодня хочу показать как реализовать алгоритм очереди нативными средствами языка C#.

Замечу, что собственная реализация подобных базовых структур, как правило, избыточный овер инжиниринг и не нужный велосипед. Всё уже давно реализовано, наверное, для всех платформ и на всех языках программирования. Конечно, .NET C# не исключение. В пространстве имён System.Collections.Generic есть класс Queue<T>, который отвечает за данный функционал. Но цель данной статьи показать как раз таки нативную и простую реализацию алгоритма. Такой подход к организации очереди — самая простая и служит скорее для демонстрации, чем для использования в реальных проектах. Это базис, служащий исключительно для понимания основных принципов очереди.

Итак, давайте создадим класс и назовём его QueueSimple. Объявим внутри локальные целочисленные переменные _Size — размер массива, _Front — позиция головы (инициализируем со значением по-умолчанию -1), _Rear — позиция хвоста (также -1), _Count — кол-во элементов. Также локальный массив типа T.

Создадим конструктор, в котором определим размер очереди и создадим массив нужной длины:

Согласно алгоритму, описанному в предыдущей статье, нам для работы понадобится два метода: IsFull, проверяющий заполнена ли очередь (условие, когда значение _Rear подобралось к размеру всего массива) и IsEmpty, возвращающий true если очередь пуста:

Непосредственно переходим к методу добавления элементов в очередь: Enqueue. Мы проверяем заполнен ли полностью массив и если да — выбрасываем ошибку. В случае, когда есть ещё место — мы устанавливаем наш новый элемент в позицию _Rear+1 и инкрементим на единицу переменную _Rear:

Следующий метод Dequeue — проверяет не пустая ли очередь и если нет, то считывает элемент: возвращает его нам и удаляет из очереди. В случае, когда _Rear и _Front равны — это означает, что из очереди были вычитаны все элементы и мы заново присваиваем этим двум переменным значение -1.

В целом, описанное выше уже полностью удовлетворяет алгоритму: можно добавлять элементы, можно считывать. Всё, что пойдёт ниже — это больше удобства и расширение базового функционала. К примеру, мы можем инкапсулировать некоторые локальные переменные в открытые public свойства:

Метод Peek служит для считывания верхнего элемента, но без его удаления. В целом, он очень похож на Dequeue с небольшими изменениями:

И, конечно, было бы неплохо добавить GetEnumerator для того, чтобы иметь возможность получать данные при помощи foreach. Для этого необходимо нашему классу реализовать интерфейс IEnumerable<T> и добавить следующий код:

Теперь можно написать несколько примеров использования. Допустим вы приоритизировали свои утренние дела следующим образом: «Встать с кровати«, «Почистить зубы«, «Позавтракать» и «Пойти на работу«. Для этого мы пишем следующий код:

Мы добавляем в очередь наши задачи в том порядке, в каком они должны быть выполнены. Две из них «исполняем» сразу, т.е. вычитываем и в очереди остаётся последние 2 задачи. В конце работы консольного приложения выводим счётчик оставшихся задач и ждём реакцию пользователя:

Результат работы программы - Очередь

Вот и всё. В подобной имплементации есть, конечно, минусы. К примеру, нет возможности вмещать в очередь больше элементов, чем было изначально проинциализировано через конструктор. Но цель была показать самый простой способ реализации алгоритма. Если вас интересует более серьёзный подход, то можете ознакомиться с классом Queue<T> в репозитории dotnet/corefx.

P.S. По-хорошему, конечно, нужны тесты, но это лишь ознакомительный проект и покрывать его тестированием, а тем более описывать их здесь — считаю лишним. Ну или пусть это будет вашим домашним заданием 🙂

Leave a comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Prev Post Next Post