до 18 ноября
Хватай скидки -30% на все!
Черная пятница
Что такое очередь простыми словами?
Автор — Владимир Балун
ex-TeamLead в Яндекс
Не все начинающие разработчики понимают, как работает очередь и в каких задачах ее стоит использовать. Из-за этого становится сложнее разбираться в алгоритмах и проходить технические собеседования.
В этой статье разберем, что такое очередь, как работает принцип FIFO и где применяется на практике.
В этой статье разберем, что такое очередь, как работает принцип FIFO и где применяется на практике.
1. Что такое очередь?
Очередь (англ. Queue) — это абстрактная структура данных, концепция которой знакома нам из реальной жизни
Например, когда мы приходим в магазин и видим очередь, то мы встаем в ее конец — то есть производим добавление нового элемента в конец очереди.
Добавление нового элемента в конец очереди
Когда подходит наша очередь, то нас в магазине обслуживают. Это означает, что из очереди извлекается элемент, который находится в ее начале.
Извлечение элемента из начала очереди
Более того, структура данных очередь подразумевает то, что вы можете обратиться к первому элементу очереди и к последнему элементу очереди.
Обращение к первому элементу очереди («1») и к последнему («2»)
Таким образом, имея такую структуру данных, мы можем добавлять элементы в конец очереди и извлекать элементы из начала очереди.
У такого способа взаимодействия с данными есть название — FIFO (First In, First Out). Этот принцип подразумевает, что «тот, кто пришел первым, будет обслужен первым». Другими словами, первый добавленный элемент первым покидает структуру данных
2. Реализация очереди
Как правило, для реализации очереди используют связанный список либо деку. В данной статье рассмотрим реализацию очереди на основе связанного списка.
Реализация очереди на основе связанного списка
Для работы с такой очередью используются два указателя:
- head — указатель на начало связанного списка;
- tail — указатель на конец связанного списка.
3. Основные операции над очередью
Добавление элемента
В очереди добавление всегда производится в конец. Поскольку у нас есть указатель на последний элемент tail, то все, что нужно сделать, — это:
1. Добавить новый элемент после текущего tail
2. Указать, что новый элемент не ссылается ни на какой следующий узел
3. Обновить предыдущий tail
Представим, что нужно добавить элемент со значением «5». В связанный список помещаем новый элемент «5», после чего обновляем указатель tail с «2» на «5».
Поскольку у нас есть указатель на последний элемент связанного списка, а вставка в известное место связанного списка является константной операцией, то добавление элемента в очередь выполняется за константное время.
Поскольку у нас есть указатель на последний элемент связанного списка, а вставка в известное место связанного списка является константной операцией, то добавление элемента в очередь выполняется за константное время.
Удаление элемента
Удаление в очереди производится из начала:
1. Сперва нужно сдвинуть указатель head на следующий элемент
2. Затем удалить старый элемент
Удаление элемента «1» из начала очереди со сдвижением указателя «head» c «1» на «4»
Удаление первого элемента привело к смещению указателя head на следующий узел. Поскольку у нас есть указатель на начало связанного списка, удаление первого элемента также является константной операцией.
Получение первого и последнего элемента
Так как очередь хранит указатели и на начало, и на конец связанного списка, мы можем за константное время обращаться к первому и последнему элементу очереди.
Указатели «head» и «tail» позволяют мгновенно получать доступ к началу и концу очереди за константу
4. Кейсы использования очереди
Очередь — одна из самых популярных структур данных в программировании. Рассмотрим известный пример. Представим, что мы разрабатываем веб-сервер, к которому одновременно приходит множество пользователей с различными запросами.
Чтобы обслуживать эти запросы в порядке их поступления, пользователей можно выстраивать в очередь. Новые запросы будут добавляться в конец очереди, а сервер будет последовательно обрабатывать запросы из ее начала. Для организации такого механизма отлично подходит структура данных очередь.
Чтобы обслуживать эти запросы в порядке их поступления, пользователей можно выстраивать в очередь. Новые запросы будут добавляться в конец очереди, а сервер будет последовательно обрабатывать запросы из ее начала. Для организации такого механизма отлично подходит структура данных очередь.
5. Заключение
Очередь используется во многих программных системах — от обработки пользовательских запросов до организации работы серверов и фоновых задач. Благодаря принципу FIFO она позволяет обрабатывать данные в том порядке, в котором они поступают.
Понимание устройства очереди помогает лучше разбираться в алгоритмах, архитектуре приложений и других структурах данных.
Если хотите подробнее разобраться в работе очередей, то смотрите наше видео с наглядными примерами из курса по структурам данных.
Понимание устройства очереди помогает лучше разбираться в алгоритмах, архитектуре приложений и других структурах данных.
Если хотите подробнее разобраться в работе очередей, то смотрите наше видео с наглядными примерами из курса по структурам данных.
Другие статьи