Najlepsza odpowiedź
W informatyce , abstrakcyjny typ danych ( ADT ) to model matematyczny dla typy danych , w których typ danych jest określony przez ich zachowanie ( semantyka ) z punktu widzenia użytkownik danych, w szczególności w zakresie możliwych wartości, możliwych operacji na danych tego typu oraz zachowania tych operacji. Kontrastuje to ze strukturami danych , które są konkretnymi reprezentacjami danych i są punktem widzenia osoby wdrażającej, a nie użytkownika.
Ze struktury danych :
W informatyce , struktura danych to szczególny sposób organizowania danych w komputerze, aby można było ich używać wydajnie .
Struktury danych mogą implementować jeden lub więcej określonych abstrakcyjnych typów danych (ADT), które służą do określenia umowy operacji i ich złożoności
Struktura danych to konkretna implementacja kontraktu dostarczona przez ADT
Co to oznacza:
1. ADT jest abstrakcyjną reprezentacją z punktu widzenia użytkownika
2. DS jest konkretna reprezentacja, nie z punktu widzenia użytkownika
Krótko mówiąc:
1. Stos to ADT , określa on tylko, że użytkownik powinien użyć push, pop itp.
2. Stos (podobnie jak inne ADT, takie jak Queue) jest implementowany przy użyciu DS, np. tablica lub lista (lista połączona itp.)
Podsumowanie:
Stos nie jest DS, ale ADT i jest zaimplementowany przy użyciu inne DS.
Mam nadzieję, że pomogło.
Powodzenia
Odpowiedź
Stosy
Stos to kontener obiektów, które są wstawiane i usuwane zgodnie z zasadą „ostatni na wejściu, pierwszy na wyjściu” (LIFO). W stosach przesuwających w dół dozwolone są tylko dwie operacje: wepchnij element do stosu i pop przedmiot ze stosu. Stos jest strukturą danych o ograniczonym dostępie – elementy można dodawać i usuwać ze stosu tylko na górze. push dodaje element na szczyt stosu, pop usuwa element z góry . Pomocną analogią jest myślenie o stosie książek; możesz usunąć tylko pierwszą książkę, a także możesz dodać nową książkę na górze.
Stos to rekurencyjna struktura danych. Oto strukturalna definicja stosu:
Aplikacje
- Najprostszym zastosowaniem stosu jest odwrócenie słowa. Przesuwasz dane słowo do stosu – litera po literze – a następnie wyrzucasz litery ze stosu.
- Inną aplikacją jest mechanizm „cofania” w edytorach tekstu; ta operacja jest wykonywana poprzez przechowywanie wszystkich zmian tekstu w stosie. Wycofywanie . Jest to proces, w którym musisz uzyskać dostęp do najbardziej aktualnego elementu danych w serii elementów. Pomyśl o labiryncie lub labiryncie – jak znaleźć drogę od wejścia do wyjścia? Ale cofnąć się gdzie? do poprzedniego punktu wyboru. Dlatego w każdym momencie wyboru przechowujesz na stosie wszystkie możliwe wybory. Następnie cofanie oznacza po prostu zdejmowanie kolejnego wyboru ze stosu.
- Przetwarzanie języka: miejsce na parametry i zmienne lokalne jest tworzone wewnętrznie przy użyciu metody stack.compiler sprawdzanie składni pasujących nawiasów klamrowych jest implementowane przy użyciu stack.support dla rekurencji
Implementacja
W standardowej bibliotece klas stosem typów danych jest adapter , co oznacza, że stos jest zbudowany na wierzchu innych struktur danych. Podstawową strukturą stosu może być tablica, wektor, ArrayList, lista połączona lub dowolny inny zbiór. Niezależnie od typu podstawowej struktury danych, stos musi implementować tę samą funkcjonalność.Osiąga się to poprzez zapewnienie unikalnego interfejsu:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
Poniższy rysunek przedstawia ideę wdrożenia według składu .
Innym wymogiem implementacji (oprócz powyższego interfejsu) jest to, że wszystkie operacje na stosie muszą być wykonywane w
stałym czasie O (1)
. Stały czas oznacza, że istnieje pewna stała k taka, że operacja zajmuje k nanosekund czasu obliczeniowego niezależnie od rozmiaru stosu.
Implementacja oparta na tablicach
W implementacji opartej na tablicach utrzymujemy następujące pola: tablica A o domyślnym rozmiarze (≥ 1 ), zmienna top , która odnosi się do najwyższego elementu w stosie i pojemność , która odnosi się do rozmiaru tablicy. Zmienna top zmieni się z -1 na capacity - 1. Mówimy, że stos jest pusty, gdy top = -1, a stos jest pełny, gdy top = capacity-1.
W stałej -size abstrakcji stosu, pojemność pozostaje niezmieniona, dlatego gdy top osiągnie pojemność , stos obiekt zgłasza wyjątek.
W dynamicznej abstrakcji stosu, gdy top osiągnie pojemność podwajamy rozmiar stosu.
Implementacja oparta na liście połączonej
Oparta na liście połączonej implementacja zapewnia najlepszą (z punktu widzenia wydajności) implementację stosu dynamicznego.
Źródło – Stosy i kolejki