Очередь (Queue). C# Реализация на массиве.

Очередь - динамическая структура данных, которая работает по принципу "Первым вошел - первым вышел". По английски FIFO (first-in, first-out). 

Графическое представление очереди:

Видно, что у нас здесь 2 переменные back, front, которые являются указателями на конец и соответственно начало очереди. С помощью метода Dequeue мы можем вытаскивать элемент с начала очереди. С помощью метода Enqueue  - добавлять в конец.

Жизненный пример очереди - очередь в больнице. Когда подходим в очередь, то встаем в конец.(Enqueue) Первые элементы входят в кабинет.(Dequeue)

Или еще один пример, пуля в автомате. Та пуля, которая находится сверху вылетает быстрее других. Несколько пуль не могут вылететь одновременно. Пример не работает в случае футуристических автоматов :D

Применение стека:

• Во многих алгоритмах, как например, поиск в ширину, алгоритм Дейкстры и так далее.
• В программах, где можно поставить приоритет операциям и потом проводить эти операции в зависимости от их приоритета, например, отправка сообщений в ICQ.
• События в системе Windows - если юзер выполнит какое-то действие в приложении, сначала не вызывается другая процедура, сначала приложению присылается сообщение, это сообщение ставится в очередь и когда все сообщения будут обработаны, то только тогда вызовется следующая процедура.

Реализация выполнена на массиве, с некоторыми хитростями.

UML Диаграмма:

Действующие лица:

1. _array - массив, где хранятся наши элементы очереди.
2. capacity - количество элементов под которые выделено памяти, запомните, что не всегда size==capacity
3. defaultCapacity - количество элементов под которые выделено памяти в момент создания объекта Очередь.
4. head - переменная которая указывает на головной элемент.
5. tail - переменная которая указывает на задний элемент.
6. size - количество элементов в очереди.
7. Count - свойство для вывода size.

Реализация:

public class CQueue
    {
        private T[] _array;
        private int size;
        private const int defaultCapacity = 10;
        private int capacity;
        private int head;
        private int tail;

        public CQueue()
        {
            capacity = defaultCapacity;
            this._array = new T[defaultCapacity];
            this.size = 0;
            this.head = -1;
            this.tail = 0;
        }

        public bool isEmpty() //проверка на пустоту
        {
            return size == 0;
        }

        public void Enqueue(T newElement)
        {
            if (this.size == this.capacity)
            {
                T[] newQueue = new T[2 * capacity];
                Array.Copy(_array, 0, newQueue,0, _array.Length);
                _array = newQueue;
                capacity *= 2;
            }
            size++;
            _array[tail++%capacity] = newElement;
        }

        public T Dequeue()
        {
            if (this.size == 0)
            {
                throw new InvalidOperationException();
            }
            size--;
            return _array[++head%capacity];
        }


        public int Count
        {
            get
            {
                return this.size;
            }
        }
    }

Posted in: Алгоритмы, Структуры данных, C#