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

34

У меня следующий домашний вопрос:

Реализуйте методы стека push (x) и pop (), используя две очереди.

Это кажется мне странным, потому что:

  • Стек - это очередь (LIFO)
  • Я не понимаю, зачем вам нужно две очереди для его реализации

Я искал вокруг:

и нашел пару решений. Вот чем я закончил:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Но я не понимаю, в чем преимущество использования одной очереди; версия с двумя очередями кажется бессмысленно сложной.

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

Я что-то пропустил? Любое понимание здесь будет оценено.

Carcigenicate
источник
17
Очередь обычно ссылается на структуру FIFO, в то время как стек является структурой LIFO. Интерфейс для LinkedList в Java - это интерфейс deque (двусторонняя очередь), который обеспечивает доступ как к FIFO, так и к LIFO. Попробуйте изменить программирование на интерфейс очереди, а не на реализацию LinkedList.
12
Более обычная проблема - реализовать очередь с использованием двух стеков. Вы можете найти книгу Криса Окасаки о чисто функциональных структурах данных интересной.
Эрик Липперт
2
Основываясь на том, что сказал Эрик, вы можете иногда оказаться на языке, основанном на стеке (таком как dc или автомат с двумя стеками (эквивалентно машине Тьюринга, потому что, ну, вы можете сделать больше)), где вы можете оказаться с несколько стеков, но без очереди.
1
@MichaelT: или вы также можете запустить процессор на базе стека
slebetman
11
"Стек - это очередь (LIFO)" ... хм, очередь - это очередь ожидания. Как линия для использования общественного туалета. Ли линии, в которых вы ждете, когда-либо ведут себя в стиле LIFO? Прекратите использовать термин «очередь LIFO», это бессмысленно.
Мердад

Ответы:

44

В этом нет никакого преимущества: это чисто академическое упражнение.

Очень давно , когда я был на первом курсе в колледже , у меня была подобная упражнение 1 . Цель состояла в том, чтобы научить студентов использовать объектно-ориентированное программирование для реализации алгоритмов вместо написания итерационных решений с использованием forциклов со счетчиками циклов. Вместо этого комбинируйте и повторно используйте существующие структуры данных для достижения ваших целей.

Вы никогда не будете использовать этот код в Real World TM . То, что вам нужно убрать из этого упражнения, это как «мыслить нестандартно» и повторно использовать код.


Обратите внимание, что вы должны использовать интерфейс java.util.Queue в своем коде, а не использовать реализацию напрямую:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Это позволяет вам Queueпри желании использовать другие реализации, а также скрывать 2 включенных метода, LinkedListкоторые могут обойти дух Queueинтерфейса. Это включает get(int)и pop()(в то время как ваш код компилируется, там есть логическая ошибка, учитывая ограничения вашего назначения. Объявление ваших переменных Queueвместо того, LinkedListчтобы показывать это). Связанное чтение: Понимание «программирования на интерфейсе» и Почему интерфейсы полезны?

1 Я до сих пор помню: упражнение было отменить Stack , используя только методы интерфейса Stack и никаких служебных методов java.util.Collectionsили другие «статической только» полезные классы. Правильное решение предполагает использование других структур данных в качестве объектов временного хранения: вы должны знать различные структуры данных, их свойства и как их комбинировать, чтобы сделать это. Поставил в тупик большую часть моего класса CS101, который никогда не программировал раньше.

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

Сообщество
источник
1
Спасибо. Я думаю, это имеет смысл. Я также понял, что я использую «незаконные» операции в приведенном выше коде (выдвигая на передний план FIFO), но я не думаю, что это что-то меняет. Я отменил все операции, и это все еще работает как задумано. Я собираюсь немного подождать, прежде чем согласиться, так как я не хочу отговаривать других людей от участия. Однако, спасибо.
Carcigenicate
19

Там нет никакого преимущества. Вы правильно поняли, что использование очередей для реализации стека приводит к ужасной сложности времени. Ни один (компетентный) программист никогда не будет делать что-то подобное в «реальной жизни».

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

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

На самом деле, это отличное упражнение. Я должен сделать это сам прямо сейчас :)

Амон
источник
3
@JohnKugelman Спасибо за ваше редактирование, но я действительно имел в виду «ужасная сложность времени». Для связанного списка на основе стека push, peekи popоперации в O (1). То же самое для стека с изменяемым размером массива, за исключением того, что pushв O (1) амортизируется с O (n) в худшем случае. По сравнению с этим стек на основе очередей значительно уступает O (n) push, O (1) pop и peek или, альтернативно, O (1) push, O (n) pop и peek.
Амон
1
«ужасное время сложность» и «значительно хуже» не совсем верно. Амортизированная сложность по-прежнему равна O (1) для push и pop. В TAOCP есть забавный вопрос (vol1?) Об этом (в основном вы должны показать, что число раз, которое элемент может переключаться из одного стека в другой, является постоянным). В худшем случае производительность для одной операции отличается, но тогда я редко слышу, чтобы кто-нибудь говорил о производительности O (N) для push в ArrayLists - обычно не интересное число.
Во
5

Определенно есть реальная цель сделать очередь из двух стеков. Если вы используете неизменяемые структуры данных из функционального языка, вы можете вставить в стек многоразовых элементов и извлечь из списка доступных объектов. Poppable элементы создаются, когда все элементы извлечены, и новый poppable стек является обратным стеку pushable, где новый pushable стек теперь пуст. Это эффективно.

Что касается стека из двух очередей? Это может иметь смысл в контексте, где у вас есть куча больших и быстрых очередей. Это определенно бесполезно в качестве такого рода упражнений на Java. Но это может иметь смысл, если это каналы или очереди сообщений. (то есть: N сообщений, поставленных в очередь, с помощью операции O (1) для перемещения (N-1) элементов впереди в новую очередь.)

обкрадывать
источник
Хм ... это заставило меня задуматься об использовании сдвиговых регистров в качестве основы для вычислений и об архитектуре ленточных /
фрезерных станков
Вау, процессор Mill действительно интересен. «Очередная машина» точно.
Роб
2

Осуществление является неоправданно ухитрился с практической точки зрения. Суть в том, чтобы заставить умно использовать интерфейс очереди для реализации стека. Например, ваше решение «Одна очередь» требует, чтобы вы перебирали очередь, чтобы получить последнее входное значение для операции «pop» стека. Однако структура данных очереди не позволяет перебирать значения, вам разрешен доступ к ним в порядке поступления (FIFO).

Destruktor
источник
2

Как уже отмечали другие: реального преимущества нет.

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

В Java даже Queueинтерфейс имеет size()метод, и все стандартные реализации этого метода - O (1).

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

В этом случае size()O (n) и его следует избегать в циклах. Или реализация непрозрачна и обеспечивает только минимум add()и remove().

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

Тем не менее, если вы живете на Java-земле, то вряд ли это что-то придумает.

Thraidh
источник
Хорошая мысль о size()методе. Тем не менее, в отсутствие метода O (1) size()для стека тривиально отслеживать его текущий размер. Ничего, чтобы остановить реализацию одной очереди.
мастер
Все зависит от реализации. Если у вас есть очередь, реализованная только с указателями вперед и указателями на первый и последний элемент, вы все равно можете написать и алгоритм, который удаляет элемент, сохраняет его в локальной переменной, добавляет элемент ранее в этой переменной в ту же очередь до тех пор, пока первый элемент виден снова. Это работает, только если вы можете однозначно идентифицировать элемент (например, через указатель), а не просто что-то с тем же значением. O (n) и использует только add () и remove (). В любом случае, проще оптимизировать, чтобы найти причину для этого, кроме размышлений об алгоритмах.
Thraidh
0

Трудно представить себе применение такой реализации, это правда. Но главное - доказать, что это можно сделать .

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

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

Ложка
источник