Jeden stos, dwie kolejki

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.

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ć.

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(\sqrt{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(\sqrt{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(\sqrt{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”.$first$$second$$first$$second$

• Popychanie odbywa się po prostu przez skolejkowania parametru na .$first$
• 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 $first$$second$$first$$second$$first$$first$$second$ i zwróć wynik dequeue.$second$

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)$$first$$second$$O(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”.$first$$second$$first$$second$

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 go$first$$second$$first$$second$$second$$first$ .$second$

• Popychanie nadal odbywa się po prostu przez skolejkowania parametru na .$first$
• 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 | < $first$$second$$first$po prostu rozkolejkowaniaFIrsti zwraca wynik. W przeciwnym razie dodaćeeconDnafirst, swapFIrstaaeCo,nd, rozkolejkowaniaeeco,nDi zwraca wynik.$|first| < \sqrt{|second|}$$first$$second$$first$$first$$second$$second$

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(\sqrt{n})$, a następnie tasujemyfirstw kolejności stosu wO(|first|)=O($|first| < \sqrt{|second|}$$first$czas. Jeśli| first| ≥$O(|first|) = O(\sqrt{n})$, to musieliśmy mieć przynajmniej$|first| \geq \sqrt{|second|}$ wzywa do Push. Stąd możemy tylko hit tego sprawę każdy$\sqrt{n}$ połączeń z Push i Pop. Rzeczywisty czas działania dla tego przypadku wynosiO(n), więc zamortyzowany czas wynosiO($\sqrt{n}$$O(n)$.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{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(\sqrt{n})$$first$

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(\sqrt{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(\sqrt{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 $first$$second$$first$$second$$first$$second$ będzie zawsze co najwyżej pierwiastkiem kwadratowym s e c o n d .$first$$second$

• 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 .$first$$first$$first$
• 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 $first$$second$$second$$first$$first$$second$$first$ .$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.$first$$first$$second$

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(\sqrt{n})$następnie Push przyjmujeO($|first| < \sqrt{|second|}$czas. Jeśli| first| ≥$O(\sqrt{n})$następnie Push zajmujeO(n)czas, ale po tej operacjifirstbędzie pusty. Zajmie toO($|first| \geq \sqrt{|second|}$$O(n)$$first$czas, zanim ponownie otrzymamy ten przypadek, więc zamortyzowany czas wynosiO($O(\sqrt{n})$czas.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

$\Theta(\sqrt{N})$

$N$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

$N$$N/2$

$\sqrt{N}$

$N/2$$N/2$

$\sqrt{N}/2$$2\sqrt{N}$

$N/2$$2\sqrt{N}$$\sqrt{N}$$N\sqrt{N}/2$$3N$$\Omega(\sqrt{N})$

$O(\lg n)$$push$$pop$$pop$$O(\lg n)$$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ł ...

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).

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.

• $A$$B$
• 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.

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.

$k$$Θ(n^{1/k})$

$k$
$n$
$O(1)$

$i$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/k})$ (lub jeśli mamy tylko jeden stos i pozwalamy na amortyzację czasu popu).

$m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(n)$

$Θ(\log n)$

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; }}