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

Возможный дубликат:
Зачем использовать два стека для очереди?

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

Ответ 1

Есть несколько очень веских причин для этого.

Во-первых, некоторые функциональные языки программирования, такие как Haskell, ML или Lisp поддерживают списки как встроенный тип. Списки обычно представляются в виде отдельных списков с прямой связью, что означает, что они поддерживают O (1), но O (n) объединяются. В таких языках, как это, очень легко сделать стек - вы просто добавляете в список, чтобы нажимать и удалять первый элемент для попса. Из-за внутренней реализации это выполняется в O (1) раз. Если вы попытались сделать очередь, используя этот список, то в очереди будет время O (n), потому что вам нужно будет добавить к концу односвязный список, который не сохранит указатель на последний элемент. С другой стороны, если вы реализуете очередь, используя два стека (или больше, очередь Hood-Melville использует шесть!), То вы можете получите амортизацию O (1) в очереди и dequeue, даже если у вас есть только стеки на вашем языке. Хотя были созданы более сложные структуры данных для поддержки чисто функциональных очередей и списков (например, 2-3 пальца), два стека конструкция по-прежнему весьма полезна во многих приложениях.

В дополнение к этому, в некоторых случаях вы можете использовать специальные стеки для реализации очереди, чтобы получить дополнительную функциональность. Например, вы можете увеличить структуру данных стека для поддержки O (1) find-min/find-max. Если у вас есть такой стек, вы можете использовать конструкцию из двух стеков для создания очереди, которая также имеет O (1) find-min/find-max. Попытка решить эту проблему напрямую намного сложнее (проверьте мою значительно более сложную конструкцию, чтобы сделать очередь с этими свойствами!)

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

Надеюсь, это поможет!