Обсуждение:Очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{tick}} Добавить реализацию на двух стеках.
+
{{tick|ticked=1}} Добавить реализацию на двух стеках.
 
:Если уж добавлять, то нужно оформить, как и остальные реализации (к примеру, добавить "операции выполняются за <tex>O(1)</tex>" и плюсы/минусы).
 
:Если уж добавлять, то нужно оформить, как и остальные реализации (к примеру, добавить "операции выполняются за <tex>O(1)</tex>" и плюсы/минусы).
 
:Хм. А почему медленнее-то? Не понятно.
 
:Хм. А почему медленнее-то? Не понятно.

Версия 17:07, 14 марта 2012

Добавить реализацию на двух стеках.

Если уж добавлять, то нужно оформить, как и остальные реализации (к примеру, добавить "операции выполняются за [math]O(1)[/math]" и плюсы/минусы).
Хм. А почему медленнее-то? Не понятно.
И, да, как я понимаю, в реализации на массивах O(1) амортизированное, а не истинное (из-за необходимости перевыделения памяти).

Ну, во-первых. В плюсах и минусах написан какой-то трешак местами. Примеры:

  • Плюсы реализации на массиве могут повторяться как минусы реализации на списке, что не есть хорошо, я думаю.
  • «размер очереди ограничен лишь объемом памяти» — корявая фраза. Размер очереди у нас в обоих случаях ничем не ограничен.

В общем, советую проверить и то, что неверно, выкинуть. В минусы реализации на списке нужно добавить тот факт, что в таком варианте память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди на массиве. Советую вообще дать прочитать этот конспект какому-нибудь хоть чуть-чуть шарящему человеку, дабы вычистить фактические ошибки (FIFO - не стратегия, а принцип) и ошибки согласования («Для реализации очереди на списке этого необходимо создать список»). Стоит оформить ссылки в соответствии с требованиями (пункт 9, требования к оформлению источников). Что такое «динамическое множество»? В псевдокоде реализации на двух стеках в операции push второй if не нужен.