Jak zaimplementować dwa stosy w jednej tablicy?

Chciałbym zacząć od stwierdzenia, że ​​to NIE jest zadanie domowe. Czytam Wstęp do algorytmów - słynny tekst CLRS, aby stać się lepszym programistą. Próbuję samodzielnie rozwiązać problemy i ćwiczenia podane w książce.

Próbuję rozwiązać Ćwiczenie 10.1-2 z rozdziału 10 Elementarne struktury danych z CLRS wydanie drugie. Oto, co jego stany:

Wyjaśnij, jak zaimplementować dwa stosy w jednej tablicy A [1..n] w taki sposób, aby żaden stos nie został przepełniony, chyba że łączna liczba elementów w obu stosach wynosi n . Operacje PUSH i POP powinny działać w czasie O (1) .

Rozwiązaniem, które do tej pory wymyśliłem, jest:

Niech tablica A [1..n] zaimplementuje dwa stosy: S1 [1..i] i S2 [i..n] .

W przypadku operacji PUSH-S1 i PUSH-S2 , jeśli stos jest „pełny”, zacznij wypychać elementy do drugiego stosu (np. Jeśli stos S1 jest pełny, gdy nowy element próbuje zostać wepchnięty, a następnie wepchnij ten element do stos S2 i odwrotnie).

Problem z tym podejściem polega na tym, że nie będę w stanie niezawodnie korzystać z POP-S1 lub POP-S2, ponieważ nie ma możliwości „zapamiętania”, który element należy do którego stosu. Jeśli elementy stosu są parami (klucz, wartość) , kluczem jest numer stosu, to aby wyskoczyć z elementu, musiałbym wyszukać, w najgorszym przypadku, i lub (ni) razy - które będą O (n ) (możesz mnie poprawić, jeśli się tu mylę), co nie byłoby O (1) .

Od dłuższego czasu zastanawiam się nad tym pytaniem. Czy jestem na dobrej drodze? Czy ktoś może podać moje możliwe wskazówki dotyczące rozwiązania tego problemu?

Ogólnie, jak powinienem „pomyśleć” o tych problemach? Czy tylko naprawdę inteligentni ludzie mogą rozwiązać tego rodzaju problemy? Czy rozwiązywanie takich problemów (np. Zdobywanie doświadczenia) pomoże mi stać się w tym lepszym?

Czekam na oświecenie.

Kolejna wskazówka oprócz tego, co powiedział Yuval: pomaga umieszczać stosy w określony sposób w tablicach i odpowiednio ustalać ich kierunek wzrostu. Nie muszą rosnąć w tym samym kierunku.

Oto kilka wskazówek:

1. Jeden ze stosów powinien rosnąć „w górę”, a drugi „w dół”.
2. Nie ma możliwości „zapamiętania”, który element należy do którego stosu - możesz użyć dodatkowych zmiennych, które pomogą ci w takich rzeczach. (Ma to większy sens w przypadku rozwiązania zaproponowanego w pierwszej podpowiedzi.)

Pierwszy stos zaczyna się od 1 i rośnie w kierunku n, a drugi zaczyna od n, a rośnie w kierunku 1. Przepełnienie stosu następuje, gdy element jest popychany, gdy dwa wskaźniki stosu sąsiadują ze sobą.

Ta metoda efektywnie wykorzystuje dostępną przestrzeń. Nie powoduje przepełnienia, jeśli w arr [] jest dostępne miejsce. Chodzi o to, aby rozpocząć dwa stosy z dwóch skrajnych rogów arr []. stos1 zaczyna się od skrajnie lewego elementu, pierwszy element na stosie 1 jest przesuwany na indeks 0. Stos2 zaczyna się od skrajnego prawego rogu, pierwszy element na stosie 2 jest przesuwany na indeks (n-1). Oba stosy rosną (lub kurczą się) w przeciwnym kierunku. Aby sprawdzić przepełnienie, wystarczy sprawdzić przestrzeń między górnymi elementami obu stosów.

Myślałem o innym rozwiązaniu. Jeśli podzielimy tablicę na pół (lub tak blisko, jak to możliwe, jeśli tablica ma nieparzystą długość) i sprawimy, że pierwszy element przejdzie do pierwszego stosu, a drugi element do drugiego stosu. Podczas wyskakiwania możemy odtworzyć te kroki. Jednak wdrożenie w ten sposób naruszałoby zasadę stosu?

Kilka wskazówek

Zrób tablicę

Elementy tablicy o nieparzystym indeksie są dla stosu1

Elementy tablicy z parzystym indeksem są dla stosu2

Teraz możesz wyhodować oba stosy od lewej do prawej strony

Wystarczy zachować zmienne, które utrzymują najwyższą pozycję obu stosów. Nie będziesz musiał przeszukiwać tablicy.

a jeśli stos1 zapełni się, gdy stos2 będzie pusty, możesz śledzić dodatkowe elementy stosu1 na stosie 2, zachowując niektóre zmienne