Jak zaimplementować kolejkę z trzema stosami?

Natknąłem się na to pytanie w książce o algorytmach ( Algorithms, 4th Edition autorstwa Roberta Sedgewicka i Kevina Wayne'a).

Kolejka z trzema stosami. Zaimplementuj kolejkę z trzema stosami, tak aby każda operacja kolejki miała stałą (w najgorszym przypadku) liczbę operacji na stosie. Ostrzeżenie: wysoki stopień trudności.

Wiem, jak ustawić kolejkę z 2 stackami, ale nie mogę znaleźć rozwiązania przy 3 stackach. Dowolny pomysł ?

(no i to nie jest praca domowa :))

PODSUMOWANIE

• Algorytm O (1) jest znany dla 6 stosów
• Algorytm O (1) jest znany dla 3 stosów, ale wykorzystujący leniwą ocenę, która w praktyce odpowiada posiadaniu dodatkowych wewnętrznych struktur danych, więc nie stanowi rozwiązania
• Ludzie w pobliżu Sedgewick potwierdzili, że nie są świadomi rozwiązania z trzema stosami w ramach wszystkich ograniczeń pierwotnego pytania

DETALE

Za tym łączem kryją się dwie implementacje: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Jednym z nich jest O (1) z trzema stosami, ALE używa leniwego wykonywania, co w praktyce tworzy dodatkowe pośrednie struktury danych (domknięcia).

Kolejnym z nich jest O (1), ale używa SZEŚCIU stosów. Jednak działa bez leniwego wykonania.

AKTUALIZACJA: Artykuł Okasakiego jest tutaj: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps i wygląda na to, że w rzeczywistości używa on tylko 2 stosów dla wersji O (1), która ma leniwą ocenę. Problem w tym, że tak naprawdę opiera się na leniwej ocenie. Pytanie brzmi, czy można to przetłumaczyć na algorytm z 3 stosami bez leniwej oceny.

AKTUALIZACJA: Inny powiązany algorytm został opisany w artykule „Stacks versus Deques” autorstwa Holgera Petersena, opublikowanym na 7th Annual Conference on Computing and Combinatorics. Możesz znaleźć artykuł w Książkach Google. Sprawdź strony 225-226. Ale algorytm nie jest w rzeczywistości symulacją w czasie rzeczywistym, jest to symulacja czasu liniowego podwójnej kolejki na trzech stosach.

gusbro: „Jak powiedział @Leonel kilka dni temu, pomyślałem, że byłoby uczciwie sprawdzić u prof. Sedgewicka, czy znał rozwiązanie lub był jakiś błąd. Napisałem więc do niego. Właśnie otrzymałem odpowiedź (choć nie od siebie, ale od kolegi z Princeton), więc lubię się z wami wszystkimi podzielić. Powiedział po prostu, że nie znał algorytmu używającego trzech stosów ORAZ innych narzuconych ograniczeń (takich jak brak leniwej oceny). Znał algorytm wykorzystujący 6 stosów, jak już wiemy, patrząc na odpowiedzi tutaj. Myślę więc, że pytanie jest nadal otwarte, aby znaleźć algorytm (lub udowodnić, że nie można go znaleźć).

Ok, to jest naprawdę trudne, a jedyne rozwiązanie, jakie mogłem wymyślić, pamięta mnie rozwiązanie Kirksa do testu Kobayashi Maru (w jakiś sposób oszukane): Pomysł jest taki, że używamy stosu stosów (i używamy tego do modelowania listy ). Nazywam operacje en / dequeue i push and pop, a następnie otrzymujemy:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY to nie kopiowanie zawartości, tylko kopia odniesienia. Służy tylko do łatwego opisania. Możesz również użyć tablicy 3 stosów i uzyskać do nich dostęp poprzez indeks, tam po prostu zmieniasz wartość zmiennej indeksu ). Wszystko jest w O (1) w terminach operacji stosu.

I tak, wiem, że jest to dyskusyjne, ponieważ mamy ukryte więcej niż 3 stosy, ale może daje innym dobre pomysły.

EDYCJA: przykład objaśnienia:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Próbowałem tutaj z małą grafiką ASCII, aby pokazać Stack1.

Każdy element jest zawinięty w pojedynczy stos elementów (więc mamy tylko bezpieczny stos stosów).

Widzisz, aby usunąć, najpierw usuwamy pierwszy element (stos zawierający tutaj element 1 i 2). Następnie zdejmij następny element i rozpakuj tam 1. Następnie mówimy, że pierwszy wyskakujący stos jest teraz naszym nowym Stack1. Mówiąc trochę bardziej funkcjonalnie - są to listy implementowane przez stosy 2 elementów, gdzie górny element jest cdr, a pierwszy / pod górny element to samochód . Pozostałe 2 pomagają stackować.

Szczególnie trudne jest wstawianie, ponieważ musisz jakoś zanurkować głęboko w zagnieżdżone stosy, aby dodać kolejny element. Dlatego jest tam Stack2. Stos 2 jest zawsze najbardziej wewnętrznym stosem. Dodawanie jest wtedy po prostu wpychaniem elementu, a następnie umieszczaniem na wierzchu nowego Stack2 (i dlatego nie możemy dotykać Stack2 w naszej operacji usuwania z kolejki).

Spróbuję udowodnić, że nie da się tego zrobić.

Załóżmy, że istnieje kolejka Q, która jest symulowana przez 3 stosy, A, B i C.

Asercje

• ASRT0: = Ponadto załóżmy, że Q może symulować operacje {queue, dequeue} w O (1). Oznacza to, że istnieje określona sekwencja wypychania / wyskakiwania stosu dla każdej operacji kolejkowania / usuwania z kolejki, która ma być symulowana.

• Bez utraty ogólności załóżmy, że operacje kolejki są deterministyczne.

Niech elementy w kolejce do Q będą ponumerowane 1, 2, ... w oparciu o ich kolejność w kolejce, przy czym pierwszy element, który jest umieszczony w kolejce do Q jest zdefiniowany jako 1, drugi jako 2 i tak dalej.

Definiować

• Q(0) := Stan Q, gdy jest 0 elementów w Q (a więc 0 elementów w A, B i C)
• Q(1) := Stan Q (i A, B i C) po 1 operacji kolejki na Q(0)
• Q(n) := Stan Q (i A, B i C) po n operacjach kolejki Q(0)

Definiować

• |Q(n)| :=liczba elementów w Q(n)(a zatem |Q(n)| = n)
• A(n) := stan stosu A, gdy stan Q jest Q(n)
• |A(n)| := liczba elementów w A(n)

I podobne definicje dla stosów B i C.

Trywialne,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| jest oczywiście nieograniczony n.

Dlatego też, co najmniej jeden |A(n)|, |B(n)|lub |C(n)|jest nieograniczona od n.

WLOG1, załóżmy, że stos A jest nieograniczony, a stosy B i C są ograniczone.

Zdefiniuj * B_u :=górną granicę B * C_u :=górną granicę C *K := B_u + C_u + 1

WLOG2, dla n takiego, że |A(n)| > Kwybierz K elementów z Q(n). Załóżmy, że 1 z tych elementów jest A(n + x)dla wszystkich x >= 0, tj. Element jest zawsze na stosie A, bez względu na to, ile operacji kolejki jest wykonywanych.

• X := ten element

Wtedy możemy zdefiniować

• Abv(n) :=liczba przedmiotów w stosie A(n)powyżej X

• Blo(n) :=liczba elementów w stosie A(n)poniżej X

  | A (n) | = Abv (n) + Blo (n)

ASRT1 :=Liczba popów wymagana do usunięcia X z kolejki Q(n)wynosi co najmniejAbv(n)

Od ( ASRT0) i ( ASRT1), ASRT2 := Abv(n)muszą być ograniczone.

Jeśli Abv(n)jest nieograniczony, to jeśli do usunięcia z kolejki X jest wymaganych 20 po usunięciu z kolejki Q(n), będzie to wymagało co najmniej Abv(n)/20wyskoków. Który jest nieograniczony. 20 może być dowolną stałą.

W związku z tym,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

musi być nieograniczony.

WLOG3, możemy wybrać elementy K od dołu A(n), a jeden z nich jest A(n + x)dla wszystkichx >= 0

X(n) := ten element dla dowolnego n

ASRT4 := Abv(n) >= |A(n)| - K

Za każdym razem, gdy element jest umieszczany w kolejce do Q(n)...

WLOG4przypuśćmy, że B i C są już wypełnione do górnych granic. Załóżmy, że osiągnięto górną granicę dla elementów powyżej X(n). Następnie nowy element wchodzi do A.

WLOG5załóżmy, że w rezultacie nowy element musi zostać wprowadzony poniżej X(n).

ASRT5 := Liczba wyskakujących okienek wymagana do umieszczenia elementu poniżej X(n) >= Abv(X(n))

Od (ASRT4), Abv(n)jest nieograniczony na n.

Dlatego liczba wyskakujących okienek wymaganych do umieszczenia elementu poniżej X(n)jest nieograniczona.

Jest to sprzeczne z ASRT1tym, że nie można zasymulować O(1)kolejki z 3 stosami.

To znaczy

Co najmniej 1 stos musi być nieograniczony.

W przypadku elementu, który pozostaje w tym stosie, liczba elementów powyżej niego musi być ograniczona lub operacja usunięcia z kolejki w celu usunięcia tego elementu będzie nieograniczona.

Jeśli jednak liczba elementów powyżej jest ograniczona, osiągnie limit. W pewnym momencie nowy element musi wejść pod nią.

Ponieważ zawsze możemy wybrać stary element spośród jednego z kilku najmniejszych elementów tego stosu, nad nim może znajdować się nieograniczona liczba elementów (w oparciu o nieograniczony rozmiar nieograniczonego stosu).

Aby wprowadzić nowy element pod nim, ponieważ nad nim znajduje się nieograniczona liczba elementów, wymagana jest nieograniczona liczba wyskoków, aby umieścić nowy element pod nim.

I stąd sprzeczność.

Istnieje 5 stwierdzeń WLOG (bez utraty ogólności). W pewnym sensie można je intuicyjnie zrozumieć jako prawdziwe (ale biorąc pod uwagę, że mają 5 lat, może to zająć trochę czasu). Formalny dowód, że nie utracono żadnej ogólności, można uzyskać, ale jest on niezwykle długi. Zostały pominięte.

Przyznaję, że takie pominięcie może pozostawić kwestionowane wypowiedzi WLOG. Jeśli masz paranoję programisty dotyczącą błędów, zweryfikuj oświadczenia WLOG, jeśli chcesz.

Trzeci stos również nie ma znaczenia. Liczy się to, że istnieje zestaw ograniczonych stosów i zestaw nieograniczonych stosów. Minimum potrzebne na przykład to 2 stosy. Oczywiście liczba stosów musi być ograniczona.

Wreszcie, jeśli mam rację, że nie ma dowodu, powinien być dostępny łatwiejszy dowód indukcyjny. Prawdopodobnie na podstawie tego, co dzieje się po każdej kolejce (obserwuj, jak wpływa to na najgorszy przypadek usunięcia z kolejki, biorąc pod uwagę zestaw wszystkich elementów w kolejce).

Uwaga: ma to być komentarz do funkcjonalnej implementacji kolejek czasu rzeczywistego (w najgorszym przypadku o stałym czasie) z listami połączonymi pojedynczo. Nie mogę dodawać komentarzy ze względu na reputację, ale byłoby miło, gdyby ktoś mógł to zmienić na komentarz dołączony do odpowiedzi przez antti.huima. Z drugiej strony, komentarz jest trochę długi.

@ antti.huima: Połączone listy to nie to samo, co stos.

• s1 = (1 2 3 4) - połączona lista z 4 węzłami, z których każdy wskazuje ten po prawej stronie i zawiera wartości 1, 2, 3 i 4

• s2 = popped (s1) --- s2 to teraz (2 3 4)

W tym momencie s2 jest równoważne popped (s1), które zachowuje się jak stos. Jednak s1 jest nadal dostępny w celach informacyjnych!

• s3 = popped (popped (s1)) --- s3 is (3 4)

Nadal możemy zajrzeć do s1, aby uzyskać 1, podczas gdy we właściwej implementacji stosu element 1 zniknął z s1!

Co to znaczy?

• s1 to odniesienie do szczytu stosu
• s2 to odniesienie do drugiego elementu stosu
• s3 jest odniesieniem do trzeciego ...

Utworzone teraz dodatkowe połączone listy służą jako odniesienie / wskaźnik! Skończona liczba stacków nie może tego zrobić.

Z tego, co widzę w artykułach / kodzie, wszystkie algorytmy wykorzystują tę właściwość list połączonych, aby zachować odniesienia.

Edycja: odnoszę się tylko do algorytmów list połączonych 2 i 3, które wykorzystują tę właściwość list połączonych, ponieważ czytałem je najpierw (wyglądały na prostsze). Nie ma to na celu pokazania, że ​​są lub nie mają zastosowania, tylko po to, aby wyjaśnić, że połączone listy niekoniecznie są identyczne. Przeczytam ten z 6, kiedy będę wolny. @Welbog: Dzięki za korektę.

Lenistwo może również symulować funkcjonalność wskaźnika w podobny sposób.

Korzystanie z listy połączonej rozwiązuje inny problem. Strategia ta może być użyta do implementacji kolejek czasu rzeczywistego w Lisp (lub przynajmniej Lisps, który nalega na budowanie wszystkiego z list połączonych): Zobacz "Operacje kolejki w czasie rzeczywistym w Pure Lisp" (link do linków antti.huima). Jest to również dobry sposób na projektowanie niezmiennych list z czasem działania O (1) i współdzielonymi (niezmiennymi) strukturami.

Możesz to zrobić w amortyzowanym, stałym czasie z dwoma stosami:

------------- --------------
            | |
------------- --------------

Dodawanie jest O(1)i usuwanie jest O(1)wtedy, gdy strona, z której chcesz wziąć, nie jest pusta iw O(n)inny sposób (podziel drugi stos na dwie części).

Sztuczka polega na tym, aby zobaczyć, że O(n)operacja będzie wykonywana tylko za każdym O(n)razem (jeśli podzielisz, np. Na pół). Stąd średni czas operacji wynosi O(1)+O(n)/O(n) = O(1).

Chociaż może się to wydawać problemem, jeśli używasz języka imperatywnego ze stosem opartym na tablicach (najszybszym), i tak będziesz mieć amortyzowany stały czas.