Предположим, у нас есть два стека и нет другой временной переменной.
Можно ли «построить» структуру данных очереди, используя только два стека?
Предположим, у нас есть два стека и нет другой временной переменной.
Можно ли «построить» структуру данных очереди, используя только два стека?
Держите 2 стека, давайте их назовем inbox
и outbox
.
Ставить в очередь :
inbox
Dequeue :
Если outbox
пусто, заполните его, inbox
вытолкнув каждый элемент из и нажав его наoutbox
Взять и вернуть верхний элемент из outbox
Используя этот метод, каждый элемент будет в каждом стеке ровно один раз - это означает, что каждый элемент будет помещен дважды и вытолкнут дважды, что приведет к амортизации операций с постоянным временем.
Вот реализация в Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
A - Как перевернуть стек
Чтобы понять, как построить очередь с использованием двух стеков, вы должны понимать, как полностью изменить стековую последовательность. Помните, как работает стек, это очень похоже на стек блюдо на вашей кухне. Последнее промытый блюдо будет на вершине стека чистой, который называется L AST я п Р рвые вывода ут (LIFO) в области вычислительной техники.
Давайте представим наш стек как бутылку, как показано ниже;
Если мы вставим целые числа 1,2,3 соответственно, то 3 будет на вершине стека. Поскольку 1 будет помещен первым, затем 2 будет помещен на вершину 1. Наконец, 3 будет помещен на вершину стека, и последнее состояние нашего стека, представленное в виде бутылки, будет таким, как показано ниже;
Теперь наш стек представлен в виде бутылки, заполненной значениями 3,2,1. И мы хотим перевернуть стек так, чтобы верхний элемент стека был 1, а нижний элемент стека был 3. Что мы можем сделать? Мы можем взять бутылку и держать ее вверх дном, чтобы все значения перевернулись по порядку?
Да, мы можем сделать это, но это бутылка. Чтобы сделать тот же процесс, нам нужен второй стек, который будет хранить первые элементы стека в обратном порядке. Давайте поместим наш заполненный стек слева, а наш новый пустой стек - справа. Чтобы изменить порядок элементов, мы собираемся вытолкнуть каждый элемент из левого стека и поместить их в правый стек. Вы можете видеть, что происходит, как мы делаем, на изображении ниже;
Итак, мы знаем, как перевернуть стек.
B - Использование двух стеков в качестве очереди
В предыдущей части я объяснил, как мы можем изменить порядок элементов стека. Это было важно, потому что если мы помещаем элементы в стек, и выводим их, то результат будет точно в обратном порядке очереди. Думая на примере, давайте поместим массив целых чисел
{1, 2, 3, 4, 5}
в стек. Если мы вытолкнем элементы и распечатаем их до тех пор, пока стек не станет пустым, мы получим массив в порядке, обратном порядку проталкивания.{5, 4, 3, 2, 1}
Помните, что для того же ввода, если мы снимаем очередь с очереди до тех пор, пока очередь не станет пустой, вывод будет{1, 2, 3, 4, 5}
. Таким образом, очевидно, что для одного и того же порядка ввода элементов вывод очереди в точности противоположен выводу стека. Поскольку мы знаем, как перевернуть стек, используя дополнительный стек, мы можем построить очередь, используя два стека.Наша модель очереди будет состоять из двух стеков. Один стек будет использоваться для
enqueue
операции (стек № 1 слева, будет называться входным стеком), другой стек будет использоваться дляdequeue
операции (стек № 2 справа будет называться выходным стеком). Проверьте изображение ниже;Наш псевдокод, как показано ниже;
Операция постановки в очередь
Операция Dequeue
Давайте поставим в очередь целые числа
{1, 2, 3}
соответственно. Целые числа будут помещены в стек ввода ( стек № 1 ), который расположен слева;Что произойдет, если мы выполним операцию удаления очереди? Всякий раз, когда выполняется операция удаления очереди, очередь будет проверять, является ли стек вывода пустым или нет (см. Псевдокод выше). Если стек вывода пуст, то стек вывода будет извлечен на выходе, чтобы элементы стека ввода будет полностью изменен. Перед возвратом значения состояние очереди будет таким, как показано ниже;
Проверьте порядок элементов в стеке вывода (стек № 2). Очевидно, что мы можем вытолкнуть элементы из стека вывода, чтобы вывод был таким же, как если бы мы исключили его из очереди. Таким образом, если мы выполним две операции удаления очереди, сначала мы получим
{1, 2}
соответственно. Тогда элемент 3 будет единственным элементом выходного стека, а входной стек будет пустым. Если мы поставим в очередь элементы 4 и 5, то состояние очереди будет следующим;Теперь выходной стек не пустой, и если мы выполним операцию удаления очереди, из выходного стека будет выведено только 3. Тогда состояние будет видно как показано ниже;
Опять же, если мы выполним еще две операции удаления очереди, при первой операции удаления очереди очередь проверит, пуст ли стек вывода, что является истиной. Затем извлеките элементы стека ввода и вставьте их в стек вывода, пока стек ввода не будет пуст, тогда состояние очереди будет таким, как показано ниже;
Легко увидеть, результат двух операций удаления очереди будет
{4, 5}
C - Реализация очереди, построенной с двумя стеками
Вот реализация в Java. Я не собираюсь использовать существующую реализацию стека, поэтому пример здесь будет изобретать колесо;
C - 1) Класс MyStack: реализация простого стека
C - 2) Класс MyQueue: реализация очереди с использованием двух стеков
C - 3) Демо-код
C - 4) Пример вывода
источник
Вы даже можете смоделировать очередь, используя только один стек. Второй (временный) стек может быть смоделирован стеком рекурсивных вызовов метода вставки.
Принцип остается неизменным при вставке нового элемента в очередь:
Класс Queue, использующий только один стек, будет выглядеть следующим образом:
источник
n items
в очередь с использованием вышеуказанной структуры данных. сумма в(1 + 2 + 4 + 8 + .... + 2(n-1))
результате~O(n^2)
. Я надеюсь, вы поняли суть.Однако временные сложности были бы еще хуже. Хорошая реализация очереди делает все в постоянное время.
редактировать
Не уверен, почему мой ответ был опущен здесь. Если мы программируем, мы заботимся о сложности времени, и использование двух стандартных стеков для создания очереди неэффективно. Это очень актуальный и актуальный момент. Если кто-то еще будет нуждаться в этом, мне было бы интересно узнать почему.
Немного подробнее : о том, почему использование двух стеков хуже, чем просто очередь: если вы используете два стека, и кто-то вызывает dequeue, когда исходящий ящик пуст, вам нужно линейное время, чтобы добраться до дна входящего почтового ящика (как вы можете видеть в коде Дэйва).
Вы можете реализовать очередь в виде односвязного списка (каждый элемент указывает на следующий вставленный элемент), сохраняя дополнительный указатель на последний вставленный элемент для толчков (или делая его циклическим списком). Реализация очереди и очереди для этой структуры данных очень проста в постоянном времени. Это наихудшее постоянное время, не амортизируется. И, как кажется, комментарии просят об этом разъяснении, постоянное время в худшем случае строго лучше, чем амортизированное постоянное время.
источник
Пусть реализуемая очередь будет q, а стеки, используемые для реализации q, будут stack1 и stack2.
q может быть реализовано двумя способами:
Способ 1 (сделав операцию enQueue дорогостоящей)
Этот метод гарантирует, что вновь введенный элемент всегда находится на вершине стека 1, так что операция deQueue просто появляется из stack1. Чтобы поместить элемент в верхнюю часть stack1, используется stack2.
Способ 2 (делая операцию deQueue дорогостоящей)
В этом методе при работе в очереди новый элемент вводится вверху stack1. В операции удаления очереди, если стек2 пуст, тогда все элементы перемещаются в стек2 и, наконец, возвращается вершина стека2.
Метод 2 определенно лучше, чем метод 1. Метод 1 перемещает все элементы дважды в операции enQueue, в то время как метод 2 (в операции deQueue) перемещает элементы один раз и перемещает элементы, только если stack2 пуст.
источник
Решение в C #
источник
Два стека в очереди определены как stack1 и stack2 .
Enqueue: euqueued элементы всегда помещаются в stack1
Исключение: вершина stack2 может быть выдвинута , так как это первый элемент, вставленный в очередь, когда stack2 не пуст. Когда stack2 пуст, мы извлекаем все элементы из stack1 и помещаем их в stack2 один за другим. Первый элемент в очереди помещается в нижнюю часть stack1 . Он может быть выведен сразу после операций выталкивания и нажатия, поскольку он находится на вершине стека2 .
Ниже приведен пример кода C ++:
Это решение позаимствовано из моего блога . Более подробный анализ с пошаговым моделированием работы доступен на моей странице в блоге.
источник
Вы должны вытолкнуть все из первого стека, чтобы получить нижний элемент. Затем поместите их все обратно во второй стек для каждой операции "удаления очереди".
источник
для разработчика на c # вот полная программа:
источник
Реализуйте следующие операции очереди с использованием стеков.
push (x) - Нажмите элемент x в конец очереди.
pop () - удаляет элемент перед очередью.
peek () - получить передний элемент.
empty () - Возвращает, пуста ли очередь.
источник
источник
Реализация очереди с использованием двух стеков в Swift:
источник
В то время как вы получите много сообщений, связанных с реализацией очереди с двумя стеками: 1. Либо сделав процесс enQueue намного более дорогостоящим 2. Или сделав процесс deQueue намного более дорогостоящим
https://www.geeksforgeeks.org/queue-using-stacks/
Один важный способ, который я узнал из вышеприведенного поста, - это создание очереди только со структурой данных стека и стеком рекурсивных вызовов.
Хотя можно утверждать, что буквально это все еще использует два стека, но в идеале это использует только одну структуру данных стека.
Ниже приводится объяснение проблемы:
Объявите один стек для обработки и удаления данных и поместите данные в стек.
в то время как у deQueueing есть базовое условие, при котором элемент стека выскакивает, когда размер стека равен 1. Это обеспечит отсутствие переполнения стека во время рекурсии deQueue.
В то время как deQueueing сначала вытолкнуть данные из верхней части стека. В идеале этот элемент будет элементом, который присутствует в верхней части стека. Теперь, когда это будет сделано, рекурсивно вызовите функцию deQueue, а затем вставьте элемент, расположенный выше, обратно в стек.
Код будет выглядеть ниже:
Таким образом, вы можете создать очередь, используя единую структуру данных стека и стек вызовов рекурсии.
источник
Ниже представлено решение на языке javascript с использованием синтаксиса ES6.
Stack.js
QueueUsingTwoStacks.js
Ниже использование:
index.js
источник
stack1
. Когда вы вернетесь к нимdequeue
снова, выstack2
поместите в них предметы , опередив их там, где они уже были.Я отвечу на этот вопрос в Go, потому что в стандартной библиотеке Go нет большого количества коллекций.
Так как стек очень прост в реализации, я решил попробовать использовать два стека для создания двусторонней очереди. Чтобы лучше понять, как я пришел к своему ответу, я разделил реализацию на две части. Надеемся, что первую часть легче понять, но она неполна.
В основном это два стека, где мы позволяем друг другу манипулировать основанием стеков. Я также использовал соглашения об именах STL, в которых традиционные операции стека push, pop, peek имеют префикс front / back независимо от того, ссылаются ли они на начало или конец очереди.
Проблема с приведенным выше кодом заключается в том, что он не очень эффективно использует память. На самом деле, он растет бесконечно, пока вы не исчерпаете пространство. Это действительно плохо. Решением этой проблемы является простое повторное использование нижней части пространства стека, когда это возможно. Мы должны ввести смещение для отслеживания этого, так как срез в Go не может расти в передней части после сокращения.
Это много маленьких функций, но из 6 функций три из них являются просто зеркалами другой.
источник
Вот мое решение в Java с использованием связанного списка.
}
Примечание. В этом случае операция pop занимает очень много времени. Поэтому я не буду предлагать создавать очередь, используя два стека.
источник
С
O(1)
dequeue()
, что совпадает с ответом pythonquick :С
O(1)
enqueue()
(это не упомянуто в этом посте, поэтому этот ответ), который также использует возврат, чтобы всплыть и вернуть самый нижний элемент.Очевидно, это хорошее упражнение по кодированию, поскольку оно неэффективно, но, тем не менее, элегантно
источник
** Простое решение JS **
источник
Для каждой операции добавления в очередь мы добавляем в начало стека 1. Для каждой очереди мы опускаем содержимое стека 1 в стек 2 и удаляем элемент в верхней части стека. Сложность времени O (n) для очереди, так как мы должны скопировать stack1 в stack2. временная сложность enqueue такая же, как и у обычного стека
источник
if (stack2 != null)
всегда имеет значение true, посколькуstack2
создается в конструкторе.Реализация очереди с использованием двух объектов java.util.Stack:
источник
return inbox.isEmpty() && outbox.isEmpty()
иreturn inbox.size() + outbox.size()
, соответственно. Код Дэйва Л. уже выдает исключение, когда вы выходите из пустой очереди. Первоначальный вопрос был даже не о Java; это было о структурах данных / алгоритмах в целом. Реализация Java была просто дополнительной иллюстрацией.