Jak zaimplementować kolejkę z trzema stosami?

Ok, to jest naprawdę trudne, a jedyne rozwiązanie, jakie udało mi się wymyślić, przypomina mi rozwiązanie Kirksa do testu Kobayashi Maru (jakoś oszukany): Chodzi o to, że używamy stosu stosów (i używamy tego do modelowania listy). Wywołuję operacje en / dequeue i push i pop, wtedy 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 nie jest kopiowaniem zawartości, jest tylko kopią referencji. To po prostu opisać to łatwo. Możesz również użyć tablicy 3 stosów i uzyskać do nich dostęp za pośrednictwem indeksu, tam będziesz wystarczy zmienić wartość zmiennej index). Wszystko jest w O(1)w Warunkach stosu operacji.

I tak Wiem, że to możliwe, ponieważ mamy ukryte więcej niż 3 stosy, ale może to dać innym z Was dobre pomysły.

EDIT: Explanation example:

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

Próbowałem tutaj z odrobiną ASCII-art, aby pokazać Stack1.

Każdy element jest zawinięty w pojedynczy stos elementów (więc mamy tylko typesafe stack of stacks).

You see to remove we first pop the first element (stos zawierający tutaj element 1 i 2). Następnie pop następny element i rozpakować tam 1. Następnie mówimy, że pierwszy poped stos jest teraz naszym nowym Stack1. Mówiąc nieco bardziej funkcjonalnie-są to listy zaimplementowane przez stosy 2 elementów, gdzie górny element ist cdr, a pierwszy / poniżej górny element to car . Pozostałe dwie pomagają stacks ' owi.

Esp trudne jest wstawianie, jak trzeba jakoś zanurkować głęboko w zagnieżdżone stosy, aby dodać kolejny element. Dlatego Stack2 tam jest. Stack2 jest zawsze najbardziej wewnętrznym stosem. Dodawanie polega na wciśnięciu elementu, a następnie wciśnięciu nowego Stack2 (i dlatego nie możemy dotykać Stack2 w naszej operacji dequeue).

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.

Twierdzenia

• ASRT0: = ponadto Załóżmy, że Q może symulować operacje {queue, dequeue} w O(1). Oznacza to, że istnieje określona sekwencja wypychania stosu/wyskakiwania dla każdej operacji queue/dequeue, 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, ..., na podstawie ich kolejności kolejek, z pierwszym elementem, który jest w kolejce do Q jest zdefiniowany jako 1, drugi jako 2, i tak dalej.

Define

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

Define

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

I podobne definicje dla stosów B i C.

Trywialnie,

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

---

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

Dlatego przynajmniej jeden z |A(n)|, |B(n)| lub |C(n)| jest nieograniczona na N.

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

Define * B_u := górna granica B * C_u := górna granica C * K := B_u + C_u + 1

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

• X := ten element

Wtedy możemy zdefiniować

• Abv(n) := Liczba pozycji w stosie A(n), która jest powyżej X

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

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

ASRT1 := Liczba wyskakujących okienek wymagana do dequeue X z Q(n) wynosi co najmniej Abv(n)

Od (ASRT0) i (ASRT1), ASRT2 := Abv(n) musi być ograniczony.

Jeśli Abv(n) jest unbounded, to jeśli 20 dequeues są wymagane do dequeue X od Q(n), będzie wymagało co najmniej Abv(n)/20 tato. Co jest nieograniczone. 20 może być dowolną stałą.

Dlatego,

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

Musi być nieograniczona.

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

X(n) := tego pierwiastka, dla dowolnego N

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

Gdy element jest w kolejce do Q(n)...

WLOG4, Załóżmy, że B I C są już wypełnione do swoich górnych granic. Załóżmy, że górna granica dla elementów powyżej X(n) została / align = "left" / Następnie nowy element wchodzi w A.

WLOG5, Załóżmy, że w rezultacie nowy element musi wejść poniżej X(n).

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

Od (ASRT4), Abv(n) jest nieograniczona na n

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

Jest to sprzeczne ASRT1, dlatego nie jest możliwe symulowanie O(1) kolejki z 3 stosy.

Tzn.

Co najmniej 1 stos musi być nieograniczony.

Dla elementu, który pozostaje w tym stosie, liczba elementów powyżej niego musi być ograniczona, lub operacja dequeue, aby usunąć ten element, będzie nieograniczona.

Jednakże, jeśli liczba elementów powyżej niego jest ograniczona, to osiągnie limit. W pewnym momencie Nowy element musi wejść poniżej niego.

Ponieważ zawsze możemy wybrać stary element spośród kilku najniższych elementów z tego stosu może istnieć Nieograniczona liczba elementów nad nim (na podstawie nieograniczonej wielkości stosu).

Aby wprowadzić nowy element pod nim, ponieważ istnieje nieograniczona liczba elementów nad nim, do umieszczenia nowego elementu pod nim wymagana jest nieograniczona liczba wyskakujących okienek.

I tym samym sprzeczność.

Istnieje 5 twierdzeń WLOG (bez utraty ogólności). W pewnym sensie mogą być intuicyjnie rozumiane jako prawdziwe (ale biorąc pod uwagę, że są 5, może to trochę potrwać). Formalny dowód, że żadna ogólność nie jest stracona, może być wyprowadzony, ale jest bardzo długi. Są pominięte.

Przyznaję, że takie pominięcie może pozostawić wypowiedzi WLOG Pod znakiem zapytania. Z paranoją programisty na błędy, proszę zweryfikować 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 dla przykładu to 2 stosy. Liczba stosów musi być oczywiście ograniczona.

Uwaga: ma to być komentarz do funkcjonalnej implementacji kolejek czasu rzeczywistego ( constant time worst case ) Z pojedynczo-linkowanymi listami. 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 antti.huima. Z drugiej strony, jest to dość długi komentarz.

@antti.huima: Listy połączone nie są takie same jak stos.

• S1 = (1 2 3 4) --- połączoną listę z 4 węzłami, z których każdy wskazuje na jeden po prawej stronie i trzymając wartości 1, 2, 3 i 4

• S2 = (S1) - - - s2 jest teraz (2 3 4)

W tym momencie S2 jest odpowiednikiem popped( s1), który zachowuje się jak stos. Jednak s1 jest nadal dostępny w celach informacyjnych!

• s3 = popped (popped(S1)) - - - s3 to (3 4)

Możemy jeszcze zajrzeć do s1, aby uzyskać 1, podczas gdy w odpowiedniej implementacji stosu, element 1 zniknął z s1!

Co to znaczy?

• s1 jest odniesieniem do the top of the stack
• s2 jest odniesieniem do drugiego elementu stosu
• s3 jest odniesieniem do trzeciego ...

Dodatkowe listy linked-list utworzone teraz każda służy jako odniesienie / wskaźnik! Skończona liczba stosów nie może tego zrobić.

Z tego, co widzę w dokumentach/kodzie, algorytmy wykorzystują tę właściwość list linked, aby zachować odniesienia.

Edit: mam na myśli tylko algorytmy 2 i 3 linked-list, które wykorzystują tę właściwość linked-List, jak je przeczytałem pierwszy (wyglądały prostsze). Nie ma to na celu pokazania, że są lub nie mają zastosowania, tylko wyjaśnienie, że listy połączone niekoniecznie są identyczne. Przeczytam ten z 6, Jak będę wolny. @Welbog: dzięki za korektę.

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

Używanie linked-list rozwiązuje inny problem. Ta strategia może być użyta do implementacji kolejek w czasie rzeczywistym w Lispie (lub przynajmniej Lispie to wymaga budowania wszystkiego z linked-lists): Patrz "operacje kolejki w czasie rzeczywistym w Pure Lispie" (linked to through antti.linki 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 stałym czasie za pomocą dwóch stosów:

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

Dodawanie jest O(1) i usuwanie jest O(1) jeśli strona, z której chcesz wziąć nie jest pusta i O(n) w przeciwnym razie (podziel drugi stos na dwa).

Sztuczka polega na tym, że operacja {[3] } będzie wykonywana tylko co O(n) czas (jeśli podzielisz się, np. na połówki). Stąd średni czas operacji wynosi O(1)+O(n)/O(n) = O(1).

Chociaż może to być problem, jeśli używasz imperatywnego języka z tablicą oparty stos (najszybszy), będziesz miał tylko zamortyzowany stały czas i tak.