Jeden stos, dwie kolejki

59

tło

Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i powiedział, że zapomniał dowodu i ... [wiesz co].

Dzisiaj przypomniałem sobie problem. Wciąż chciałem wiedzieć, więc oto jest ...

Pytanie

Czy można zaimplementować stos przy użyciu dwóch kolejek , aby operacje PUSH i POP działały w zamortyzowanym czasie O (1) ? Jeśli tak, czy możesz mi powiedzieć jak?

Uwaga: sytuacja jest dość łatwa, jeśli chcemy zaimplementować kolejkę z dwoma stosami (z odpowiednimi operacjami WYJŚCIE i WYJŚCIE ). Proszę zwrócić uwagę na różnicę.

PS: Powyższy problem nie dotyczy samej pracy domowej. Praca domowa nie wymagała żadnych dolnych granic; tylko implementacja i analiza czasu pracy.

MS Dousti
źródło
2
Myślę, że możesz użyć tylko ograniczonej ilości miejsca innej niż dwie kolejki (O (1) lub O (log n)). Wydaje mi się to niemożliwe, ponieważ nie mamy możliwości odwrócenia kolejności długiego strumienia wejściowego. Ale oczywiście nie jest to dowód, chyba że można go przekształcić w rygorystyczne twierdzenie…
Tsuyoshi Ito
@Tsuyoshi: Masz rację co do założenia o ograniczonej przestrzeni. I tak, właśnie to powiedziałem temu (upartemu) TA, ale on odmówił :(
MS Dousti
2
@Tsuyoshi: Nie sądzę, że musisz ogólnie zakładać ograniczenie przestrzeni, musisz tylko założyć, że nie możesz przechowywać obiektów wypchniętych i wyskakujących ze stosu w innym miejscu niż dwie kolejki (i prawdopodobnie stała liczba zmiennych).
Kaveh
@SadeqDousti Moim zdaniem jedynym sposobem byłoby to możliwe, jeśli użyjesz implementacji kolejki z listami połączonymi i użyjesz niektórych wskaźników, aby zawsze wskazywać na górę „stosu”
Charles Addis
2
Wygląda na to, że TA rzeczywiście chciał powiedzieć „Zaimplementuj kolejkę za pomocą dwóch stosów”, co jest rzeczywiście możliwe właśnie w „O (1) zamortyzowanym czasie”.
Thomas Ahle

Odpowiedzi:

45

Nie mam rzeczywistej odpowiedzi, ale oto kilka dowodów na to, że problem jest otwarty:

  • Nie wspomniano o tym w Ming Li, Luc Longpré i Paul MB Vitányi, „The power of the queue”, Structures 1986, który rozważa kilka innych blisko powiązanych symulacji

  • Nie wspomina o tym Martin Hühne, „Na mocy kilku kolejek”, Theor. Komp. Sci. 1993, kolejny dokument.

  • Nie wspomina o tym w Holger Petersen, „Stacks versus Deques”, COCOON 2001.

  • Burton Rosenberg, „Szybkie niedeterministyczne rozpoznawanie języków bezkontekstowych przy użyciu dwóch kolejek”, Inform. Proc. Łotysz. 1998, daje algorytm O (n log n) dwu-kolejkowy do rozpoznawania dowolnej CFL przy użyciu dwóch kolejek. Ale niedeterministyczny automat odpychający może rozpoznać świetlówki kompaktowe w czasie liniowym. Więc jeśli istniałaby symulacja stosu z dwiema kolejkami szybszymi niż O (log n) na operację, Rosenberg i jego sędziowie powinni byli o tym wiedzieć.

David Eppstein
źródło
4
+1 za doskonałe referencje. Jest jednak kilka szczegółów technicznych: niektóre dokumenty, jak pierwsza, nie rozważają problemu symulowania jednego stosu przy użyciu dwóch kolejek (tyle, ile mogę powiedzieć z streszczenia). Inni rozważają analizę najgorszego przypadku, a nie zamortyzowany koszt.
MS Dousti
13

Odpowiedź poniżej brzmi „oszustwo”, ponieważ chociaż nie używa on żadnej przestrzeni między operacjami, same operacje mogą wykorzystywać więcej niż przestrzeń . Zobacz gdzie indziej w tym wątku, aby uzyskać odpowiedź, w której nie ma tego problemu.O(1)

Chociaż nie mam odpowiedzi na dokładne pytanie, znalazłem algorytm, który działa w czas zamiastO(n). Uważam, że jest ciasno, chociaż nie mam dowodu. Jeśli już, algorytm pokazuje, że próba udowodnienia dolnej granicyO(n)jest daremna, więc może pomóc w odpowiedzi na twoje pytanie.O(n)O(n)O(n)

Przedstawiam dwa algorytmy, pierwszy z nich to prosty algorytm z czasem działania dla Pop, a drugi z O ( O(n)czas działania Pop. Pierwszy opisuję głównie ze względu na jego prostotę, dzięki czemu drugi jest łatwiejszy do zrozumienia.O(n)

Aby podać więcej szczegółów: pierwsze nie używa dodatkowej spacji, ma najgorszy przypadek (i amortyzowane) Push i najgorszy przypadek O ( n ) (i amortyzowane) Pop, ale zachowanie najgorszego przypadku nie zawsze jest wyzwalane. Ponieważ nie wykorzystuje żadnej dodatkowej przestrzeni poza dwiema kolejkami, jest nieco „lepszy” niż rozwiązanie oferowane przez Rossa Snidera.O(1)O(n)

Drugi używa pojedynczego pola liczb całkowitych (więc dodatkowa spacja ), ma najgorszy przypadek O ( 1 ) (i zamortyzowany) Push i O ( O(1)O(1)amortyzowany Pop. Czas jego działania jest zatem znacznie lepszy niż w przypadku „prostego” podejścia, ale wymaga on dodatkowej przestrzeni.O(n)

Pierwszy algorytm

Mamy dwie kolejki: kolejkę kolejek s e c o n D . f i r s t będzie naszą „kolejką wypychającą”, podczas gdy s e c o n d będzie kolejką już w „kolejności stosów”.fajarstsmidoonrefajarstsmidoonre

  • Popychanie odbywa się po prostu przez skolejkowania parametru na .fajarst
  • Wyskakiwanie odbywa się w następujący sposób. Jeśli jest pusty, po prostu rozkolejkowania a e C O n d i zwraca wynik. W przeciwnym razie odwracamy f i r s t , dołączamy wszystkie s e c o n d do f i r s t i zamieniamy f i r s t i s e c o n d . Następnie dequeue s e c ofajarstsmidoonrefajarstsmidoonrefajarstfajarstsmidoonre i zwróć wynik dequeue.smidoonre

Kod C # dla pierwszego algorytmu

Może to być dość czytelne, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Analiza

Oczywiście Push działa w czasie . Pop może dotykać wszystko wewnątrz F I r s t a a e C O n d stałej ilości czasu, więc mamy O ( n ) w najgorszym przypadku. Algorytm wykazuje takie zachowanie (na przykład), jeśli popycha się n elementów na stos, a następnie wielokrotnie wykonuje pojedynczą operację Push i pojedynczą operację Pop.O(1)fajarstsmidoonreO(n)n

Drugi algorytm

Mamy dwie kolejki: kolejkę kolejek s e c o n D . f i r s t będzie naszą „kolejką wypychającą”, podczas gdy s e c o n d będzie kolejką już w „kolejności stosów”.fajarstsmidoonrefajarstsmidoonre

Jest to dostosowane wersję pierwszego algorytmu, w którym nie od razu SHUFFLE ", których zawartość w a e C O n d . Zamiast tego, jeśli f i r s t zawiera wystarczająco małą liczbę elementów w porównaniu do s e c o n d (mianowicie pierwiastek kwadratowy z liczby elementów w s e c o n d ), reorganizujemy tylko f i r s t w stosie i nie łącz gofajarstsmidoonrefajarstsmidoonresmidoonrefajarst .smidoonre

  • Popychanie nadal odbywa się po prostu przez skolejkowania parametru na .fajarst
  • Wyskakiwanie odbywa się w następujący sposób. Jeśli jest pusty, po prostu rozkolejkowania a e C O n d i zwraca wynik. Inaczej, porządkowanie zawartości F I r s t , tak, że są w kolejności stosu. Jeśli | f i r s t | < fajarstsmidoonrefajarstpo prostu rozkolejkowaniaFIrsti zwraca wynik. W przeciwnym razie dodaćeeconDnafirst, swapFIrstaaeCo,nd, rozkolejkowaniaeeco,nDi zwraca wynik.|fajarst|<|smidoonre|fajarstsmidoonrefajarstfajarstsmidoonresmidoonre

Kod C # dla pierwszego algorytmu

Może to być dość czytelne, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Analiza

Oczywiście Push działa w czasie .O(1)

Pop działa w amortyzowany czas. Istnieją dwa przypadki: jeśli| first| <O(n), a następnie tasujemyfirstw kolejności stosu wO(|first|)=O(|fajarst|<|smidoonre|fajarstczas. Jeśli| first| O(|fajarst|)=O(n), to musieliśmy mieć przynajmniej|fajarst||smidoonre| wzywa do Push. Stąd możemy tylko hit tego sprawę każdyn połączeń z Push i Pop. Rzeczywisty czas działania dla tego przypadku wynosiO(n), więc zamortyzowany czas wynosiO( nnO(n).O(nn)=O(n)

Ostatnia uwaga

Możliwe jest wyeliminowanie dodatkowej zmiennej kosztem zmiany Pop na operacji, poprzez reorganizację popFIrstw każdym połączeniu zamiast push wszystkie prace.O(n)first

Alex ten Brink
źródło
Zredagowałem pierwsze akapity, więc moja odpowiedź jest sformułowana jako rzeczywista odpowiedź na pytanie.
Alex ten Brink
6
Używasz tablicy (odwracacza) do cofania! Nie sądzę, żebyś mógł to zrobić.
Kaveh
To prawda, że ​​używam dodatkowej przestrzeni podczas wykonywania metod, ale pomyślałem, że byłoby to dozwolone: ​​jeśli chcesz zaimplementować kolejkę przy użyciu dwóch stosów w prosty sposób, musisz odwrócić jeden ze stosów w jednym punkcie i do tego stopnia, że Wiem, że potrzebujesz do tego dodatkowej przestrzeni, więc ponieważ to pytanie jest podobne, pomyślałem, że użycie dodatkowej spacji podczas wykonywania metody będzie dozwolone, o ile nie użyjesz dodatkowej spacji między wywołaniami metod.
Alex ten Brink
6
„jeśli chcesz zaimplementować kolejkę przy użyciu dwóch stosów w prosty sposób, musisz odwrócić jeden ze stosów w jednym punkcie i, o ile wiem, potrzebujesz dodatkowej przestrzeni, aby to zrobić” --- Nie. Istnieje sposób na uzyskanie zamortyzowanego kosztu Enqueue na 3, a zamortyzowanego kosztu Dequeue na 1 (tj. Oba O (1)) z jedną komórką pamięci i dwoma stosami. Trudna część to tak naprawdę dowód, a nie konstrukcja algorytmu.
Aaron Sterling
Po dłuższym zastanowieniu zdaję sobie sprawę, że rzeczywiście oszukuję, a mój poprzedni komentarz jest naprawdę błędny. Znalazłem sposób, aby to naprawić: wymyśliłem dwa algorytmy o takich samych czasach działania, jak powyższe dwa (chociaż Push jest teraz operacją, która trwa długo, a Pop jest teraz wykonywany w stałym czasie) bez użycia dodatkowego miejsca. Opublikuję nową odpowiedź, gdy wszystko to zanotuję.
Alex ten Brink
12

Po kilku komentarzach do mojej poprzedniej odpowiedzi stało się dla mnie jasne, że mniej więcej oszukuję: wykorzystałem dodatkową przestrzeń ( dodatkowe miejsce w drugim algorytmie) podczas wykonywania mojej metody Pop.O(n)

Poniższy algorytm nie wykorzystuje żadnej dodatkowej spacji między metodami, a jedynie dodatkową przestrzeń podczas wykonywania operacji Push i Pop. Push ma O ( O(1)amortyzowane czas pracy i pop maO(1)najgorszym przypadku (i amortyzowane) Czas trwania.O(n)O(1)

Uwaga dla moderatorów: Nie jestem do końca pewien, czy moja decyzja, aby uczynić to osobną odpowiedzią, jest poprawna. Pomyślałem, że nie powinienem usuwać mojej pierwotnej odpowiedzi, ponieważ może ona nadal mieć związek z pytaniem.

Algorytm

Mamy dwie kolejki: kolejkę kolejek s e c o n D . F I r s t będzie naszym 'bufor', a e e c o n d będzie głównym 'przechowywanie'. Obie kolejki zawsze będą w „stosie”. F I r s t zawierają elementy w górnej części stosu i e e c o n D zawiera elementy na dole stosu. Rozmiar f i rfajarstsmidoonrefajarstsmidoonrefajarstsmidoonre będzie zawsze co najwyżej pierwiastkiem kwadratowym s e c o n d .fajarstsmidoonre

  • Wypychanie odbywa się poprzez „wstawienie” parametru na początku kolejki w następujący sposób: kolejkujemy parametr do , a następnie usuwamy z kolejki i ponownie kolejkujemy wszystkie pozostałe elementy w f i r s t . W ten sposób parametr kończy się na początku f i r s t .fajarstfajarstfirst
  • Jeśli staje się większy niż pierwiastek kwadratowy s e c o n d , kolejkujemy wszystkie elementy s e c o n d na f i r s t jeden po drugim, a następnie zamieniamy f i r s t i s e c o n d . W ten sposób, elementy f i r s t (w górnej części stosu) kończy się na głowicy s efirstsecondsecondfirstfirstsecondfirst .second
  • Pop dokonuje dequeueing , a powrót wyniku, jeżeli f i r s t nie jest pusta, a inaczej dequeueing a e C O n d a powracający wynik.firstfirstsecond

Kod C # dla pierwszego algorytmu

Ten kod powinien być dość czytelny, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Analiza

Oczywiście w najgorszym przypadku Pop działa w czasie .O(1)

Push działa w amortyzowany czas. Istnieją dwa przypadki: jeśli| first| <O(n)następnie Push przyjmujeO(|first|<|second|czas. Jeśli| first| O(n)następnie Push zajmujeO(n)czas, ale po tej operacjifirstbędzie pusty. Zajmie toO(|first||second|O(n)firstczas, zanim ponownie otrzymamy ten przypadek, więc zamortyzowany czas wynosiO( nO(n)czas.O(nn)=O(n)

Alex ten Brink
źródło
na temat usuwania odpowiedzi, proszę spojrzeć na meta.cstheory.stackexchange.com/q/386/873 .
MS Dousti,
Nie rozumiem linii first.Enqueue(first.Dequeue()). Czy coś źle wpisałeś?
MS Dousti,
Dzięki za link, odpowiednio zaktualizowałem swoją pierwotną odpowiedź. Po drugie, dodałem wiele komentarzy do mojego kodu opisujących, co dzieje się podczas wykonywania mojego algorytmu, mam nadzieję, że rozwiąże to wszelkie nieporozumienia.
Alex ten Brink
dla mnie algorytm był bardziej czytelny i łatwiejszy do zrozumienia przed edycją.
Kaveh
9

Θ(N.)

N.N.N.N.N.

P.US.H.N.(P.US.H.N.P.OP.N.)N.

N.N./2)

N.

N./2)N./2)

N./2)2)N.

N./2)2)N.N.N.N./2)3)N.Ω(N.)

Shaun Harker
źródło
NN
nQ1N/2Q22nn4:1+2++n+n2n
Najwyraźniej odpowiedź Piotra zaprzecza tej dolnej granicy?
Joe
PUSHNPOPNO(N)
O(N)
6

O(lgn)pushpoppopO(lgn)pop jest wymagane, a kolejka wyjściowa jest pusta, wykonujesz sekwencję idealnych przetasowań, aby odwrócić kolejkę wejściową i zapisać ją w kolejce wyjściowej.

O(1)

O ile mi wiadomo, to nowy pomysł ...

Peter Boothe
źródło
Argh! Powinienem był poszukać zaktualizowanego lub powiązanego pytania. Dokumenty, do których łączyłeś się w swojej wcześniejszej odpowiedzi, wskazywały na stosunek k stosów do k + 1 stosów. Czy ta sztuczka kończy moc k kolejek między k i k + 1 stosów? Jeśli tak, to trochę fajny sidenote. Tak czy inaczej, dzięki za powiązanie mnie z twoją odpowiedzią, więc nie marnowałem zbyt wiele czasu na pisanie tego w innym miejscu.
Peter Boothe
1

Bez korzystania z dodatkowej przestrzeni, może przy użyciu kolejki z priorytetami i zmuszania każdego nowego pusha do nadania mu większego priorytetu niż poprzedni? Nadal nie byłby to O (1).

Alfa
źródło
0

Nie mogę zmusić kolejek do wdrożenia stosu w zamortyzowanym stałym czasie. Mogę jednak wymyślić sposób na uzyskanie dwóch kolejek w celu wdrożenia stosu w najgorszym przypadku w czasie liniowym.

  • ZAb
  • Za każdym razem, gdy wykonywana jest operacja wypychania, odwróć bit i wstaw element do kolejki, którą bit wyznacza teraz. Usuń wszystko z drugiej kolejki i pchnij ją do bieżącej kolejki.
  • Operacja pop powoduje zdjęcie przedniej części bieżącej kolejki i nie dotyka zewnętrznego bitu stanu.

Oczywiście możemy dodać kolejny kawałek stanu zewnętrznego, który mówi nam, czy ostatnia operacja była pushem czy popem. Możemy opóźnić przenoszenie wszystkiego z jednej kolejki do drugiej, dopóki nie otrzymamy dwóch operacji wypychania z rzędu. To sprawia, że ​​operacja pop jest nieco bardziej skomplikowana. To daje nam zamortyzowaną złożoność O (1) dla operacji pop. Niestety push pozostaje liniowy.

Wszystko to działa, ponieważ za każdym razem, gdy wykonywana jest operacja wypychania, nowy element jest umieszczany na czele pustej kolejki, a pełna kolejka jest dodawana do jej końca, skutecznie odwracając elementy.

Jeśli chcesz uzyskać amortyzację operacji w stałym czasie, prawdopodobnie będziesz musiał zrobić coś mądrzejszego.

Ross Snider
źródło
4
Z pewnością mogę użyć pojedynczej kolejki o takiej samej złożoności z jak najgorszym czasem i bez komplikacji, zasadniczo traktując tę ​​kolejkę jako okrągłą listę z dodatkowym elementem kolejki reprezentującym górę stosu.
Dave Clarke
Wygląda na to, że możesz! Wygląda jednak na to, że do symulacji stosu w ten sposób potrzeba więcej niż jednej klasycznej kolejki.
Ross Snider
0

Istnieje trywialne rozwiązanie, jeśli twoja kolejka umożliwia ładowanie od przodu, która wymaga tylko jednej kolejki (a ściślej mówiąc: deque). Być może jest to rodzaj kolejki, o której myśli TA w pierwotnym pytaniu?

Bez możliwości ładowania z przodu, oto inne rozwiązanie:

Ten algorytm wymaga dwóch kolejek i dwóch wskaźników, nazwiemy je odpowiednio Q1, Q2, podstawowy i dodatkowy. Po inicjalizacji Q1 i Q2 są puste, punkty pierwotne do Q1 i drugorzędne do Q2.

Operacja PUSH jest trywialna, polega jedynie na:

*primary.enqueue(value);

Operacja POP jest nieco bardziej zaangażowana; wymaga buforowania wszystkich z wyjątkiem ostatniej pozycji kolejki podstawowej do kolejki dodatkowej, zamiany wskaźników i zwrócenia ostatniego pozostałego elementu z kolejki oryginalnej:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

Sprawdzanie granic nie jest wykonywane i nie jest to O (1).

Gdy piszę to, widzę, że można to zrobić za pomocą pojedynczej kolejki za pomocą pętli for zamiast pętli while, tak jak zrobił to Alex. Tak czy inaczej, operacja PUSH to O (1), a operacja POP zmienia się w O (n).


Oto inne rozwiązanie wykorzystujące dwie kolejki i jeden wskaźnik, odpowiednio o nazwach Q1, Q2 i queue_p:

Po inicjalizacji Q1 i Q2 są puste, a kolejka_p wskazuje na Q1.

Ponownie operacja PUSH jest trywialna, ale wymaga jednego dodatkowego kroku skierowania queue_p na drugą kolejkę:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

Operacja POP jest podobna do poprzedniej, ale teraz w kolejce jest n / 2 elementów, które należy obrócić:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

Operacja PUSH to nadal O (1), ale teraz operacja POP to O (n / 2).

Osobiście dla tego problemu wolę pomysł zaimplementowania pojedynczej, podwójnie zakończonej kolejki (deque) i nazywanie jej stosem, kiedy chcemy.

oosterwal
źródło
Twój drugi algorytm pomaga zrozumieć bardziej zaangażowany jeden z Alex.
hengxin
0

kΘ(n1/k)

k
n
O(1)

jaΘ(nja/k)Θ(nja/k)O(1)ja+1O(n1/k)ja-1Θ(n1/k) (lub jeśli mamy tylko jeden stos i pozwalamy na amortyzację czasu popu).

mmΩ(mn1/k)o(n1/k)Ω(n1/k)o(n2)/k)ko(n)

Θ(logn)

Dmytro Taranovsky
źródło
-3

Stos można zaimplementować przy użyciu dwóch kolejek, używając drugiej kolejki jako nadrzędnej. Kiedy przedmioty są wypychane na stos, są dodawane na końcu kolejki. Za każdym razem, gdy element jest otwierany, elementy n - 1 pierwszej kolejki muszą być przenoszone do drugiej, a pozostały element jest zwracany. klasa publiczna QueueStack wdraża IStack {private IQueue q1 = new Queue (); prywatne IQueue q2 = nowa kolejka (); public void push (E e) {q1.enqueue (e) // O (1)} public E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } p rivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}

Pradeepkumar
źródło
2
Czy przegapiłeś część pytania dotyczącego zamortyzowanego czasu O (1)?
David Eppstein