Jaka jest różnica między tablicą a stosem?

Według Wikipedii stos :

to abstrakcyjny typ danych ostatni i pierwszy (LIFO) i liniowa struktura danych.

Podczas gdy tablica :

to struktura danych składająca się z kolekcji elementów (wartości lub zmiennych), z których każdy jest identyfikowany przez co najmniej jeden indeks lub klucz tablicy.

O ile rozumiem, są one dość podobne. Jakie są główne różnice? Jeśli nie są takie same, to co może zrobić tablica, której nie potrafi stos i odwrotnie?

Z pewnością możesz zaimplementować stos za pomocą tablicy. Różnica polega na dostępie. W tablicy masz listę elementów i możesz uzyskać do nich dostęp w dowolnym momencie. (Pomyśl o kilku drewnianych klockach ułożonych w jednym rzędzie).

Ale na stosie nie ma operacji losowego dostępu; istnieje tylko Push, Peeki Popwszystkie, które zajmują się wyłącznie z elementu na szczycie stosu. (Pomyśl o drewnianych klockach ułożonych pionowo w stos. Nie możesz dotknąć niczego pod szczytem wieży, inaczej spadnie).

W czystej stosie, jedyne dopuszczalne są operacje Push, PoporazPeek ale z praktycznego punktu widzenia, to nie do końca prawda. A raczej Peekoperacja często pozwala spojrzeć na dowolną pozycję na stosie, ale haczyk polega na tym, że jest on związany z jednym końcem stosu.

Tak więc, jak powiedzieli inni, tablica ma dostęp losowy i wszystko odnosi się do początku tablicy .

W stosie możesz dodawać / usuwać tylko na roboczym końcu stosu, ale nadal masz dostęp do odczytu losowego ale jest on powiązany z działającym końcem . To podstawowa różnica.

Na przykład, gdy przekazujesz parametry do stosu do funkcji, odbiorca nie musi odrywać parametrów, aby na nie spojrzeć. Po prostu wypycha lokalne zmienne na stos i odwołuje się do wszystkich lokalnych zmiennych i parametrów na podstawie przesunięcia od wskaźnika stosu. Gdybyś używał tylko tablicy, to skąd odbiorca wiedziałby, gdzie szukać jej parametrów? Po zakończeniu wywoływania zrzuca zmienne lokalne, wypycha wartość zwracaną, zwraca kontrolę do wywołującego, a wywołujący zrzuca wartość zwracaną (jeśli istnieje), a następnie usuwa parametry ze stosu. Piękno polega na tym, że działa ono bez względu na to, jak daleko jesteś zagnieżdżony w wywołaniach funkcji (zakładając, że nie zabraknie miejsca na stosie).

To jedno szczególne zastosowanie / implementacja, ale ilustruje różnicę: tablica jest zawsze przywoływana od początku, ale stosy są zawsze przywoływane z pewnej roboczej pozycji końcowej.

Jedną z możliwych implementacji stosu jest tablica plus indeks do zapamiętania, gdzie znajduje się koniec roboczy.

Myślę, że największym nieporozumieniem jest implementacja w porównaniu z podstawowymi strukturami danych.

W większości (bardziej podstawowych języków) tablica reprezentuje zestaw elementów o stałej długości, do którego można uzyskać dostęp w dowolnym momencie. Fakt, że masz wiele takich elementów, nie mówi ci nic o tym, jak powinien być używany (i szczerze mówiąc, komputer nie będzie wiedział / obchodził się, jak go używać, o ile nie naruszasz użytkowania).

Stos to abstrakcja używana do reprezentowania danych, które powinny być obsługiwane w określony sposób. Jest to koncepcja abstrakcyjna, ponieważ mówi tylko, że musi mieć podprogram / metodę / funkcję, która może dodawać do góry lub usuwać z góry, podczas gdy dane poniżej góry nie są dotykane. Twój wybór użycia tablicy w ten sposób.

Możesz utworzyć stos z wielu różnych rodzajów struktur danych: tablic (z pewnym maksymalnym rozmiarem), tablic dynamicznych (może rosnąć, gdy brakuje miejsca) lub połączonych list. Osobiście uważam, że połączona lista najlepiej reprezentuje ograniczenia stosu, ponieważ musisz włożyć trochę wysiłku, aby zobaczyć rzeczy poza pierwszym elementem i bardzo łatwo jest dodać do przodu i usunąć z przodu.

Możesz więc użyć tablicy do utworzenia stosu, ale nie są one równoważne

Ich obowiązki są różne:

• Stos musi mieć możliwość wbijania elementów na stos i wypychania elementów ze stosu, dlatego zwykle ma metody Pop()i metodyPush()

• Obowiązkiem tablicy jest pobranie / ustawienie elementu o określonym indeksie

Możesz pobrać element z dowolnego indeksu tablicy A \.

Za pomocą stosu możesz odzyskać przedmiot na środku stosu A, używając innego stosu: B.

Ciągle wyjmujesz najwyższy przedmiot z A i wkładasz go do B, aż znajdziesz się w pożądanym elemencie A, a następnie odkładasz przedmioty z B z powrotem na stos A.

Tak więc dla danych, które wymagają możliwości pobrania dowolnego indeksu, trudniej jest obsługiwać stos.

W sytuacji, w której chcesz zachować „ostatnie wejście, pierwsze wyjście”, stos da ci mniejszy narzut niż tablica.

Nie posunąłbym się nawet do stwierdzenia, że ​​są „bardzo podobne”.

Tablica służy do przechowywania rzeczy, które później będą dostępne sekwencyjnie lub poprzez indeks. Struktura danych nie sugeruje żadnej metody dostępu (FIFO, LIFO, FILO itp.), Ale można z niej korzystać w ten sposób, jeśli chcesz.

Stos jest sposobem śledzenia rzeczy podczas ich generowania. Metoda dostępu jest implikowana / wymagana w zależności od typu tworzonego stosu. Stos ramek byłby przykładem LIFO. Zastrzeżenie - Być może mieszam tutaj swoją taksonomię struktury danych, a stos może naprawdę zezwalać tylko na LIFO. W przeciwnym razie byłby to inny typ kolejki.

Mógłbym więc użyć tablicy jako stosu (chociaż nie chciałbym), ale nie mogę użyć stosu jako tablicy (chyba że ciężko nad tym pracuję).

Dostęp do danych w tablicy można uzyskać za pomocą klucza lub indeksu. Dostęp do danych w stosie można uzyskać, gdy zostanie on wysunięty z górnej części stosu. Oznacza to, że dostęp do danych z tablicy jest łatwy, jeśli znasz jej indeks. Dostęp do danych ze stosu oznacza, że ​​musisz wyskakiwać elementy, aż znajdziesz ten, którego szukasz, co oznacza, że ​​dostęp do danych może potrwać dłużej.

Tablica jest z perspektywy programistów, ustalona w miejscu i rozmiarze, wiesz, gdzie jesteś i gdzie jest cała ta sprawa. Masz dostęp do wszystkich.

Dzięki stosowi siedzisz na jednym jego końcu, ale nie masz pojęcia o jego wielkości ani o tym, jak bezpiecznie możesz się posunąć. Twój dostęp do niego jest ograniczony do kwoty, którą przydzieliłeś, często nawet nie wiesz, czy przy przydzielaniu żądanej kwoty, jeśli po prostu uderzyłeś w stertę lub przestrzeń programu. Twój widok na stos jest małą tablicą, którą sam przydzieliłeś, jaki rozmiar chciałeś, nad którą masz kontrolę i którą możesz zobaczyć. Twoja porcja nie różni się niczym od tablicy. Różnica polega na tym, że twoja tablica jest przyczepiona do jednego końca drugiej tablicy ze względu na argumenty i terminologię, których nie masz widoczności, nie masz pojęcia, jak duży lub mały, i nie możesz go dotknąć, nie powodując szkody. W każdym razie tablica, chyba że globalna, jest często implementowana na stosie, więc tablica i stos dzielą to samo miejsce na czas trwania tej funkcji.

Jeśli chcesz dostać się do strony sprzętowej, to oczywiście jest ona specyficzna dla procesora, ale ogólnie tablica opiera się na znanym punkcie początkowym / adresie, rozmiar jest znany kompilatorowi / programatorowi, a adresy są w nim obliczane, czasami używając adresowania przesunięcia rejestru (załaduj wartość z adresu zdefiniowanego przez tę podstawową wartość rejestru plus tę wartość rejestru przesunięcia, podobnie po skompilowaniu może to być bezpośrednie przesunięcie niekoniecznie oparte na rejestrze, zależy oczywiście od procesora), które w złożeniu bardzo przypomina dostęp do tablicy w kodzie wysokiego poziomu. Podobnie w przypadku stosu, jeśli jest dostępny, można użyć rejestru lub adresowania natychmiastowego przesunięcia, często jednak używa on specjalnego rejestru, albo samego wskaźnika stosu, albo rejestru zarezerwowanego przez kompilator / programistę do użycia do uzyskania dostępu do ramki stosu w tym celu. funkcjonować. W przypadku niektórych procesorów używane są specjalne funkcje dostępu do stosu i / lub wymagane do uzyskania dostępu do stosu. Masz instrukcje push i pop, ale nie są one używane tak często, jak myślisz i tak naprawdę nie dotyczą tego pytania. W przypadku niektórych procesorów push i pop to aliasy instrukcji, które mogą być używane z dowolnym rejestrem, w dowolnym miejscu, nie tylko wskaźnikiem stosu na stosie, dodatkowo usuwając powiązanie push i pop z tym pytaniem.