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

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

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

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