Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/17: Рейтинг темы: голосов - 17, средняя оценка - 5.00
Zedapp
44 / 30 / 18
Регистрация: 15.11.2014
Сообщений: 169
1

Преимущества и недостатки при реализации стека, очереди и дека через дин. массива

20.03.2015, 23:38. Просмотров 3510. Ответов 4
Метки нет (Все метки)

Доброго времени суток!

1) Назовите преимущества и недостатки реализации очереди с помощью динамического массива.
2) Назовите преимущества и недостатки реализации стека с помощью односвязного списка.
3) Назовите преимущества и недостатки реализации дека с помощью динамического массива.

1) По первому я могу лишь предположить, что будет долгое время работы в связи с тем, что необходимо будет довыделять буфер, если вдруг закончится место в массиве. Да и в принципе достаточно долго доставать элемент, если он находится в конце.
2) Ничего не придумал
3) ничего не придумал

Если есть идеи, подкиньте пожалуйста.

Добавлено через 1 час 41 минуту
UPD:

1) Достоинсва: можно не заботится, о том, что закончится память, можно быстро найти нужный элемент(например бинарным поиском если очередь отсортирована. В отличии от очереди реализованной на затрачивает меньше памяти.
Недостатки: большое время добавления элемента, если заканчивается память(из-за того, что необходима скопировать весь массив в новый буфер.
2) Достоинства: Добавление элемента всегда работает за одно и тоже время(т.к. нет необходимости компировать весь стек, если вдруг кончится память),
Недостатки: Возможность перемещаться по стеку лишь в одном направлении, что затруднит поиск необхоимого элемента, элементы списка могут располагаться в памяти разреженно, что оказывает негативный эффект на кэширование процессора.
3)Достоинства: Занимает меньше памяти, чем реализация дека с помощью списка
Недостатки: Сложнее добавлять новые элементы если реализовывать не списком.

Наверняка ещё есть что-то, но вроде должно хватить. Если что добавьте потом.

Модератор закройте тему.
Всегда хотел это сказать.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2015, 23:38
Ответы с готовыми решениями:

QuickSort и MergeSort: недостатки и преимущества
Добрый вечер! Qsort плоха тем, что в худшем случае работает за О(n^2)....

Какие преимущества и недостатки потоковых операций ввода-вывода
Здравствуйте! Какие вы знаете преимущества и недостатки потоковых операций...

Ошибка в реализации стека через односвязный список
Здравствуйте, при реализации стека через односвязный список столкнулся с...

Ошибка при реализации стека
Здравствуйте, помогите пожалуйста разобраться в ошибке.Пишу класс, в нём есть...

Ошибка исполнения при реализации стека
#include <iostream> using namespace std; struct item {int a; item*p; };...

4
ValeryS
Модератор
7265 / 5519 / 692
Регистрация: 14.02.2011
Сообщений: 18,701
20.03.2015, 23:53 2
Цитата Сообщение от Zedapp Посмотреть сообщение
Возможность перемещаться по стеку лишь в одном направлении,
по стеку а равно по очереди вообще нельзя перемещаться , только положил/ снял
1
Zedapp
44 / 30 / 18
Регистрация: 15.11.2014
Сообщений: 169
21.03.2015, 00:17  [ТС] 3
Цитата Сообщение от ValeryS Посмотреть сообщение
нельзя перемещатьс
Я имел ввиду, что допустим если есть необходимость проверить, есть ли данный элемент в стеке не доставая его.
0
sklad1002
20 / 20 / 13
Регистрация: 28.04.2013
Сообщений: 85
21.03.2015, 00:36 4
Лучший ответ Сообщение было отмечено Zedapp как решение

Решение

Zedapp, каким методом ты решил это выяснить? pop, push или peek? Ты можешь глянуть только вехний, это стек, бро

Добавлено через 12 минут
по теме
1) очередь динамическим массивом. полная лажа, или я чет не понял. если у нас есть еще хотя бы 2 указателя : на последний элемент очереди и на первый, и они постоянно меняются, то это еще куда ни шло, а если есть просто массив и мы считаем что [0] элемент он первый, а какой - то там последний, то каждое извлечение элемента (только первого естественно) влечет за собой копирование всех остальных назад на 1 это жуть какая то получается, или это влечет за собой выделение нового массива длиной н-1, копирование туда и удаление старого?
из плюсов: памяти нужно ровно столько, сколько весят данные
2) стек односвязным списком - все по науке
минусы - чуть больше памяти
3) тоже что с очередью, я не понимаю что именно они имеют ввиду, если есть указатели дополнительные, то все не так плохо, если нет то беда
1
Forrgit
5 / 5 / 6
Регистрация: 17.05.2014
Сообщений: 61
Завершенные тесты: 2
21.03.2015, 00:40 5
Недостатки стека через динам. массив:
-одной из основных преимуществом массива над указателями является обращение элемента по индексу, в стеке такой функции не должно быть
-добавление в стек происходит в голову и из неё же извлекается, т.е. идет работа с 1 элементом. Теперь конкретней: при добавлении в стек реализованном через указатели нужно будет создать только 1 указатель, выделить под него память и связать со стеком, итого не в зависимости сколько элементов в текущем стеке мы выделяем память только под 1 элемент. В динам. массиве для добавления 1го элемента придется целиком перевыделять память для всего массива, т.е. есть стек на 100000 элементов и чтобы добавить 1 элемент нужно перевыделить 100001 элементов, итого мы имеем большие косяки по памяти.

Тоже самое с очередью и деком
1
21.03.2015, 00:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2015, 00:40

Ошибки при реализации стека с помощью указателей
Нужно написать программу реализующую стек с помощью указателей, прототипы...

Зачем при реализации стека используются двухсвязные списки?
Зачем при реализации стека используются двухсвязные списки????

Непонятная ошибка при инициализации дин. массива
Вылетает на memset'е с ошибкой записи. Что неправильно? int i = 0; int j...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru