В чем заключается особенности очереди в информатике
Типы очередей в структуре данных
Простая очередь
Как видно из самого названия, простая очередь позволяет нам просто выполнять операции. то есть вставка и удаление выполняются аналогичным образом. Вставка происходит в конце (конце) очереди, а удаления выполняются в начале (начале) списка очереди.
Все узлы соединены друг с другом последовательно. Указатель первого узла указывает на значение второго и так далее.
Первый узел не имеет указателя, указывающего на него, тогда как последний узел не имеет указателя, указывающего на него.
Круговая Очередь
В отличие от простых очередей, в циклической очереди каждый узел последовательно соединяется со следующим узлом, но указатель последнего узла также связан с адресом первого узла. Следовательно, последний узел и первый узел также соединяются, образуя общую кольцевую связь.
Очередь приоритетов
Очередь приоритетов делает возможным получение данных только через предварительно определенный номер приоритета, назначенный элементам данных.
Хотя удаление выполняется в соответствии с номером приоритета (элемент данных с наивысшим приоритетом удаляется первым), вставка выполняется только по порядку.
Двусторонняя очередь (Dequeue)
Двусторонняя очередь позволяют операции вставки и удаления с обоих концов (передний и задний) очереди.
Очереди являются важной концепцией структур данных, и для их правильной работы очень важно понять их типы.
Как и зачем делать очередь на двух стеках
Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат 🙂
Для начала вспомним основы:
Стек реализует принцип LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Стек имеет две основные операции:
Очередь
Очередь — это структура данных с доступом к элементам FIFO (англ. First In, First Out – «первым пришёл — первым ушёл»)
Очередь имеет два основных метода в своем интерфейсе:
Обычно рассматривают два базовых подхода к реализации очереди:
Почему стек круче, чем очередь
Представим себе, что наша структура данных должна поддерживать следующий набор операций:
Для стека можно очень просто поддерживать любую из приведенных операций: достаточно хранить на его вершине пару:
, где второй элемент пары — результат операции, примененной ко всем элементам стека.
Ниже пример реализации стека с поддержкой минимума на Python:
А теперь подумайте, как проделать тот же фокус с очередью? Если пробовать с классической очередью, организованной на массиве, вряд ли что-то получится. Это связано с тем, что операция минимум не имеет обратную операцию (как операция сложения имеет операцию вычитания, например). Как вы могли догадаться, далее я расскажу о не совсем классической реализации очереди на двух стеках.
Очередь на двух стеках
Главное условие, которое должно быть выполнено — все операции должны выполняться за амортизированное O(1).
Возьмем два стека: s1 и s2.
Операцию push будем всегда делать в стек s1.
Операция pop будет устроена так: если стек s2 пустой, перекладываем все элементы из s1 в s2 последовательными вызовами pop и push. Теперь в стеке s2 лежат элементы в обратном порядке (самый верхний элемент — это самый первый положенный элемент в нашу очередь).
Если s2 не пуст, тупо достаем элементы из него. Как только s2 окажется снова пустым повторяем ту же операцию.
Время работы
Операция push: Мы тупо кладем элемент в стек s1. Время работы O(1).
Операция pop: Для каждого элемента мы делаем не более одного перекладывания из стека в стек, следовательно амортизированное время работы составит O(1).
Операция get_min: Для стеков s1 и s2 известны минимумы, поэтому мы просто берем минимум из минимумов. Время работы O(1).
Бонусная задачка
Заключение
Спасибо, что дочитали до конца!
Если вас заинтересовала тема, можете почитать как сделать персистентную очередь на двух стеках здесь, либо дождаться выхода следующего моего топика.
Пишите в комментариях какие задачи на двух стеках вам приходилось решать на интервью или контестах.
Очереди — что это, зачем и как использовать? Посмотрим на возможности AWS SQS
Сначала давайте дадим определение понятию «очередь — queue».
Возьмем для рассмотрения тип очереди «FIFO»(first in, first out). Если взять значение из википедии — «это абстрактный тип данных с дисциплиной доступа к элементам». Если вкратце, это означает что мы не можем из нее доставать данные в случайном порядке, а только забирать то — что пришло первым.
Далее, нужно определиться зачем вообще они нужны?
1. Для отложенных операций. Классическим примером является обработка картинок. К примеру пользователь загрузил на сайт картинку, которую нам нужно обработать, эта операция занимает много времени, пользователь столько ждать не хочет. Поэтому мы грузим картинку, далее передаем ее в очередь. И она будет обработана, когда какой либо «worker» ее достанет.
2. Для обработки пиковых нагрузок. К примеру, есть какая-то часть системы, на которую иногда обрушивается большой трафик и она не требует мгновенного ответа. Как вариант, генерация каких-либо отчетов. Выкидывая в очередь эту задачу — мы даем возможность обрабатывать это с равномерной нагрузкой на систему.
3. Масштабируемость. И наверное самая важная причина, очередь дает возможность
масштабироваться. Это означает, что вы можете поднять несколько сервисов для обработки параллельно, что сильно повысит производительность.
Теперь давайте рассмотрим проблемы, с которыми столкнемся, если будем создавать очередь сами:
1. Параллельный доступ. Забрать из очереди определенное сообщение может только один обработчик. То есть если одновременно два сервиса попросят сообщения, каждому из них должен вернуться уникальный набор сообщений. Иначе, получится, что одно сообщение обработается два раза. Что может быть чревато.
2. Механизм дедупликации. В сервисе должна быть система, защищающая очередь от дубликатов. Может быть ситуация, в которой случайно в очередь будет отправлено один и тот-же набор данных два раза. В итоге мы одно и тоже обработаем два раза. Что опять же чревато.
3. Механизм обработки ошибок. Допустим наш сервис забрал из очереди три сообщения. Два из которых он успешно обработал, отправив запросы на удаление из очереди. А третье он не смог обработать и умер. Сообщение которое находится в статусе обработки — недоступно для других сервисов. И оно не должно навечно остаться в статусе обработки. Такое сообщение должно передаться другому обработчику по какой-то логике. Вариант реализации такой логики мы рассмотрим скоро на примере AWS SQS(Simple Queue Service)
Amazon Web Services — Simple Queue Service
Теперь давайте рассмотрим как решает эти проблемы SQS и что он может
1. Параллельный доступ. У очереди вы можете задать параметр «Visibility timeout». Он определяет, сколько по времени максимально может длиться обработка сообщения. По умолчанию он равен 30 секундам. Когда какой-либо сервис забирает сообщение, оно переводится в статус «In Flight» на 30 секунд. Если за это время не было команды удалить это сообщение из очереди, оно возвращается в начало и следующий сервис сможет его получить для обработки еще раз.
Небольшая схемка работы.
2. Механизм обработки ошибок. В SQS можно настроить вторую очередь для «мертвых» сообщений(Dead Letter Queue). То есть те, которые не смог обработать наш сервис, будут отправляться в отдельную очередь, которой вы можете распоряжаться по своему усмотрению. Также вы можете задавать после которого кол-ва неудачных попыток сообщение перейдет в «мертвую» очередь. Неудачной попыткой считается истечение «Visibility timeout». То есть если за это время не было отправлено запроса на удаление, такое сообщение будет считаться необработанным и вернется в основную очередь или перейдет в «мертвую».
3. Дедупликация сообщений. Так же SQS имеет систему защиты от дубликатов. У каждого сообщения есть «Deduplication Id», SQS не добавит в очередь сообщение с
повторным «Deduplication Id» в течении 5 минут. Вы обязаны задавать «Deduplication Id» в каждом сообщении или включить генерацию id на основе контента. Это означает что в «Deduplication Id» будет попадать хэш сгенерированный исходя из вашего контента. Параметр «Content-Based Deduplication». Подробнее о дедупликации
Notice: Будьте внимательны, если отправить два одинаковых сообщения в течении 5 минут и у вас включен «Content-Based Deduplication» SQS не добавит второе сообщение в очередь.
Notice: Будьте внимательны, к примеру если на девайсе отпала связь, и он не получил ответ и затем отправил повторный запрос спустя 5 минут, дубликат создастся.
4. Long poll. Длительный опрос. SQS поддерживает такой тип подключения с максимальным таймаутом в 20 секунд. Что нам позволяет сэкономить на трафике и «дерганье» сервиса.
5. Метрики. Так же Amazon предоставляет подробные метрики по очередям. Такие как кол-во полученных/отправленных/удаленных сообщений, размеры в КБ этих сообщений и прочее. Также вы можете подключить SQS к сервису логов CloudWatch. Там сможете увидеть еще подробнее. Так же там можно настроить так называемые «сигналы тревоги»(Alarms) и вы можете настраивать действия по каким либо событиям. Подробнее о подключении к SQS. И Документация по CloudWatch
Теперь давайте рассмотрим настройки очереди:
Основные:
Message Retention Period — кол-во секунд/минут/часов/дней, которое означает, сколько по времени будут в очереди храниться необработанные сообщения. Максимально — 14 дней.
Maximum Message Size — максимальный размер сообщения в KB. Значение от 1KB до 256KB.
Receive Message Wait Time — время, сколько будет держаться коннект в случае, если мы используем «Long poll», для получения новых сообщений.
Content-Based Deduplication — флаг, если установлен в true, то в каждое сообщение будет добавлен «Deduplication Id» в виде SHA-256 хэша, сгенерированный из контента.
Настройки «мертвой очереди»
Use Redrive Policy — флаг, если установлен, то сообщения после нескольких попыток будут перенаправляться.
Dead Letter Queue — имя «мертвой» очереди, в которую будут отправляться необработанные сообщения.
Maximum Receives — кол-во неудачных попыток обработки, после которых сообщение будет отправляться в «мертвую» очередь
Notice: Также обратите внимание, что все основные параметры мы можем отправлять вместе с каждым сообщением отдельно. К примеру, каждое отдельное сообщение может иметь свой Visibility Timeout или Delivery Delay
Теперь немного про сами сообщения и их свойства:
Сообщение имеет несколько параметров:
Также есть атрибуты сообщений
Атрибуты состоят из имени, типа и значения.
Notice: Обратите внимание, что максимальное кол-во атрибутов 10 Подробности
Динамические структуры данных: очередь и стек
Очереди
Описание очереди выглядит следующим образом:
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
1 способ: адресное поле ссылается на объявляемую структуру.
2 способ: адресное поле ссылается на ранее объявленную структуру.
Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередь через объявление линейного двунаправленного списка:
Пример 2. Дана последовательность ненулевых целых чисел. Признаком конца последовательности является число 0. Найдите среди них первый наибольший отрицательный элемент. Если такого элемента нет, то выведите сообщение об этом.
В данной задаче будем использовать основные операции для работы с очередью, рассмотренные ранее. Приведем главную функцию и функцию для реализации поиска первого наибольшего отрицательного элемента.
Ключевые термины
LIFO (Last Input – First Output) – это метод доступа к элементам стека по принципу «последним пришел – первым вышел»
Вершина стека – это доступный элемент стека.
Конец очереди – это позиция доступного для вставки в очередь элемента.
Начало очереди – это позиция доступного для извлечения из очереди элемента.
Алгоритмы и структуры данных для начинающих: стеки и очереди
Авторизуйтесь
Алгоритмы и структуры данных для начинающих: стеки и очереди
В предыдущих частях мы рассматривали базовые структуры данных, которые, по сути, являлись надстройками над массивом. В этой статье мы добавим к коллекциям простые операции и посмотрим, как это повлияет на их возможности.
Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу.
Наиболее часто встречающаяся аналогия для объяснения стека — стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.
Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.
Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.
Класс Stack
Метод Push
Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.
Метод Pop
Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.
Метод Peek
Метод Count
Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.
Пример: калькулятор в обратной польской записи
Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:
Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.
То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:
То есть, для выражения «4 2 +» действия будут следующие:
В конце на стеке окажется одно значение — 6.
Очередь
Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.
Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.
Класс Queue
Метод Enqueue
Новые элементы очереди можно добавлять как в начало списка, так и в конец. Важно только, чтобы элементы доставались с противоположного края. В данной реализации мы будем добавлять новые элементы в начало внутреннего списка.
Метод Dequeue
Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.
Метод Peek
Метод Count
Двусторонняя очередь
Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.
Класс Deque
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Пример: реализация стека
Двусторонняя очередь часто используется для реализации других структур данных. Давайте посмотрим на пример реализации стека с ее помощью.
У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.
Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.
Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:
Хранение элементов в массиве
Как уже было упомянуто, у реализации очереди с использованием массива есть свои преимущества. Она выглядит простой, но на самом деле есть ряд нюансов, которые надо учесть.
Давайте посмотрим на проблемы, которые могут возникнуть, и на их решение. Кроме того, нам понадобится информация об увеличении внутреннего массива из прошлой статьи о динамических массивах.
При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.
Добавляем элемент в начало
Добавляем элемент в конец
Добавляем еще один элемент в начало
Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).
И еще один в конец
Массив заполнен, поэтому при добавлении элемента произойдет следующее:
Добавляем значение в конец расширенного массива
Теперь посмотрим, что происходит при удалении элемента:
Удаляем элемент из начала
Удаляем элемент с конца
Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди — элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».
Теперь давайте посмотрим на реализацию.
Класс Deque (с использованием массива)
Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля — сам массив, его размер и указатели на «хвост» и «голову» очереди.
Алгоритм роста
Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).
Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Продолжение следует
Вот мы и закончили четвертую часть нашего цикла статей. В ней мы рассмотрели стеки и очереди. В следующий раз мы перейдем к бинарным деревьям поиска.