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.
Wtedy możemy zdefiniować
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).