В чем разница между queue и deque и stack

c++ deque vs queue vs stack

Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:

but for stack you can only do it like this

My question is, what’s the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?

9 Answers 9

Moron/Aryabhatta is correct, but a little more detail may be helpful.

Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.

Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.

You can think of s as a restricted deque and q as a restricted list.

All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back() , push_back() , and pop_back() for stack and front() , back() , push_back() , and pop_front() for queue.

See stack and queue for more detail.

With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[] . This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front() and pop_front() .

В чем разница между queue и deque и stack

Класс Stack

• Поведение: Добавляет элемент на вершину стека.
• Сложность: O(1).

• Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

• Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в стеке.
• Сложность: O(1).

Класс Queue

Метод Enqueue

• Поведение: Добавляет элемент в очередь.
• Сложность: O(1).

Метод Dequeue

• Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

• Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Класс Deque

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1).

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1).

Метод DequeueFirst

• Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

• Алгорим роста определит размер нового массива.
• Элементы скопируются в новый массив с «головы» до «хвоста».
• Добавится новый элемент.

Класс Deque (с использованием массива)

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод DequeueFirst

• Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

1.

2.

3.

Привет! Сегодня поговорим о таких важных для любого программиста вещах как структуры данных . Википедия гласит: Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Определение немного запутанное, но суть его ясна. Структура данных — это такое своеобразное хранилище, где мы держим данные для дальнейшего использования. В программировании существует огромное количество разнообразных структур данных. Очень часто при решении конкретной задачи самое главное — выбор наиболее подходящей для этого структуры данных. И со многими их них ты уже знаком! Например, с массивами . А также с Map (которую обычно переводят как “словарь”, “карта”, или “ассоциативный массив”). Очень важно понимать: структуры данных не привязаны к какому-то конкретному языку . Это просто абстрактные “чертежи”, по которым каждый язык программирования создает свои собственные классы — реализации этой структуры. Например, одна из самых известных структур данных — связный список . Ты можешь зайти в википедию, почитать о том как он устроен, какие у него есть достоинства и недостатки. Возможно, тебе покажется знакомым его определение 🙂 “Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка” Так ведь это же наш LinkedList ! Точно, так оно и есть 🙂 Структура данных “связный список” реализована в языке Java в классе LinkedList . Но и в других языках связный список тоже реализован! В Python он называется “ llist ”, в Scala называется так же, как в Java — “ LinkedList ”. Связный список — одна из базовых распространенных структур данных, поэтому ее реализацию ты найдешь в любом современном языке программирования. То же самое с ассоциативным массивом. Вот его определение из Википедии: Ассоциативный массив — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. Ничего не напоминает? 🙂 Точно, для нас, джавистов, ассоциативный массив — это интерфейс Map . Но эта структура данных реализована и в других языках! Например, программисты на C# знают его под названием “Dictionary”. А в языке Ruby он реализован в классе под названием “Hash”. В общем, ты примерно понял в чем смысл: структура данных — это такая общая для всего программирования штука, которая реализуется по-своему в каждом конкретном языке. Сегодня мы изучим две такие структуры и посмотрим, как они реализованы в Java — стек и очередь.

Русские Блоги

1.3 Сценарии применения deque

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

Два, стек

2.1 Введение в стек

1. Стек — это адаптер контейнера, специально используемый в контексте операций «последний вошел — первым ушел». Его удаление может быть выполнено только с одного конца контейнера для вставки и извлечения элементов.
2. Стек реализован как адаптер контейнера. Адаптер контейнера инкапсулирует определенный класс в качестве своего нижнего контейнера и предоставляет набор определенных функций-членов для доступа к его элементам. Конкретный класс используется в качестве его нижнего уровня, а конец контейнера для конкретного элемента ( То есть вершина стека) толкается и выталкивается.
3. Нижний контейнер стека может быть любым стандартным шаблоном класса контейнера или каким-либо другим конкретным классом контейнера. Эти классы контейнера должны поддерживать следующие операции:
   empty: пустая операция
   назад: получить операцию хвостового элемента
   push_back: операция вставки элемента в конец
   pop_back: операция удаления элемента из хвоста
4. Стандартные контейнеры vector, deque и list соответствуют этим требованиям. По умолчанию, если для стека не указан конкретный базовый контейнер,
   по умолчанию использует двухстороннюю очередь.

2.2 реализация моделирования стека

Три, очередь

3.1 Введение в очередь

1. Очередь — это адаптер контейнера, который специально используется для работы в контексте FIFO (первым пришел — первым ушел), в котором элементы вставляются с одного конца контейнера, а элементы извлекаются с другого.
2. Очередь реализована как адаптер контейнера. Адаптер контейнера инкапсулирует определенный класс контейнера в качестве базового класса контейнера. Очередь предоставляет набор определенных функций-членов для доступа к своим элементам. Элементы входят в очередь с конца очереди и выходят из нее с начала очереди.
3. Базовый контейнер может быть одним из стандартных шаблонов классов контейнера или другими специально разработанными классами контейнеров. Базовый контейнер должен как минимум поддерживать следующие операции
   :
   пусто: проверьте, пуста ли очередь.
   size: возвращает количество допустимых элементов в очереди.
   front: возвращает ссылку на элемент head.
   назад: вернуть ссылку на хвостовой элемент
   push_back: введите очередь в конец очереди
   pop_front: выйти из очереди в начале очереди
4. Этим требованиям соответствуют стандартные классы контейнера deque и list. По умолчанию, если для создания экземпляра очереди не указан класс контейнера, используется стандартная двухсторонняя очередь контейнера.

3.2 реализация моделирования очереди

Четыре, priority_queue

4.1 Введение в priority_queue

1. Приоритетная очередь — это своего рода контейнерный адаптер, в котором согласно строгим критериям слабого упорядочения ее первый элемент всегда является самым большим среди содержащихся в ней элементов.
2. Этот контекст похож на кучу. Элементы могут быть вставлены в кучу в любое время, и может быть получен только самый большой элемент кучи (элемент наверху в очереди с приоритетом).
   элемент).
3. Очередь с приоритетом реализована как адаптер контейнера. Адаптер контейнера инкапсулирует определенный класс контейнера в качестве своего базового класса контейнера. Очередь предоставляет набор специальных функций.
   указывает функцию-член для доступа к ее элементам. Элементы извлекаются из «хвоста» конкретного контейнера, который называется вершиной очереди приоритета.
4. Базовым контейнером может быть любой стандартный шаблон класса контейнера или другие специально разработанные классы контейнера. Контейнер должен быть
   Доступ к прокси-серверу и поддерживает следующие операции:
   empty (): проверьте, пуст ли контейнер.
   size (): возвращает количество допустимых элементов в контейнере.
   front (): возвращает ссылку на первый элемент в контейнере.
   push_back (): вставить элемент в конец контейнера
   pop_back (): удалить элемент в конце контейнера
5. Этим требованиям удовлетворяют стандартные классы контейнеров vector и deque. По умолчанию, если нет указателя на создание для определенного класса priority_queue
   Если вы указываете класс контейнера, используйте вектор.
6. Необходимо поддерживать итераторы с произвольным доступом, чтобы структура кучи всегда поддерживалась внутри. Адаптер контейнера автоматически вызывает функции алгоритма при необходимости.
   make_heap, push_heap и pop_heap для автоматического завершения этой операции

4.2 Использование priority_queue

По умолчанию приоритетная очередь использует вектор в качестве базового контейнера данных хранилища. В векторе алгоритм кучи используется для создания элементов вектора в структуру кучи. Следовательно, priority_queue — это куча, а priority_queue может учитываться для всех мест, где требуется куча. . нота:По умолчанию priority_queue большой

Обработка встроенных типов:

Если вы помещаете настраиваемый тип данных в priority_queue, пользователю необходимо предоставить перегрузку> или <в настраиваемом типе

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

4.4 Реализация моделирования priority_queue

Пять связанных вопросов, требующих внимания

1. Зачем использовать deque в качестве базовой структуры стека и очереди?

Прежде всего, преимущество deque состоит в том, что голова и хвост просты в использовании, а эффективность может достигать O (1). Недостатком является то, что базовое пространство deque не является непрерывным. Причина, по которой оно кажется непрерывным, — это заслуга итератора. Именно из-за deque. Пространство не является непрерывным, поэтому эффективность его обхода крайне мала, поскольку необходимо судить о местоположении следующего пространства. Стек и очередь используются в качестве адаптеров контейнеров. Их не нужно пересекать, их нужно использовать только на обоих концах, чтобы избежать дефектов deque. Хотя другие контейнеры также могут использоваться в качестве базовой структуры стека и очереди, они не так эффективны, как deque.

2. Что такое контейнерный адаптер?

Адаптер — это шаблон проектирования (шаблон проектирования — это набор многократно используемых, известных большинству людей, каталогизированных, общий опыт проектирования кода
end), режим заключается в преобразовании интерфейса класса в другой интерфейс, который требуется заказчику.

3. Почему stack, queue и priority_queue называются адаптерами контейнера?

Хотя элементы также могут храниться в стеке, очереди и priority_queue, они не делятся на ряды контейнеров в STL, а называются адаптерами контейнеров, потому что каждый контейнер имеет свою собственную реализацию внизу. И stack, queue, priority_queue просто инкапсулируют другие контейнеры внизу

В чем разница между queue и deque и stack

Здесь мы добавляем в очередь LinkedList некоторые строки, затем в цикле извлекаем их из очереди и одновременно выводим на экран. Наличие элементов в очереди проверяем через метод peek(), который возвращает null в случае, если элементов не осталось. Это сделано лишь для наглядности. Логичнее наличие элементов проверять через метод isEmpty(). В результате увидим, что элементы извлекаются в том же порядке, в котором были добавлены:

Обратите внимание, что LinkedList также реализует интерфейс List, который мы рассматривали в предыдущей статье.

Теперь проделаем то же самое с очередью PriorityQueue.

На экране увидим следующее:

То есть вопреки порядку добавления, элементы извлекаются в алфавитном порядке. Таким образом, можно сделать вывод, что PriorityQueue сортирует элементы в порядке возрастания (или алфавитный порядок для строк).

Тогда на экране увидим:

То есть элементы извлекаются в обратном порядке, начиная с последнего. Класс Stack является расширением класса Vector. Оба этих класса появились ещё в Java 1.0. Ныне они считаются устаревшими и их не рекомендуется применять в новых проектах.

Интерфейс Deque реализуют всё тот же LinkedList, а также ArrayDeque.

Пример работы с деком в качестве стека:

Выводы

На основании рассмотренных нами интерфейсов и реализаций можно сделать вывод, что для самой простой реализации очереди Queue следует выбрать LinkedList. Eсли требуется как-то сортировать элементы внутри очереди, то подойдёт PriorityQueue. Если же нам нужна функциональность стека, то надо использовать интерфейс Deque и одну из его реализаций: LinkedList или ArrayDeque.

c++ deque vs queue vs stack

очередь и стек являются структурами, широко упоминаемыми. Однако в C++ для queue вы можете сделать это двумя способами:

но для стека вы можете сделать это только так

мой вопрос в том, в чем разница между queue и deque, почему предлагаются две структуры? Для stack может быть включена любая другая структура?

8 ответов

Морон / Арьябхатта прав, но немного больше деталей может быть полезно.

очередь и стек являются контейнерами более высокого уровня, чем deque, vector или list. Под этим я подразумеваю, что вы можете построить очередь или стек из контейнеров нижнего уровня.

построит стек ints, используя deque в качестве базового контейнера и очередь двойников, используя список в качестве базового контейнера.

вы можете думать о s как ограниченный deque и q как ограниченный список.

посмотреть стек и очереди подробнее.

посмотреть очереди для детали.

очередь: вы можете вставить только в одном конце и удалить из другого.

Deque: вы можете вставлять и удалять с обоих концов.

таким образом, используя Deque, вы можете моделировать очередь, а также стек.

в библиотеке C++, как std::stack и std::queue реализованы как container переходник. Это означает, что они предоставляют интерфейс стека или очереди соответственно, но ни один из них не является контейнером сам по себе. Вместо этого они используют какой-то другой контейнер (например, std::deque или std::list хранение данных), а std::stack класс просто имеет крошечный бит кода для перевода push и pop to push_back и pop_back (и std::queue делает примерно то же самое, но с использованием push_back и pop_front ).

a deque-это двусторонняя очередь, которая позволяет легко вставлять/удалять с любого конца. Очереди позволяют только вставку в одном конце и извлечение из другого.

deque поддерживает insert / pop от back & front

queue поддерживает только вставку сзади и pop спереди. Вы знаете, FIFO (первый в первый выход).

деке является двусторонним. Очереди нет.

приоритет очереди dequeue происходит в соответствии с некоторым заказом (приоритет) сравнение не порядок enqueue.

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

очереди приоритетов часто реализуются с помощью куч.

Простейшие структуры данных: стек, очередь, дек

Понятие структуры данных

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

Таким образом, структура данных характеризуется операциями, которые она может выполнять, и скоростью их выполнения.

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

Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.

Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:

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

Очередь

Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.

Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):

При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.

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

Стек, очередь и дек в стандартной библиотеке C++

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

Более сложные структуры данных

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

brestprog

Олимпиадное программирование в Бресте и Беларуси

c ++ deque vs queue vs stack

но для стека вы можете сделать это только так

Мой вопрос: в чем разница между очередью и deque, почему предложены две структуры? Для стека может быть включена любая другая структура?

8 ответов

Морон /Арьябхатта верны, но может быть полезно немного больше деталей.

Очередь и стек являются контейнерами более высокого уровня, чем deque, vector или list. Под этим я подразумеваю, что вы можете построить очередь или стек из контейнеров более низкого уровня.

Построит стек целых чисел, используя deque в качестве основного контейнера и очередь двойников, используя список в качестве основного контейнера.

Вы можете думать о s как ограниченном deque и q как ограниченный список.

См. стек и queue для получения более подробной информации.

Очередь: вы можете вставить только один конец и удалить из другого.

Deque: вы можете вставлять и удалять с обоих концов.

Таким образом, используя Deque, вы можете смоделировать очередь и стек.

deque поддерживает вставку /вставку из задней части & передняя

Дека двусторонняя. Очередь не.

Приоритет очереди очереди происходит в соответствии с некоторым порядком (приоритетом) сравнения, а не порядком очереди.

Например, вы можете хранить синхронизированные события в том, где вы хотите сначала извлечь самое быстрое событие, и запросить его запланированное время, чтобы вы могли спать до этого момента.

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

Помогите разобраться в разнице между очередями и стекам

Мне не понятна тема очередей стеков и вариантов из реализаций. Выжимка из того что мне удалось накопать в гугле выглядит как-то так:

Вопрос: Вроде-бы PriorityQueue и LinkedList ее реализации в коллекциях java. А другие есть? Или по другому:

Вопрос: Вот это совсем не понятно это по типу как замкнутый двунаправленный связанный список? Что это? Не понятна идея и какую проблему она решает.

Вопрос: Вроде у List есть реализация Stack она вроде как отражает эту идею. А еще есть реализации? А какую проблему этот механизм решает?

Вот запутался немного, помогите разобраться что для чего нужно, и какие реализации имеет. Спасибо.

3 ответа 3

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

Почитать с картинками можно статьи, вроде этой, здесь о самостоятельной реализации, но принцип хорошо описан «изнутри».