В этой статье обсуждается структура данных очереди в информатике: что такое структура данных очереди, основные операции очереди, пример реализации очереди на основе срезов.

Определение очереди как абстрактного типа данных

В информатике очередь - это абстрактный тип данных, который обслуживает линейный набор элементов. Элемент может быть вставлен только в конец сзади и удален с другого конца спереди в соответствии с принципом FIFO (first-in, first-out).

Аналогия, которая поможет вам понять принцип очереди, - представить очередь как очередь людей, ожидающих обслуживания. Новичок идет в конец очереди, а человек, который вначале обслуживается.

Базовым типом данных для очереди может быть массив или связанный список.

Объявление типа очереди

Как и стек, мы объявляем очередь как структуру с полями items и mutex.

Операции

Для очереди есть две основные операции: Enqueue () и Dequeue ().

queue.Enqueue (элемент Item)

Вставляет элемент в конец (задний) очереди .

Для вставки нового элемента в очередь мы используем встроенную функцию append (), которая вставляет новый элемент в конец среза.

Элемент queue.Dequeue ()

Удаляет последний элемент с начала (перед) очереди и возвращает удаленный элемент.

Поскольку функция Dequeue () возвращает удаленный элемент, перед повторной нарезкой мы инициализируем переменную lastItem и сохраняем удаленный элемент внутри переменной:

lastItem := queue.items[0]

Затем мы повторно разрезаем очередь с помощью следующего оператора:

queue.items = queue.items[1:]

В результате мы получаем все элементы от второго (первого индекса) до последнего из очереди. Первый элемент в очереди имеет нулевой индекс.

Кроме того, применение этого метода к пустой очереди должно возвращать nil. Таким образом, перед удалением элемента нам необходимо проверить длину очереди. В следующем примере метод возвращает nil, если длина очереди равна нулю:

main ()

Создайте новый экземпляр очереди в файле main.go. Добавляйте новые элементы с помощью метода Enqueue (). В приведенном ниже примере мы создали очередь, состоящую из нескольких элементов:

5←4←3←2←1

Чтобы увидеть полную очередь, используйте Dump ().

Последний элемент (перед) в этой очереди - 5, а первый (задний) - 1.

Чтобы очистить очередь, используйте Reset ().

Чтобы узнать, пуста ли очередь, используйте IsEmpty (). True, если очередь пуста, и false, если очередь не пуста.

Методы Dump (), Reset (), Peek () и IsEmpty () в этой статье опускаются, так как они уже обсуждались здесь.

Джейн - программист на Go и технический писатель в области разработки программного обеспечения. В течение 5 лет она писала технические материалы на английском и русском языках. Она закончила Новосибирский государственный технический университет по специальности Информационная безопасность по специальности Информационная безопасность автоматизированных систем. Вы можете подписаться на нее в Твиттере и увидеть другие ее письменные работы на publishing.enthusiastic.io.