В этой статье обсуждается структура данных очереди в информатике: что такое структура данных очереди, основные операции очереди, пример реализации очереди на основе срезов.
Определение очереди как абстрактного типа данных
В информатике очередь - это абстрактный тип данных, который обслуживает линейный набор элементов. Элемент может быть вставлен только в конец сзади и удален с другого конца спереди в соответствии с принципом 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.