Czy w jednej tablicy można zaimplementować trzy stosy z czasem push / pop O (1)?

Dwa stosy można skutecznie zaimplementować za pomocą jednej tablicy o stałym rozmiarze: stos nr 1 zaczyna się od lewego końca i rośnie w prawo, a stos nr 2 zaczyna się od prawego końca i rośnie w lewo. Czy to samo jest możliwe dla trzech stosów?

Mówiąc dokładniej, czy możliwe jest wdrożenie trzech stosów, biorąc pod uwagę następujące warunki:

Masz tablicę o stałym rozmiarze, która może pomieścić N obiektów.
Dopóki suma trzech rozmiarów stosu wynosi <N, push () nie powinien zawieść.
Zarówno operacje push (), jak i pop () powinny zająć czas O (1).
Oprócz tablicy możesz użyć tylko dodatkowego miejsca O (1).

Oto przykłady rozwiązań, które nie spełniają tych wymagań:

Podział tablicy na 3 stałe części i użycie każdej części do stosu (narusza 2).
Podobnie jak powyżej, ale z ruchomymi granicami między stosami (narusza 3).
Proste implementacje oparte na listach połączonych (narusza 4).

Przyjmę nietrywialne algorytmy lub dowody niemożności, nawet jeśli nie spełniają one wszystkich warunków (1) - (4) dokładnie, na przykład algorytm, w którym push / pop zajmuje zamortyzowany czas O (1) lub gdzie dodatkowa pamięć jest mniejsza niż O (N), np. O (log N). Lub dowód niemożności, który pokazuje, że na przykład dostęp do mniej niż 5 elementów tablicy na push / pop jest niemożliwy.

ds.data-structures lower-bounds

— użytkownik 1020406
źródło

Nie wiem, czy uważasz to za naruszenie wymogu 4, ale jeśli każdy „obiekt” w tablicy N obiektów może zawierać dodatkowe pole, takie jak indeks liczb całkowitych, możesz zaimplementować „listy połączone” w swojej tablicy . Możesz przytrzymać indeks górnej części każdego z 3 stosów za pomocą 3 zmiennych zewnętrznych, a każdy „obiekt” może wskazywać na poprzedni element, który ma stos.

— Avi Tal

Przez „obiekty” rozumiałem rzeczy, które push () akceptuje, a pop () zwraca. Z punktu widzenia implementacji stosu są to po prostu nieprzezroczyste obiekty BLOB danych (na przykład obiekt może być 32-bitową liczbą całkowitą). Implementacja stosu nie powinna w żaden sposób modyfikować tych obiektów.

— user1020406

Rozważ, że najpierw wykonujesz sekwencję operacji wypychania, a następnie tylko operacje pop. Czy coś wiadomo o tej wersji problemu?

N

$N$

— Dmitri Urbanowicz

Czy dodatkowej przestrzeni Cię zadowoli?

O (\sqrt{N})

$O(\sqrt{N})$

— Dmitri Urbanowicz

Re: Wersja „N popycha, a potem N wyskakuje”: Nie wiem, ale nawet zidentyfikowanie tego jako interesującego podproblemu jest przydatne, ponieważ nawet tam nie jest jasne, czy możliwe jest rozwiązanie O (1). Zobacz odpowiedź @ Alexei i jej wątek komentarza dla górnej granicy. Jeśli chodzi o rozwiązanie , tak, zaakceptuję. Jestem nowy w publikowaniu pytań na temat wymiany stosów, więc nie jestem pewien, jak radzić sobie z przypadkami, w których z czasem można uzyskać coraz lepsze rozwiązania. Jednym z podejść, jakie widziałem, było odczekanie około dnia przed zaakceptowaniem odpowiedzi na wypadek opublikowania czegoś lepszego, więc zrobię to.

O (\sqrt{N})

$O(\sqrt N)$

— użytkownik1020406

Odpowiedzi:

Fredman i Goldsmith wykazali w „Three Stacks” (Journal of Algorithms, 1994), że możliwe jest osiągnięcie kawałków zmarnowanej przestrzeni. Jest to również minimum potrzebne dla tablic o rozmiarze co najmniej 16 quattuordecillion yottabajtów. Opisałem prosty algorytm marnujący słowa miejsca w mojej odpowiedzi StackOverflow na to pytanie . Jak wspomniano w komentarzach @ dmitri-urbanowicz, po prostu traktuje tablicę jako bloków o rozmiarze , gdzie każdy blok jest używany dla dokładnie jednego stosu i zawiera pojedynczy wskaźnik do następnego bloku w tym stosie. $\Theta(n^\varepsilon)$ $\Theta(\sqrt{n})$ $\sqrt{n}$ $\sqrt{n}$

— jbapple
źródło

Niech N będzie długością podstawowej tablicy. Mogę sobie wyobrazić stosy jako połączone listy dużych porcji, dzięki czemu ogólna liczba porcji nie będzie większa niż O (log2 (N)). Umieść trzeci stos między pierwszymi dwoma, o indeksie N / 2. Mamy więc 3 zajęte obszary i 2 bezpłatne. Jeśli stos nie może przyjąć następnego elementu, oznacza to, że jeden wolny obszar jest wyczerpany. Jeśli druga też się wyczerpie, cała pamięć zostanie wyczerpana. W przeciwnym razie istnieje inny wolny obszar o rozmiarze nie większym niż N / 2. Kontynuuj przepełniony stos w tym wolnym obszarze. dzięki czemu cała konfiguracja przypomina początkowy układ stosów. Ponieważ wolna pamięć jest teraz nie większa niż połowa początkowej, nie będzie więcej niż log2 (N) takich operacji łączenia. Każda operacja łączenia wymaga stałej ilości pamięci, aby zapisać poprzedni stan stosu. Więc,

— Aleksiej Kaigorodov
źródło

Jak przetwarzacie pamięć uzyskaną przez wyskakiwanie rzeczy z jednego z dużych kawałków?

— Emil Jeřábek

Dobre pytanie. Szybka odpowiedź jest taka, że fragment, który staje się wolny, zwraca swoją pamięć do wolnego obszaru, z którego został wcześniej pobrany. Ale co, jeśli wolny obszar skurczył się od czasu przydziału pamięci dla tego fragmentu, a fragment ten nie sąsiaduje z nim? Prowadzi to do fragmentacji wolnej pamięci, mogą istnieć więcej niż 2 wolne obszary, co rujnuje całą moją konstrukcję.

— Aleksiej Kaigorodow

Występowanie rzeczywiście stanowi problem, ale konstrukcja Aleksieja stanowi dobrą górną granicę dla wersji problemu, o którą pytał Dmitri w komentarzach: co zrobić, jeśli wymagamy, aby wszystkie pchnięcia miały miejsce przed wszystkimi popami? Zastanawiam się, czy w tym przypadku jest możliwe coś lepszego niż O (log N).

— user1020406