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

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

Queue

Queue

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

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

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

Очередь

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Queue
{
    /// <summary>
    /// Очередь.
    /// </summary>
    /// <typeparam name="T"> Тип данных, хранимых в очереди. </typeparam>
    public class Queue<T>
    {
        /// <summary>
        /// Коллекция хранимых данных.
        /// </summary>
        private List<T> _items = new List<T>();
 
        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count => _items.Count;
 
        /// <summary>
        /// Добавить элемент в очередь.
        /// </summary>
        /// <param name="item"> Добавляемые данные. </param>
        public void Enqueue(T item)
        {
            // Проверяем входные данные на пустоту.
            if(item == null)
            {
                throw new ArgumentNullException(nameof(item));
            }
 
            // Добавляем данные в коллекцию элементов.
            _items.Add(item);
        }
 
        /// <summary>
        /// Получить элемент из очереди с удалением.
        /// </summary>
        /// <returns> Элемент данных. </returns>
        public T Dequeue()
        {
            // Получить элемент из начала очереди.
            var item = GetItem();
 
            // Удаляем элемент из коллекции.
            _items.Remove(item);
 
            // Возвращаем полученный элемент.
            return item;
        }
 
        /// <summary>
        /// Прочитать элемент из очереди без удаления.
        /// </summary>
        /// <returns> Элемент данных. </returns>
        public T Peek()
        {
            // Получаем элемент из начала очереди.
            var item = GetItem();
 
            // Возвращаем полученных элемент.
            return item;
        }
 
        /// <summary>
        /// Получить элемент из начала очереди.
        /// </summary>
        /// <returns> Начальный элемент очереди. </returns>
        private T GetItem()
        {
            // Получаем первый элемент.
            var item = _items.FirstOrDefault();
 
            // Если элемент пуст, то сообщаем об ошибке.
            if (item == null)
            {
                throw new NullReferenceException("Очередь пуста. Нет элементов для получения.");
            }
 
            return item;
        }
    }
}

Вызов

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Queue
{
    class Program
    {
        static void Main(string[] args)
        {
            // Создаем новую очередь.
            var queue = new Queue<int>();
 
            // Добавляем новые элементы в очередь.
            queue.Enqueue(1);
            queue.Enqueue(7);
            queue.Enqueue(42);
            queue.Enqueue(69);
            queue.Enqueue(-17);
            Console.WriteLine($"Очередь содержит {queue.Count} элементов.");
 
            // Получаем элементы с удалением.
            var item1 = queue.Dequeue();
            Console.WriteLine($"Первый элемент из очереди {item1}.");
            var item2 = queue.Dequeue();
            Console.WriteLine($"Второй элемент из очереди {item2}.");
 
            // Добавляем новый элемент в очередь.
            queue.Enqueue(88);
 
            // Просматриваем элемент без удаления.
            var item3 = queue.Peek();
            Console.WriteLine($"Обзор элемента без удаления {item3}.");
 
            Console.ReadLine();
        }
    }
}

Заключение

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

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