Абстрактный тип данных “очередь”¶

Абстрактный тип данных для очереди определяется следующими структурой и операциями. Как описывалось выше, очередь структурирована как упорядоченная коллекция элементов, которые добавляются с одного конца, называемого “хвост”, и удаляются с другого, называемого “голова”. Очередь поддерживает свойство упорядочения FIFO. Операции для очереди представлены ниже.

• Queue() создаёт новую пустую очередь. Не нуждается в параметрах, возвращает пустую очередь.
• enqueue(item) добавляет новый элемент в конец очереди. Требует элемент в качестве параметра, ничего не возвращает.
• dequeue() удаляет передний элемент из очереди. Не нуждается в параметрах, возвращает элемент. Очередь изменяется.
• isEmpty() проверяет очередь на пустоту. Не нуждается в параметрах, возвращает булево значение.
• size() возвращает количество элементов в очереди (целое число). Не нуждается в параметрах.

Как пример, если мы предположим, что q - это очередь, которая создана и пока пуста, то Таблица 1 показывает результаты последовательности операций над нею. Содержимое очереди показано таким образом, что голова находится справа. 4 была первым элементом, ожидающим обработки, поэтому она будет первым элементом, убираемым из очереди.