Очередь

Последнее обновление: 02.09.2016

Очередь (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).

Очередь в C#

Применение очереди:

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
Помощь сайту
Юмани:
410011174743222
Перевод на карту
Номер карты:
4048415020898850