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

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

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

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

public class Queue<T>
{
	private int _Front = -1;
	private int _Rear = -1;
	private int _Count = 0;
	private readonly int _Size;
	private readonly T[] _Array;
}

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

public Queue(int Size)
{
	this._Size = Size;
	this._Array = new T[Size];
}

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

public bool IsFull()
{
	return _Rear == _Size - 1;
}

public bool IsEmpty()
{
	return _Count == 0;
}

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

public void Enqueue(T Item)
{
	if (this.IsFull())
		throw new Exception("Очередь полностью заполнена.");

	_Array[++_Rear] = Item;
	_Count++;
}

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

public T Dequeue()
{
	if (this.IsEmpty())
		throw new Exception("Очередь не заполнена.");

	T value = _Array[++_Front];
	_Count--;
	if(_Front == _Rear)
	{
		_Front = -1;
		_Rear = -1;
	}
	return value;
}

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

public int Size
{
	get { return _Size; }
}

public int Count
{
	get { return _Count; }
}

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

public T Peek()
{
	if (this.IsEmpty())
		throw new Exception("Очередь не заполнена.");

	T value = _Array[_Front + 1];
	return value;
}

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

public IEnumerator GetEnumerator()
{
	if (this.IsEmpty())
		throw new Exception("Очередь не заполнена.");

	for (int i = _Front + 1; i <= _Rear; i++)
		yield return _Array[i];
}

IEnumerator IEnumerable.GetEnumerator()
{
	return this.GetEnumerator();
}

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

class Program
{
	static void Main(string[] args)
	{
		Queue<string> q = new Queue<string>(5);
		q.Enqueue("Встать с кровати");
		q.Enqueue("Почистить зубы");
		q.Enqueue("Позавтракать");
		q.Enqueue("Пойти на работу");
		Console.WriteLine("Сделано: " + q.Dequeue());
		Console.WriteLine("Сделано: " + q.Dequeue());
		foreach (string c in q)
		{
			Console.WriteLine("Осталось: " + c);
		}
		Console.WriteLine("Всего осталось: " + q.Count.ToString());
		Console.Read();
	}
}

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

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

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