Я считаю, что лучший способ дополнить мою последнюю статью о стеках - это статья об очередях. Об очередях и стеках часто говорят вместе, потому что они похожи, хотя их использование и реализация различны. Я рассмотрю базовую концепцию очередей и, как и другие мои статьи, рассмотрю проблему LeetCode, чтобы показать, как они используются. Задача LeetCode: Количество студентов, не умеющих обедать. Вопрос звучит мрачно, но показать, как пользоваться очередями, - хорошая проблема.

Что такое очередь?

Как и стек, очередь - это линейный абстрактный тип данных, который может содержать длинный список элементов. Очереди же устроены совершенно по-другому. Очередь - это структура данных в порядке очереди (FIFO). Элементы могут быть удалены только в начале очереди, а элементы могут быть вставлены только в конец очереди. Это важное отличие от стека, который является структурой данных «последний пришел - первый вышел» (LIFO).

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

Операции

Еще одна причина, по которой очереди и стеки связаны вместе, заключается в том, что они имеют схожие функции. Мы можем добавить или удалить элемент. Операция добавления элемента в конец очереди - это функция enqueue(). Что действует очень похоже на метод push(). Операция удаления элемента из начала очереди - это функция dequeue(). Что действует очень похоже на метод shift().

Большой O

Сложность по времени как для вставки, так и для удаления элемента занимает время O (1), постоянное время.

Поиск и доступ к элементу занимает O (n) времени, линейное время.

Выполнение

Как и стеки, очереди могут быть реализованы с использованием связанных списков или массивов. Ресурсы, представленные в конце, подробно описывают, как записывать очереди в массивы и связанные списки. В проблеме LeetCode, которую я рассмотрел, мы используем реализацию массива.

Количество студентов, не умеющих обедать

Маршруты:

Школьный кафетерий предлагает круглые и квадратные бутерброды во время обеденного перерыва, обозначенные цифрами 0 и 1 соответственно. Все студенты выстраиваются в очередь. Каждый студент предпочитает бутерброды квадратной или круглой формы.

Количество бутербродов в кафетерии равно количеству студентов. Бутерброды складываются стопкой. На каждом этапе:

  • Если учащийся, стоящий в начале очереди, предпочитает бутерброд на вершине стопки, он возьмет его и покинет очередь.
  • В противном случае они покинут ее и перейдут в конец очереди.

Это продолжается до тех пор, пока ни один из студентов в очереди не захочет взять верхний бутерброд и, следовательно, не сможет есть. Возвращает количество студентов, которые не могут есть.

Пример:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0

Мы видим, что нашему ученику с индексом 0 не нужен первый бутерброд, поэтому мы хотим удалить ученика и поместить его в конец строки. студенты: [1,1,0,0] -> [1,0,0,1]. Мы снова проверяем и видим, что ученик с индексом 0 также не хочет первый бутерброд. Снимаем их и снова ставим до конца. студенты: [1,0,0,1] -> [0,0,1,1]. Теперь у нас есть матч из бутерброда и студента. Убираем бутерброд и ученицу из их массивов.

студенты = [0,1,1], бутерброды = [1,0,1]

Мы видим закономерность. Если количество студента и бутерброда совпадает, мы удаляем их обоих. Если они не совпадают, мы удаляем ученика и помещаем его в конец строки. Мы хотим использовать этот шаблон до тех пор, пока не закончатся ученики или не исчезнут предпочтительные бутерброды для учеников. Мы можем сделать это, используя цикл while, который проверяет длину массива студентов и логическую проверку, чтобы увидеть, есть ли совпадение с массивом студентов и первым индексом массива сэндвичей.

Следуя этому шаблону, для каждого ученика есть совпадение, и мы возвращаем результат 0.

Это мое решение, написанное на JavaScript. Надеюсь, это пошаговое руководство было полезно!

Для получения дополнительных ресурсов по очередям я предлагаю просмотреть эти полезные ссылки.

Https://medium.com/basecs/to-queue-or-not-to-queue-2653bcde5b04

Https://medium.com/swlh/stacks-and-queues-f281aa5462cf

Ссылка на проблему LeetCode: https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/

Статья о моих стеках: https://medium.com/javascript-in-plain-english/stack-of-pancakes-solving-remove-all-adjacent-duplicates-in-string-c3ace240f4f7