Odwracanie listy przy użyciu dwóch kolejek

To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N elementów przy użyciu dwóch początkowo pustych kolejek? Czynności prawne to:$O(1)$$N$

1. Kolejkuj następny element z listy wprowadzania (do końca każdej kolejki).
2. Usuń z kolejki element na początku każdej kolejki i umieść go ponownie w kolejce (do końca każdej kolejki).
3. Usuń element z nagłówka każdej kolejki i dodaj go do listy wyników.

Jeżeli lista wejściowy składa się z elementów, , w jaki sposób minimalna liczba operacji potrzebnych do wytworzenia wyjściowej listy odwróconej [ N , N - 1 , . . . , 2 , 1 ] zachowują się? Szczególnie interesujący byłby dowód, że rośnie on szybciej niż O ( N ) , ponieważ rozwiązałby pierwotne pytanie przecząco.$[1,2,...,N-1,N]$$[N,N-1,...,2,1]$$O(N)$

Aktualizacja (15 stycznia 2011 r.): Problem można rozwiązać w , jak pokazano w przesłanych odpowiedziach i ich komentarzach; a dolna granica Ω ( N ) jest trywialna. Czy którąkolwiek z tych granic można poprawić?$O(N \log N)$$\Omega(N)$

Jeśli N jest potęgą dwóch, uważam, że operacje O (N log N) są wystarczające, nawet w przypadku nieco bardziej ograniczonego problemu, w którym wszystkie elementy zaczynają się w jednej z kolejek i muszą kończyć w odwrotnej kolejności na jednej z kolejek (bez listy wejść i wyjść).

W krokach O (N) można zacząć od wszystkich elementów w jednej kolejce, grać „jeden dla ciebie jeden dla mnie”, aby podzielić je na przemienne podzbiory w drugiej kolejce, a następnie połączyć je wszystkie z powrotem w jedną kolejkę. Pod względem binarnych reprezentacji pozycji elementów, realizuje to operację obrotu.

W krokach O (N) można również wyciągać pary elementów z jednej kolejki, zamieniać je, a następnie odkładać z powrotem, odwracając wszystkie pary. Pod względem binarnych reprezentacji pozycji przedmiotów uzupełnia to bit pozycji niskiego rzędu.

Powtarzając O (log N) razy odtasowanie i zamianę parami, możemy uzupełnić wszystkie bity reprezentacji binarnych pozycji - co jest tym samym, co odwrócenie listy.

$\sum_{i=0}^{N/2-1}(N-2i-2)$

Pozwala nazwać dwie dostępne kolejki jako lewą i prawą. Oto podstawowa idea tego algorytmu przy założeniu, że N jest parzyste:

1. Odczytaj wartości z początkowej listy elementów i wepchnij wszystkie nieparzyste liczby do lewej kolejki, a nawet liczby parzyste do prawej kolejki
2. Jednym z pierwszych kroków najszybszym sposobem na wyprowadzenie maksymalnej wartości jest przeniesienie elementów N / 2-1 z prawej kolejki do lewej i umieszczenie najwyższej wartości z prawej kolejki na liście wyników
3. Teraz musimy zrobić to samo dla kolejnej kolejki - przenieść elementy N / 2-1 z kolejki lewej do prawej i wrzucić górny element z kolejki lewej do listy wyników
4. Zamień kolejki i powtórz kroki 2 i 3 dla N = N-2

Łatwo jest zobaczyć, jak algorytm powinien działać dla nieparzystego N.