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.