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

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

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

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

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

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

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

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

Модератор закройте тему.
Всегда хотел это сказать.

0

Сообщение от Zedapp Возможность перемещаться по стеку лишь в одном направлении,

по стеку а равно по очереди вообще нельзя перемещаться , только положил/ снял

1

Сообщение от ValeryS нельзя перемещатьс

Я имел ввиду, что допустим если есть необходимость проверить, есть ли данный элемент в стеке не доставая его.

0

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

Добавлено через 12 минут
по теме
1) очередь динамическим массивом. полная лажа, или я чет не понял. если у нас есть еще хотя бы 2 указателя : на последний элемент очереди и на первый, и они постоянно меняются, то это еще куда ни шло, а если есть просто массив и мы считаем что [0] элемент он первый, а какой - то там последний, то каждое извлечение элемента (только первого естественно) влечет за собой копирование всех остальных назад на 1 это жуть какая то получается, или это влечет за собой выделение нового массива длиной н-1, копирование туда и удаление старого?
из плюсов: памяти нужно ровно столько, сколько весят данные
2) стек односвязным списком - все по науке
минусы - чуть больше памяти
3) тоже что с очередью, я не понимаю что именно они имеют ввиду, если есть указатели дополнительные, то все не так плохо, если нет то беда

1

Недостатки стека через динам. массив:
-одной из основных преимуществом массива над указателями является обращение элемента по индексу, в стеке такой функции не должно быть
-добавление в стек происходит в голову и из неё же извлекается, т.е. идет работа с 1 элементом. Теперь конкретней: при добавлении в стек реализованном через указатели нужно будет создать только 1 указатель, выделить под него память и связать со стеком, итого не в зависимости сколько элементов в текущем стеке мы выделяем память только под 1 элемент. В динам. массиве для добавления 1го элемента придется целиком перевыделять память для всего массива, т.е. есть стек на 100000 элементов и чтобы добавить 1 элемент нужно перевыделить 100001 элементов, итого мы имеем большие косяки по памяти.

Тоже самое с очередью и деком

1