Два стека с deque, какова цель его реализации?

Question

От Алгоритмы 4-й :

1.3.48 Два стека с декой.Реализуйте два стека с одной декой, чтобы каждая операция занимала постоянное число операций деке (см. Упражнение 1.3.33).

Что означает реализация 2 стеков с одним деком?Есть практические причины?Почему бы мне не создать 2 стека напрямую?

---

1.3.49 Очередь с тремя стеками.Реализуйте очередь с тремя стеками, чтобы каждая операция очереди занимала постоянное (в худшем случае) количество операций стека.Предупреждение: высокая степень сложности.

Смежный вопрос: Как реализовать очередь из трех стеков?

Кроме того, зачем мне нужно реализовывать очередьс тремя стеками?Разве я не могу просто создать очередь напрямую?

Answer 1

Кажется, что нет практического использования для этих реализаций.

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

(возможно, вторичная цель - научить программиста реализовывать смешные видениябосса:))

Answer 2

Стеки из Deques

Стеки - это структуры с первым и последним выходом.Deques позволяет вам толкать / выталкивать как спереди, так и сзади.Если вы отслеживаете количество элементов, которые вы сохранили в передней / задней части, то вы можете использовать переднюю часть как одну стопку, а заднюю часть как другую, возвращая элементы NULL, если ваши счетчики обнуляются.

Почему вы бы это сделали?Кто знает, но читайте дальше.

Очереди из стеков

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

Почему хотите ли вы сделать это?

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

Непосредственно реализовать очередь сложнее ...Вы добавляете предметы к одному концу, но вытягиваете их с другого.Два стека дают вам возможность сделать это.

Но почему 3 очереди?

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

Вам не нужен грубый алгоритм, который дает непредсказуемую производительность.

Вам нужны гарантии.

В этом ответе StackOverflow объясняется, что решение с 3 стеками неизвестно, но существует решение с 6 стеками.

Почему стеки от запросов

Вернемся к первому вопросу.Как мы уже видели, есть веские причины, чтобы иметь возможность строить очереди из стеков.Для компьютера это естественный способ построения сложной структуры данных из простой.Это может даже дать нам гарантии производительности.

Стеки из Dequeues не кажутся мне практичными в работе с компьютером.Но информатика не о компьютерах;речь идет о поиске эффективных алгоритмических решений проблем.Может быть, вы храните материал на разнонаправленном ленточном конвейере на заводе.Вы можете запрограммировать ремень так, чтобы он действовал как деку, и используйте деку для создания стеков.В этом контексте вопрос имеет больше смысла.

Answer 3

Эта первая проблема больше похожа на упражнение, чем на что-либо еще.Я сомневаюсь, что во многих случаях вы хотели бы реализовать два стека, используя одну деку, хотя я счастлив, что оказался неправ.Я думаю, что цель вопроса, однако, состоит в том, чтобы заставить вас задуматься о «геометрии» блогов и стеков.Есть действительно красивое решение проблемы, которое довольно изящно, и если вы увидите, как оно работает, оно даст вам более глубокое понимание того, как работают все эти типы.

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

Но опять же, в обоих случаях они в основном предназначены для упражнений, которые помогут вам лучше понять основы.Вы бы на самом деле сделали что-нибудь из этого на практике?Вероятно, нет - какой-то дизайнер библиотеки, скорее всего, сделает это за вас.Но даст ли вам выполнение этих упражнений гораздо более глубокое понимание того, как работают эти типы данных, с какими вещами они хороши и плохи, а также с пониманием того, как должны работать разработчики библиотек?Да, полностью!