Załóżmy, że mamy dwa stosy i żadnej innej zmiennej tymczasowej.
Czy możliwe jest „skonstruowanie” struktury danych kolejki przy użyciu tylko dwóch stosów?
algorithm
data-structures
stack
queue
Nitin
źródło
źródło
A - Jak odwrócić stos
Aby zrozumieć, jak zbudować kolejkę przy użyciu dwóch stosów, powinieneś zrozumieć, jak odwrócić stos krystalicznie czysty. Pamiętaj, jak działa stos, jest bardzo podobny do stosu naczyń w kuchni. Ostatni myte naczynia będzie na górze stosu czystą, co nazywa się L AST I N F IRST O UT (LIFO) w informatyce.
Wyobraźmy sobie nasz stos jak butelkę jak poniżej;
Jeśli popchniemy odpowiednio liczby całkowite 1,2,3, wówczas 3 będzie na górze stosu. Ponieważ 1 zostanie popchnięty jako pierwszy, następnie 2 zostaną umieszczone na górze 1. Na koniec 3 zostaną umieszczone na górze stosu, a najnowszy stan naszego stosu przedstawiony jako butelka będzie wyglądał jak poniżej;
Teraz mamy nasz stos reprezentowany jako butelka wypełniona wartościami 3,2,1. I chcemy odwrócić stos, aby górny element stosu wynosił 1, a dolny element stosu wynosił 3. Co możemy zrobić? Możemy wziąć butelkę i trzymać ją do góry nogami, aby wszystkie wartości odwróciły się w kolejności?
Tak, możemy to zrobić, ale to jest butelka. Aby wykonać ten sam proces, musimy mieć drugi stos, który będzie przechowywać pierwsze elementy stosu w odwrotnej kolejności. Umieśćmy nasz zaludniony stos po lewej, a nasz nowy pusty stos po prawej. Aby odwrócić kolejność elementów, wyskakujemy z każdego elementu z lewego stosu i popychamy je do prawego stosu. Możesz zobaczyć, co się dzieje, kiedy to robimy, na poniższym obrazku;
Wiemy więc, jak odwrócić stos.
B - Używanie dwóch stosów jako kolejki
W poprzedniej części wyjaśniłem, w jaki sposób możemy odwrócić kolejność elementów stosu. Było to ważne, ponieważ jeśli popchniemy i pop elementy do stosu, dane wyjściowe będą dokładnie w odwrotnej kolejności w kolejce. Myśląc o przykładzie, pchnijmy tablicę liczb całkowitych
{1, 2, 3, 4, 5}
na stos. Jeśli wstawimy elementy i wydrukujemy je, aż stos będzie pusty, otrzymamy tablicę w odwrotnej kolejności wypychania, co będzie{5, 4, 3, 2, 1}
Zapamiętaj, że dla tego samego wejścia, jeśli usuniemy kolejkę z kolejki, aż kolejka będzie pusta, wynik będzie{1, 2, 3, 4, 5}
. Jest więc oczywiste, że dla tej samej kolejności wprowadzania elementów wynik kolejki jest dokładnie odwrotny niż wynik stosu. Ponieważ wiemy, jak odwrócić stos przy użyciu dodatkowego stosu, możemy zbudować kolejkę przy użyciu dwóch stosów.Nasz model kolejek będzie składał się z dwóch stosów. Jeden stos zostanie użyty do
enqueue
operacji (stos nr 1 po lewej stronie, będzie nazywany jako stos wejściowy), inny stos zostanie użyty dodequeue
operacji (stos nr 2 po prawej, będzie nazywany stosem wyjściowym). Sprawdź obraz poniżej;Nasz pseudo-kod jest jak poniżej;
Kolejkuj operację
Dequeue Operation
Kolejkujmy
{1, 2, 3}
odpowiednio liczby całkowite . Liczby całkowite będą wypychane na stos wejściowy ( stos nr 1 ), który znajduje się po lewej stronie;Co stanie się, jeśli wykonamy operację usuwania kolejki? Za każdym razem, gdy wykonywana jest operacja usuwania kolejki, kolejka sprawdzi, czy stos wyjściowy jest pusty, czy nie (patrz pseudo-kod powyżej). Jeśli stos wyjściowy jest pusty, stos wejściowy zostanie wyodrębniony na wyjściu, więc elementy stosu wejściowego zostanie odwrócony. Przed zwróceniem wartości stan kolejki będzie taki jak poniżej;
Sprawdź kolejność elementów w stosie wyjściowym (stos nr 2). Oczywiste jest, że możemy wstawić elementy ze stosu wyjściowego, aby dane wyjściowe były takie same, jakbyśmy usunęli kolejkę z kolejki. Zatem jeśli wykonamy dwie operacje usuwania kolejki, najpierw otrzymamy
{1, 2}
odpowiednio. Wówczas element 3 będzie jedynym elementem stosu wyjściowego, a stos wejściowy będzie pusty. Jeśli kolejkujemy elementy 4 i 5, wówczas stan kolejki będzie następujący;Teraz stos wyjściowy nie jest pusty, a jeśli wykonamy operację usuwania kolejki, tylko 3 zostaną wyskakujące ze stosu wyjściowego. Wtedy stan będzie widoczny jak poniżej;
Ponownie, jeśli wykonamy dwie kolejne operacje usuwania z kolejki, podczas pierwszej operacji usuwania z kolejki kolejka sprawdzi, czy stos wyjściowy jest pusty, co jest prawdą. Następnie wyskakuj z elementów stosu wejściowego i popchnij je do stosu wyjściowego, aż stos wejściowy będzie pusty, a następnie stan kolejki będzie następujący:
Łatwo zauważyć, że wynik dwóch operacji usuwania w kolejce będzie
{4, 5}
C - Implementacja kolejki zbudowanej z dwóch stosów
Oto implementacja w Javie. Nie zamierzam używać istniejącej implementacji Stack, więc przykład tutaj wymyśli na nowo koło;
C - 1) Klasa MyStack: prosta implementacja stosu
C - 2) Klasa MyQueue: Implementacja kolejki przy użyciu dwóch stosów
C - 3) Kod demonstracyjny
C - 4) Wyjście próbki
źródło
Możesz nawet symulować kolejkę, używając tylko jednego stosu. Drugi (tymczasowy) stos może być symulowany przez stos wywołań rekurencyjnych wywołań metody wstawiania.
Zasada pozostaje taka sama przy wstawianiu nowego elementu do kolejki:
Klasa kolejki korzystająca tylko z jednego stosu wyglądałaby następująco:
źródło
n items
do kolejki przy użyciu powyższej struktury danych. suma(1 + 2 + 4 + 8 + .... + 2(n-1))
daje wynik~O(n^2)
. Mam nadzieję, że rozumiesz.Złożoność czasu byłaby jednak gorsza. Dobra implementacja kolejki robi wszystko w stałym czasie.
Edytować
Nie jestem pewien, dlaczego moja odpowiedź została tutaj zanotowana. Jeśli programujemy, dbamy o złożoność czasu, a używanie dwóch standardowych stosów do tworzenia kolejki jest nieefektywne. To bardzo ważny i istotny punkt. Jeśli ktoś jeszcze odczuwa potrzebę dalszego głosowania za tym, chciałbym wiedzieć, dlaczego.
Trochę więcej szczegółów : dlaczego użycie dwóch stosów jest gorsze niż kolejka: jeśli użyjesz dwóch stosów i ktoś wywoła dequeue, gdy skrzynka nadawcza jest pusta, potrzebujesz liniowego czasu, aby dostać się do dolnej części skrzynki odbiorczej (jak widać w kodzie Dave'a).
Możesz zaimplementować kolejkę jako pojedynczo połączoną listę (każdy element wskazuje na następny wstawiany element), zachowując dodatkowy wskaźnik do ostatnio wstawionego elementu dla wypychań (lub tworząc z niego cykliczną listę). Implementowanie kolejki i usuwania z kolejki w tej strukturze danych jest bardzo łatwe do wykonania w stałym czasie. To najgorszy możliwy stały czas, nie amortyzowany. A ponieważ komentarze wydają się prosić o to wyjaśnienie, stały najgorszy przypadek jest zdecydowanie lepszy niż stały zamortyzowany czas.
źródło
Niech kolejką do implementacji będzie q, a stosy użyte do implementacji q będą stos1 i stos2.
q można zaimplementować na dwa sposoby:
Metoda 1 (przez uczynienie operacji enQueue kosztowną)
Ta metoda zapewnia, że nowo wprowadzony element zawsze znajduje się na górze stosu 1, dzięki czemu operacja deQueue wyskakuje ze stosu1. Aby umieścić element na górze stosu1, stosuje się stos2.
Metoda 2 (przez uczynienie operacji deQueue kosztowną)
W tej metodzie w operacji kolejkowania nowy element jest wprowadzany na górze stosu1. W operacji usuwania z kolejki, jeśli stos2 jest pusty, wówczas wszystkie elementy są przenoszone na stos2 i na końcu zwracana jest góra stosu2.
Metoda 2 jest zdecydowanie lepsza niż metoda 1. Metoda 1 przenosi wszystkie elementy dwukrotnie w operacji enQueue, podczas gdy metoda 2 (w operacji deQueue) przesuwa elementy raz i przenosi elementy tylko wtedy, gdy stos2 jest pusty.
źródło
Rozwiązanie w C #
źródło
Dwa stosy w kolejce są zdefiniowane jako stos1 i stos2 .
Kolejka: Wymienione elementy są zawsze wypychane na stos1
Dequeue: Górną część stosu2 można wysunąć, ponieważ jest to pierwszy element wstawiany do kolejki, gdy stos2 nie jest pusty. Kiedy stos2 jest pusty, usuwamy wszystkie elementy ze stosu 1 i pchamy je kolejno do stosu 2 . Pierwszy element w kolejce jest wypychany na spód stosu1 . Można go wyskoczyć bezpośrednio po operacji popping i push, ponieważ znajduje się na górze stosu2 .
Poniższy przykładowy kod C ++:
To rozwiązanie zostało zapożyczone z mojego bloga . Bardziej szczegółowa analiza z symulacjami operacji krok po kroku jest dostępna na mojej stronie blogu.
źródło
Musisz usunąć wszystko z pierwszego stosu, aby uzyskać dolny element. Następnie umieść je wszystkie z powrotem na drugim stosie dla każdej operacji „usuwania”.
źródło
dla programisty c # tutaj jest kompletny program:
źródło
Zaimplementuj następujące operacje w kolejce, używając stosów.
push (x) - Wciśnij element x na tył kolejki.
pop () - Usuwa element z przodu kolejki.
peek () - Pobierz przedni element.
empty () - Zwraca, czy kolejka jest pusta.
źródło
źródło
Implementacja kolejki przy użyciu dwóch stosów w Swift:
źródło
Otrzymasz wiele postów związanych z implementacją kolejki z dwoma stosami: 1. Albo przez uczynienie procesu enQueue znacznie droższym 2. Lub przez uczynienie procesu deQueue znacznie droższym
https://www.geeksforgeeks.org/queue-using-stacks/
Jednym z ważnych sposobów, jakie dowiedziałem się z powyższego postu, było zbudowanie kolejki z samą strukturą danych stosu i stosem wywołań rekurencyjnych.
Chociaż można argumentować, że dosłownie nadal używa dwóch stosów, ale idealnie jest to tylko jedna struktura danych stosu.
Poniżej znajduje się wyjaśnienie problemu:
Zadeklaruj pojedynczy stos do enQueuing i deQueing danych i wepchnij dane do stosu.
podczas gdy deQueueing ma warunek podstawowy, w którym element stosu jest wyskakujący, gdy rozmiar stosu wynosi 1. Zapewni to, że nie nastąpi przepełnienie stosu podczas rekurencji deQueue.
Podczas deQueueing najpierw pop dane z góry stosu. Idealnie ten element będzie elementem znajdującym się na górze stosu. Teraz, gdy to zrobisz, rekurencyjnie wywołaj funkcję deQueue, a następnie wepchnij element wyskakujący powyżej z powrotem do stosu.
Kod będzie wyglądał jak poniżej:
W ten sposób można utworzyć kolejkę przy użyciu struktury danych z jednym stosem i stosu wywołań rekurencyjnych.
źródło
Poniżej znajduje się rozwiązanie w języku javascript wykorzystujące składnię ES6.
Stack.js
QueueUsingTwoStacks.js
Poniżej jest użycie:
index.js
źródło
stack1
. Gdy przejdzieszdequeue
ponownie, przeniesiesz do nich przedmiotystack2
, stawiając je przed tym, co już tam było.Odpowiem na to pytanie w Go, ponieważ Go nie ma bogatej kolekcji w swojej standardowej bibliotece.
Ponieważ stos jest naprawdę łatwy do wdrożenia, pomyślałem, że spróbuję użyć dwóch stosów, aby uzyskać podwójnie zakończoną kolejkę. Aby lepiej zrozumieć, w jaki sposób doszedłem do mojej odpowiedzi, podzieliłem implementację na dwie części, pierwsza część jest, mam nadzieję, łatwiejsza do zrozumienia, ale jest niepełna.
W zasadzie są to dwa stosy, w których pozwalamy sobie na manipulowanie dnem stosów. Użyłem również konwencji nazewnictwa STL, w której tradycyjne operacje stosu push, pop i peek mają przedrostek przód / tył, niezależnie od tego, czy odnoszą się do przodu, czy do tyłu kolejki.
Problem z powyższym kodem polega na tym, że nie wykorzystuje on bardzo skutecznie pamięci. W rzeczywistości rośnie bez końca, dopóki nie zabraknie ci miejsca. To naprawdę źle. Rozwiązaniem tego problemu jest ponowne użycie dolnej części stosu, gdy tylko jest to możliwe. Musimy wprowadzić przesunięcie, aby to śledzić, ponieważ kawałek Go nie może rosnąć z przodu po zmniejszeniu.
To wiele małych funkcji, ale spośród 6 funkcji 3 z nich są tylko zwierciadłami drugiej.
źródło
oto moje rozwiązanie w Javie za pomocą Linkedlist.
}
Uwaga: w tym przypadku operacja pop jest bardzo czasochłonna. Więc nie będę sugerował tworzenia kolejki przy użyciu dwóch stosów.
źródło
Z
O(1)
dequeue()
, co odpowiada odpowiedzi pythonquicka :Z
O(1)
enqueue()
(nie jest to wspomniane w tym poście, więc ta odpowiedź), która również używa cofania, aby utworzyć bąbelki i zwrócić najniższy element.Oczywiście jest to dobre ćwiczenie kodowania, ponieważ jest nieefektywne, ale mimo to eleganckie.
źródło
** Łatwe rozwiązanie JS **
źródło
Do każdej operacji kolejkowania dodajemy na górę stosu1. Przy każdym usuwaniu z kolejki opróżniamy zawartość stosu1 do stosu2 i usuwamy element u góry stosu. Czas złożoności wynosi O (n) dla usuwania z kolejki, ponieważ musimy skopiować stos1 na stos2. złożoność czasowa kolejki jest taka sama jak w przypadku zwykłego stosu
źródło
if (stack2 != null)
jest zawsze prawdziwy, ponieważstack2
jest tworzony w konstruktorze.Implementacja kolejki przy użyciu dwóch obiektów java.util.Stack:
źródło
return inbox.isEmpty() && outbox.isEmpty()
ireturn inbox.size() + outbox.size()
odpowiednio. Kod Dave'a L. już zgłasza wyjątek, kiedy usuwasz kolejkę z pustej kolejki. Pierwotne pytanie nie dotyczyło nawet Javy; chodziło ogólnie o struktury danych / algorytmy. Implementacja Java była tylko dodatkową ilustracją.