Существует несколько различных способов реализации очередей и стеков со связанными списками и массивами, и я не уверен, какие из них вы ищете.Однако перед анализом любой из этих структур давайте рассмотрим некоторые важные соображения времени выполнения для вышеуказанных структур данных.
В односвязном списке с указателем только заголовка стоимость добавления значения равна O (1)- мы просто создаем новый элемент, связываем его указатель, чтобы он указывал на старый заголовок списка, а затем обновляем указатель заголовка.Стоимость удаления первого элемента также составляет O (1), что выполняется путем обновления указателя заголовка, чтобы он указывал на элемент после текущего заголовка, а затем освобождает память для старого заголовка (если выполняется явное управление памятью).Однако постоянные коэффициенты в этих терминах O (1) могут быть высокими из-за затрат на динамическое распределение.Избыток памяти связанного списка обычно составляет O (n) общей дополнительной памяти из-за хранения дополнительного указателя в каждом элементе.
В динамическом массиве мы можем получить доступ к любому элементу за O (1) времени,Мы также можем добавить элемент в амортизированный O (1) , что означает, что общее время для n вставок равно O (n), хотя фактические временные границы для любой вставки могут быть намного хуже.Как правило, динамические массивы реализуются за счет того, что большинство вставок принимают O (1), добавляя в предварительно выделенное пространство, но имея небольшое количество вставок, выполняемых за Θ (n) времени, удваивая емкость массива и копируя элементы поверх.Есть способы попытаться уменьшить это, выделяя дополнительное пространство и лениво копируя элементы (см., Например, эту структуру данных ).Как правило, использование памяти динамического массива довольно хорошее - например, когда массив полностью заполнен, есть только O (1) дополнительные издержки - хотя сразу после того, как массив удвоился, может быть O (n) неиспользованнымэлементы, расположенные в массиве.Поскольку распределения происходят редко, а доступы быстрые, динамические массивы обычно быстрее, чем связанные списки.
Теперь давайте подумаем о том, как реализовать стек и очередь, используя связанный список или динамический массив.Есть много способов сделать это, поэтому я предполагаю, что вы используете следующие реализации:
- Стек:
- Очередь:
- Связанный список: в видеодносвязный список с указателем головы и хвоста.
- Массив: в виде кольцевого буфера , поддерживаемого массивом.
Давайтерассмотрим каждый из них по очереди.
Стек, поддерживаемый односвязным списком. Поскольку односвязный список поддерживает O (1) предварительное и временное удаление, стоимость push или popв стек со связанными списками также наихудший случай 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).
Подводя итог, все структуры поддерживают нажатие и выталкивание n элементов за O (n) время. Версии связанного списка имеют лучшее поведение в худшем случае, но могут иметь худшее общее время выполнения из-за количества выполненных выделений. Версии массива медленнее в худшем случае, но имеют лучшую общую производительность, если время на операцию не слишком важно.
Другой вариант, который вы можете использовать для реализации стеков, - это VList , последняя структура данных, которая представляет собой гибрид связанного списка и динамического массива. Он выделяет меньше ресурсов, чем связанный список, и содержит меньше указателей, хотя в худшем случае использование пространства немного выше. Возможно, вы также захотите взглянуть на списки чанков, которые являются еще одним гибридом массивов и связанных списков, которые можно использовать как для стеков, так и для очередей.
Надеюсь, это поможет!