На основе массивов и стеков и очередей на основе списков

Я пытаюсь сравнить темпы роста (как время выполнения, так и пространство) для операций стека и очереди при реализации как массивов, так и связанных списков. До сих пор мне удалось найти средние временные ряды для очереди pop() s, но ничего, что всесторонне исследует эти две структуры данных и сравнивает их поведение во время выполнения/пространства.

В частности, я ищу сравнение push() и pop() для обеих очередей и стеков, реализованных как как массивы, так и связанные списки (таким образом, 2 операции x 2 структуры x 2 реализации или 8).

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

Ближайшая вещь, которую я смог найти, это "мама всех чит-листов cs" pdf, которая явно является чит-листом мастеров или докторантов передовых алгоритмов и дискретных функций.

Я просто ищу способ определить, когда и где я должен использовать реализацию на основе массива, и реализацию на основе списка для стеков и очередей.

Ответ 1

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

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

В динамическом массиве мы можем получить доступ к любому элементу в O (1) времени. Мы также можем добавить элемент в амортизированный O (1), что означает, что общее время для n вставок равно O (n), хотя фактическое время границы на любой вставке могут быть намного хуже. Как правило, динамические массивы реализуются за счет того, что большинство вложений принимают O (1) путем добавления в предварительно распределенное пространство, но с небольшим количеством вставок выполняется в & Theta; (n) время, удваивая емкость массива и копируя элементы. Есть способы попытаться уменьшить это, выделив лишнее пространство и лениво копируя элементы (см. эту структуру данных, например). Как правило, использование памяти динамического массива довольно хорошо - когда массив полностью заполнен, например, есть только O (1) дополнительные служебные данные - хотя сразу после того, как массив удвоился по размеру, возможно, O (n) не используется элементов, выделенных в массиве. Поскольку распределения нечасты, а обращения выполняются быстро, динамические массивы обычно быстрее, чем связанные списки.

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

Стек:
- Связанный список: как односвязный список с указателем головы.
- Массив: как динамический массив
Очередь:
- Связанный список: как односвязный список с указателем головы и хвоста.
- Массив: как круговой буфер, поддерживаемый массивом.

Рассмотрим каждый по очереди.

Стоп, поддерживаемый односвязным списком.. Поскольку односвязный список поддерживает O (1) время preend и delete - во-первых, затраты на то, чтобы нажать или поместить в поддерживаемый ссылками список стек также O (1) наихудший. Однако каждый добавленный новый элемент требует нового распределения, а распределения могут быть дорогими по сравнению с другими операциями.

Стек, поддерживаемый динамическим массивом. Нажатие на стек может быть реализовано путем добавления нового элемента в динамический массив, который берет амортизированное время O (1) и наихудшее значение O (n) время. Поппать из стека можно реализовать, просто удалив последний элемент, который запускается в худшем случае O (1) (или амортизируется O (1), если вы хотите попытаться восстановить неиспользуемое пространство). Другими словами, наиболее распространенная реализация имеет наилучший вариант O (1) push и pop, худший случай O (n) push и O (1) pop, а также амортизацию O (1) push и O (1) pop.

Очередь, поддерживаемая односвязным списком. Включение в связанный список может быть реализовано путем добавления к обратной стороне односвязного списка, который занимает наихудшее время O (1). Удаление может быть реализовано путем удаления первого элемента, который также занимает наихудшее время O (1). Это также требует нового распределения для очереди, что может быть медленным.

Очередь, поддерживаемая растущим круговым буфером. Запуск в циклический буфер работает, вставив что-то в следующую свободную позицию в круговом буфере. Это работает, увеличивая массив при необходимости, а затем вставляя новый элемент. Используя аналогичный анализ для динамического массива, это занимает наилучшее время O (1), наихудшее время O (n) и время амортизации O (1). Удаление из буфера работает, удалив первый элемент кругового буфера, который занимает время O (1) в худшем случае.

Подводя итог, все структуры поддерживают push и popping n элементов в O (n) времени. Связанные версии списков имеют лучшее поведение в худшем случае, но могут иметь худшую общую продолжительность выполнения из-за количества выполненных распределений. Варианты массивов медленнее в худшем случае, но имеют лучшую общую производительность, если время на операцию не слишком важно.

Другим вариантом, который может потребоваться для реализации стеков, является VList, недавняя структура данных, которая представляет собой гибрид связанного список и динамический массив. Он делает меньше распределений, чем связанный список, и имеет меньше указателей, хотя использование пространства в худшем случае немного выше. Вы также можете посмотреть в chunklists, которые являются еще одним гибридом массивов и связанных списков, которые могут использоваться как для стеков, так и для очередей.

Надеюсь, это поможет!

Ответ 2

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

С помощью вектора вы можете только эффективно добавлять/удалять элементы в конце контейнера. С помощью deque вы можете эффективно добавлять/удалять элементы в начале/конце контейнера. Со списком вы можете эффективно вставлять/удалять элементы в любом месте контейнера.

векторы/deque допускают итераторы произвольного доступа. списки допускают только последовательный доступ.

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

EDIT:

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