Theory and Tasks for Students - Spring 2019
Queue

Queue (очередь) - структура данных, также называемая FIFO - First In, First Out, то есть элементы добавляются в конец очереди и извлекаются из начала. У очереди обычно имеется три метода:

  • void Enqueue(item) добавляет в конец один элемент,
  • type Dequeue() удаляет из начала один элемент и возвращает его значение,
  • type Front() возвращает значение переднего элемента, не производя изменений.

Классическая реализация очереди чисел: class Queue { private int[] _items; private int _right = -1; private int _count = 0; public bool IsEmpty { get { return _count == 0; } } public int Capacity { get { return _items.Length; } } public Queue() : this(512) { } public Queue(int capacity) { _items = new int[capacity]; } public void Enqueue(int item) { if (_count >= Capacity) { throw new OverflowException(String.Format("Queue size exceeded maximum capacity of {0} elements.", Capacity)); } _right = (_right + 1) % Capacity; // деление по модулю "зацикливает" очередь _count++; _items[_right] = item; } public int Dequeue() { if (_count == 0) { throw new OverflowException(String.Format("Can't remove elements from an empty Queue")); } int res = _items[(_right - _count + 1 + Capacity) % Capacity]; _count--; return res; } public int Front() { if (_count == 0) { throw new OverflowException(String.Format("No front element in an empty Queue")); } return _items[(_right - _count + 1 + Capacity) % Capacity]; } }