Очередь (queue) - это структура данных, которая работает по принципу FIFO (First In First Out - Первый пришел, первый вышел). При добавлении новый элемент помещается в конец очереди или ее хвост, а удаление идет с начала очереди или головы очереди.
Банальным примером очереди может служить обычная очередь в больнице, где новые пациенты встают в конец очереди, а прием пациентов осуществляется с начала очереди.
Для реализации очереди мы опять же будем использовать класс элемента, который содержит сами данные и ссылку на следующий элемент:
public class Node<T> { public Node(T data) { Data = data; } public T Data { get; set; } public Node<T> Next { get; set; } }
Сам класс очереди будет выглядеть следующим образом:
using System; using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp { public class Queue<T> : IEnumerable<T> { Node<T> head; // головной/первый элемент Node<T> tail; // последний/хвостовой элемент int count; // добавление в очередь public void Enqueue(T data) { Node<T> node = new Node<T>(data); Node<T> tempNode = tail; tail = node; if (count == 0) head = tail; else tempNode.Next = tail; count++; } // удаление из очереди public T Dequeue() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; head = head.Next; count--; return output; } // получаем первый элемент public T First { get { if (IsEmpty) throw new InvalidOperationException(); return head.Data; } } // получаем последний элемент public T Last { get { if (IsEmpty) throw new InvalidOperationException(); return tail.Data; } } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { Node<T> current = head; while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { Node<T> current = head; while (current != null) { yield return current.Data; current = current.Next; } } } }
Для добавления в очередь нам надо переустановить ссылку на последний элемент tail:
public void Enqueue(T data) { Node<T> node = new Node<T>(data); Node<T> tempNode = tail; tail = node; if (count == 0) head = tail; else tempNode.Next = tail; count++; }
При удалении надо переустановить ссылку на первый элемент. Так как первый элемент удаляется, то новым первым элементом становится следующий за ним:
public T Dequeue() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; head = head.Next; count--; return output; }
Сложность алгоритмов добавления и удаления из очереди составляет O(1).
Применение очереди:
Queue<string> queue = new Queue<string>(); queue.Enqueue("Kate"); queue.Enqueue("Sam"); queue.Enqueue("Alice"); queue.Enqueue("Tom"); foreach (string item in queue) Console.WriteLine(item); Console.WriteLine(); Console.WriteLine(); string firstItem = queue.Dequeue(); Console.WriteLine($"Извлеченный элемент: {firstItem}"); Console.WriteLine(); foreach (string item in queue) Console.WriteLine(item);
Консольный вывод:
Kate Sam Alice Tom Извлеченный элемент: Kate Sam Alice Tom