Как реализовать очередь из трех стеков?

Question

Я сталкивался с этим вопросом в книге алгоритмов ( Алгоритмы, 4-е издание Роберта Седжвика и Кевина Уэйна).

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

Я знаю, как создать очередь с 2 стеками, но не могу найти решение с 3 стеками. Любая идея ?

(о, а это не домашняя работа :))

Answer 1

РЕЗЮМЕ

• O (1) алгоритм известен для 6 стеков
• O (1) алгоритм известен для 3 стеков, но использует ленивую оценку, которая на практике соответствует наличию дополнительных внутренних структур данных, поэтому он не является решением
• Люди возле Седжвика подтвердили, что не знают о решении с 3 стеками во всех ограничениях исходного вопроса

ОПИСАНИЕ

За этой ссылкой есть две реализации: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Одним из них является O (1) с тремя стеками, НО он использует отложенное выполнение, что на практике создает дополнительные промежуточные структуры данных (замыкания).

Еще один из них - O (1), но использует SIX стеки. Тем не менее, он работает без ленивого исполнения.

ОБНОВЛЕНИЕ: статья Окасаки здесь: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps, и кажется, что он фактически использует только 2 стека для версии O (1), которая имеет ленивую оценку. Проблема в том, что он действительно основан на ленивой оценке. Вопрос в том, можно ли его преобразовать в алгоритм 3-стека без ленивых вычислений.

ОБНОВЛЕНИЕ: еще один связанный алгоритм описан в статье Хольгера Петерсена «Стеки против требований», опубликованной на 7-й ежегодной конференции по вычислительной технике и комбинаторике. Вы можете найти статью из Google Книг. Проверьте страницы 225-226. Но на самом деле алгоритм - это не симуляция в реальном времени, а симуляция двусторонней очереди с тремя стеками в линейном времени.

gusbro: "Как @Leonel сказал несколько дней назад, я подумал, что было бы справедливо проверить у профессора Седжвика, знает ли он решение или была ли какая-то ошибка. Поэтому я написал ему. Я только что получил ответ ( хотя и не от себя, а от коллеги из Принстона), поэтому я хотел бы поделиться со всеми вами. Он в основном сказал, что он не знает ни одного алгоритма, использующего три стека И другие наложенные ограничения (например, не использующие ленивую оценку). Он знал о алгоритм, использующий 6 стеков, как мы уже знаем, глядя на ответы здесь. Поэтому я думаю, что вопрос все еще открыт, чтобы найти алгоритм (или доказать, что он не может быть найден). "

Answer 2

Хорошо, это действительно сложно, и единственное решение, которое я мог придумать, помнит меня о решении Киркса для теста Кобаяси Мару (каким-то образом обманутым): Идея в том, что мы используем стек стеков (и используем его для моделирования списка). Я вызываю операции en / dequeue и push и pop, тогда мы получаем:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

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

И да, я знаю его argueable, потому что у нас есть неявное более 3 стеков, но, возможно, это даст другим о вас хорошие идеи.

РЕДАКТИРОВАТЬ: Пример объяснения:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Я попробовал здесь с небольшим ASCII-искусством показать Stack1.

Каждый элемент упакован в один стек элементов (поэтому у нас есть только стеки безопасных стеков).

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

Esp tricky - это вставка, так как вам нужно как-то погрузиться глубоко во вложенные стеки, чтобы добавить еще один элемент. Вот почему Stack2 там. Stack2 всегда самый внутренний стек. Добавление - это просто вставить элемент внутрь, а затем вставить новый Stack2 (и поэтому нам не разрешается касаться Stack2 в нашей операции удаления очереди).

Answer 3

Я собираюсь попробовать доказательство, чтобы показать, что это не может быть сделано.

---

Предположим, существует очередь Q, которая моделируется 3 стеками, A, B и C.

Утверждения

• ASRT0: = Кроме того, предположим, что Q может моделировать операции {очередь, очередь} в O (1).Это означает, что существует определенная последовательность нажатий / выталкиваний стека для каждой моделируемой операции очереди / очереди.

• Без потери общности предположим, что операции очереди являются детерминированными.

Пусть элементы, поставленные в очередь в Q, будут пронумерованы 1, 2, ..., в зависимости от их порядка очереди, причем первый элемент, помещенный в очередь в Q, определен как 1, второй - как2 и т. Д.

Определить

• Q(0) := Состояние Q, когда в Q есть 0 элементов (и, следовательно, 0 элементов в A, B и C)
• Q(1) := Состояние Q (и A, B и C) после 1 операции очереди на Q(0)
• Q(n) := Состояние Q (и A, B и C) после nоперации с очередями в Q(0)

Определить

• |Q(n)| := количество элементов в Q(n) (следовательно, |Q(n)| = n)
• A(n) := состояние стека A, когда состояние Q равно Q(n)
• |A(n)| := количество элементов в A(n)

И аналогичные определения длястеки B и C.

Тривиально,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| явно неограничен на n.

Следовательно, по крайней мере один из |A(n)|, |B(n)|или |C(n)| не ограничено по n.

WLOG1, предположим, что стек A неограничен, а стеки B и C. ограничены.

Определите * B_u := верхнюю границу B * C_u := верхняя граница C * K := B_u + C_u + 1

WLOG2, для n такого, что |A(n)| > K, выберите K элементов из Q(n).Предположим, что 1 из этих элементов находится в A(n + x) для всех x >= 0, т.е. элемент всегда находится в стеке A независимо от того, сколько операций очереди выполнено.

• X := этот элемент

Затем мы можем определить

• Abv(n) := количество элементов в стеке A(n), которое выше X

• Blo(n) :=количество элементов в стеке A(n) ниже X

  | A (n) |= Abv (n) + Blo (n)

ASRT1 := Количество всплывающих окон, требуемых для удаления X из Q(n), составляет не менее Abv(n)

От(ASRT0) и (ASRT1), ASRT2 := Abv(n) должны быть ограничены.

Если Abv(n) не ограничен, то если для удаления X из Q(n) требуется 20 декеев, потребуетсяминимум Abv(n)/20 хлопаетКоторый неограничен.20 может быть любой константой.

Следовательно,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

должен быть неограниченным.

---

WLOG3, мы можем выбрать K элементов снизуA(n), и один из них находится в A(n + x) для всех x >= 0

X(n) := этого элемента, для любого заданного n

ASRT4 := Abv(n) >= |A(n)| - K

Всякий раз, когда элемент ставится в очередь Q(n) ...

WLOG4, предположим, что B и C уже заполнены до их верхних границ.Предположим, что верхняя граница для элементов выше X(n) была достигнута.Затем новый элемент вводит A.

WLOG5, предположим, что в результате новый элемент должен войти ниже X(n).

ASRT5 := Количество всплывающих окон, необходимое для установкиэлемент ниже X(n) >= Abv(X(n))

Начиная с (ASRT4), Abv(n) не ограничен по n.

Следовательно, число всплывающих окон, необходимое для помещения элемента ниже X(n), не ограничено.

---

Это противоречит ASRT1, поэтому невозможно смоделировать очередь O(1) с 3 стеками.

---

Т.е.

Как минимум 1стек должен быть неограниченным.

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

Однако,если число элементов над ним ограничено, то оно достигнет предела.В какой-то момент новый элемент должен войти под ним.

Поскольку мы всегда можем выбрать старый элемент из числа одного из самых нижних элементов этого стека, над ним может быть неограниченное количество элементов (в зависимости от неограниченного размера неограниченного стека).

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

И, таким образом, противоречие.

---

Существует 5 операторов WLOG (без потери общности). В некотором смысле, они могут быть интуитивно поняты, чтобы быть правдой (но, учитывая, что они 5, это может занять некоторое время). Формальное доказательство того, что общность не потеряна, может быть получено, но оно чрезвычайно длинное. Они опущены.

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

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

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

Answer 4

Примечание: это комментарий к функциональной реализации очередей в реальном времени (наихудший случай с постоянным временем) с односвязными списками.Я не могу добавлять комментарии из-за своей репутации, но было бы хорошо, если бы кто-то мог изменить это на комментарий, добавленный к ответу antti.huima.Опять же, это несколько длинно для комментария.

@antti.huima: Связанные списки не совпадают со стеком.

• s1 = (1 2 34) --- связанный список с 4 узлами, каждый из которых указывает на один справа, и содержит значения 1, 2, 3 и 4

• s2 = popped (s1) -- s2 теперь (2 3 4)

В этот момент s2 эквивалентен popped (s1), который ведет себя как стек.Тем не менее, s1 все еще доступен для справки!

• s3 = popped (popped (s1)) --- s3 is (3 4)

Мы все еще можем заглянуть вs1, чтобы получить 1, тогда как в правильной реализации стека элемент 1 ушел из s1!

Что это значит?

• s1 - ссылка на вершину стека1026 *
• s2 - ссылка на второй элемент стека
• s3 - ссылка на третий ...

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

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

ПравитьЯ имею в виду только алгоритмы 2-го и 3-го связанных списков, использующие это свойство связанных списков, так как я их сначала прочитал (они выглядели проще).Это не означает, что они применимы или не применимы, просто чтобы объяснить, что связанные списки не обязательно идентичны.Я прочитаю один с 6, когда я свободен.@Welbog: Спасибо за исправление.

---

Лень также может имитировать функционирование указателя аналогичным образом.

---

Использование связанного списка решает другую проблему.Эту стратегию можно использовать для реализации очередей в реальном времени в Лиспе (или, по крайней мере, в Лиспе, который настаивает на построении всего из связанных списков): обратитесь к разделу «Операции с очередями в реальном времени в чистом Лиспе» (связан с ссылками antti.huima).Это также хороший способ создания неизменяемых списков с O (1) временем работы и общими (неизменяемыми) структурами.

Answer 5

Вы можете сделать это в амортизированном постоянном времени с двумя стеками:

------------- --------------
            | |
------------- --------------

Добавление - O(1), удаление - O(1), если сторона, с которой вы хотите взять, не пуста, и O(n) в противном случае (разбейте другой стек на две части).

Хитрость заключается в том, чтобы увидеть, что операция O(n) будет выполняться только каждый раз O(n) (если вы разделитесь, например, пополам). Следовательно, среднее время для операции составляет O(1)+O(n)/O(n) = O(1).

Хотя это может показаться проблемой, если вы используете императивный язык со стеком на основе массива (самый быстрый), вы все равно будете иметь только амортизированное постоянное время.