У меня следующий домашний вопрос:
Реализуйте методы стека 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)
; но версия с одной очередью была бы значительно проще. Это должно потребовать только один цикл.
Я что-то пропустил? Любое понимание здесь будет оценено.
Ответы:
В этом нет никакого преимущества: это чисто академическое упражнение.
Очень давно , когда я был на первом курсе в колледже , у меня была подобная упражнение 1 . Цель состояла в том, чтобы научить студентов использовать объектно-ориентированное программирование для реализации алгоритмов вместо написания итерационных решений с использованием
for
циклов со счетчиками циклов. Вместо этого комбинируйте и повторно используйте существующие структуры данных для достижения ваших целей.Вы никогда не будете использовать этот код в Real World TM . То, что вам нужно убрать из этого упражнения, это как «мыслить нестандартно» и повторно использовать код.
Обратите внимание, что вы должны использовать интерфейс java.util.Queue в своем коде, а не использовать реализацию напрямую:
Это позволяет вам
Queue
при желании использовать другие реализации, а также скрывать 2 включенных метода,LinkedList
которые могут обойти духQueue
интерфейса. Это включаетget(int)
иpop()
(в то время как ваш код компилируется, там есть логическая ошибка, учитывая ограничения вашего назначения. Объявление ваших переменныхQueue
вместо того,LinkedList
чтобы показывать это). Связанное чтение: Понимание «программирования на интерфейсе» и Почему интерфейсы полезны?1 Я до сих пор помню: упражнение было отменить Stack , используя только методы интерфейса Stack и никаких служебных методов
java.util.Collections
или другие «статической только» полезные классы. Правильное решение предполагает использование других структур данных в качестве объектов временного хранения: вы должны знать различные структуры данных, их свойства и как их комбинировать, чтобы сделать это. Поставил в тупик большую часть моего класса CS101, который никогда не программировал раньше.2 Методы все еще существуют, но вы не можете получить к ним доступ без приведения типов или отражения. Так что нелегко использовать эти методы без очереди.
источник
Там нет никакого преимущества. Вы правильно поняли, что использование очередей для реализации стека приводит к ужасной сложности времени. Ни один (компетентный) программист никогда не будет делать что-то подобное в «реальной жизни».
Но это возможно. Вы можете использовать одну абстракцию для реализации другой, и наоборот. Стек может быть реализован с точки зрения двух очередей, а также вы можете реализовать очередь с точки зрения двух стеков. Преимущество этого упражнения :
На самом деле, это отличное упражнение. Я должен сделать это сам прямо сейчас :)
источник
push
,peek
иpop
операции в O (1). То же самое для стека с изменяемым размером массива, за исключением того, чтоpush
в O (1) амортизируется с O (n) в худшем случае. По сравнению с этим стек на основе очередей значительно уступает O (n) push, O (1) pop и peek или, альтернативно, O (1) push, O (n) pop и peek.Определенно есть реальная цель сделать очередь из двух стеков. Если вы используете неизменяемые структуры данных из функционального языка, вы можете вставить в стек многоразовых элементов и извлечь из списка доступных объектов. Poppable элементы создаются, когда все элементы извлечены, и новый poppable стек является обратным стеку pushable, где новый pushable стек теперь пуст. Это эффективно.
Что касается стека из двух очередей? Это может иметь смысл в контексте, где у вас есть куча больших и быстрых очередей. Это определенно бесполезно в качестве такого рода упражнений на Java. Но это может иметь смысл, если это каналы или очереди сообщений. (то есть: N сообщений, поставленных в очередь, с помощью операции O (1) для перемещения (N-1) элементов впереди в новую очередь.)
источник
Осуществление является неоправданно ухитрился с практической точки зрения. Суть в том, чтобы заставить умно использовать интерфейс очереди для реализации стека. Например, ваше решение «Одна очередь» требует, чтобы вы перебирали очередь, чтобы получить последнее входное значение для операции «pop» стека. Однако структура данных очереди не позволяет перебирать значения, вам разрешен доступ к ним в порядке поступления (FIFO).
источник
Как уже отмечали другие: реального преимущества нет.
В любом случае, один ответ на вторую часть вашего вопроса, почему бы просто не использовать одну очередь, выходит за рамки Java.
В Java даже
Queue
интерфейс имеетsize()
метод, и все стандартные реализации этого метода - O (1).Это не обязательно верно для наивного / канонического связанного списка, который реализует программист C / C ++, который будет просто сохранять указатели на первый и последний элемент, а каждый элемент - указатель на следующий элемент.
В этом случае
size()
O (n) и его следует избегать в циклах. Или реализация непрозрачна и обеспечивает только минимумadd()
иremove()
.При такой реализации вам нужно сначала подсчитать количество элементов, передав их во вторую очередь, перенести
n-1
элементы обратно в первую очередь и вернуть оставшийся элемент.Тем не менее, если вы живете на Java-земле, то вряд ли это что-то придумает.
источник
size()
методе. Тем не менее, в отсутствие метода O (1)size()
для стека тривиально отслеживать его текущий размер. Ничего, чтобы остановить реализацию одной очереди.Трудно представить себе применение такой реализации, это правда. Но главное - доказать, что это можно сделать .
С точки зрения фактического использования этих вещей, однако, я могу думать о двух. Одним из применений для этого является реализация систем в стесненных средах, которые не были предназначены для этого : например, блоки Redstone Minecraft, как оказалось , представляют собой систему, полную по Тьюрингу, которую люди используют для реализации логических схем и даже целых процессоров. В первые дни игр, основанных на сценариях, многие из первых игровых ботов также были реализованы таким образом.
Но вы также можете применить этот принцип в обратном направлении, гарантируя , что что - то не возможно в системе , если вы не хотите, чтобы это было . Это может возникнуть в контексте безопасности: например, мощные системы конфигурации могут быть преимуществом, но все же есть уровни мощности, которые вы, скорее всего, не предоставите пользователям. Это ограничивает то, что вы можете позволить языку конфигурации делать, чтобы злоумышленник не мог его подорвать, но в этом случае это то, что вам нужно.
источник