Abstrakcyjny typ danych — Abstract data type

Nie mylić z algebraicznym typem danych .

W informatyce , abstrakcyjny typ danych ( ADT ) jest model matematyczny dla typów danych . Abstrakcyjny typ danych jest definiowany przez jego zachowanie ( semantykę ) z punktu widzenia użytkownika danych, w szczególności w zakresie możliwych wartości, możliwych operacji na danych tego typu oraz zachowania się tych operacji. Ten model matematyczny kontrastuje ze strukturami danych , które są konkretnymi reprezentacjami danych i stanowią punkt widzenia realizatora, a nie użytkownika.

Formalnie ADT można zdefiniować jako „klasę obiektów, których zachowanie logiczne jest zdefiniowane przez zestaw wartości i zestaw operacji”; jest to analogiczne do struktury algebraicznej w matematyce. Co rozumie się przez „zachowanie” różni się w zależności od autora, przy czym dwa główne typy formalnych specyfikacji zachowania to specyfikacja aksjomatyczna (algebraiczna) i model abstrakcyjny; Odpowiadają one aksjomatycznych semantyki i semantyki operacyjnych od An abstrakcyjnej maszyny , odpowiednio. Niektórzy autorzy uwzględniają również złożoność obliczeniową („koszt”), zarówno pod względem czasu (w przypadku operacji obliczeniowych), jak i przestrzeni (w przypadku reprezentowania wartości). W praktyce wiele typowych typów danych nie jest ADT, ponieważ abstrakcja nie jest idealna, a użytkownicy muszą być świadomi problemów, takich jak przepełnienie arytmetyczne, które są spowodowane reprezentacją. Na przykład liczby całkowite są często przechowywane jako wartości o stałej szerokości (32-bitowe lub 64-bitowe liczby binarne), dlatego w przypadku przekroczenia maksymalnej wartości występują przepełnienia liczb całkowitych .

ADT są koncepcją teoretyczną w informatyce, używaną do projektowania i analizy algorytmów , struktur danych i systemów oprogramowania i nie odpowiadają specyficznym cechom języków komputerowych — główne języki komputerowe nie obsługują bezpośrednio formalnie określonych ADT. Jednak różne cechy języka odpowiadają pewnym aspektom ADT i można je łatwo pomylić z właściwymi ADT; obejmują one typy abstrakcyjne , nieprzezroczyste typy danych , protokoły i projektowanie według umowy . ADT zostały po raz pierwszy zaproponowane przez Barbarę Liskov i Stephena N. Zillesa w 1974 roku, jako część rozwoju języka CLU .

Przykłady

Na przykład, liczby całkowite są ADT, zdefiniowanymi jako wartości ..., -2, -1, 0, 1, 2, ... oraz przez operacje dodawania, odejmowania, mnożenia i dzielenia wraz z większą niż , mniej niż itp., które zachowują się zgodnie ze znaną matematyką (z dbałością o dzielenie liczb całkowitych ), niezależnie od tego, jak liczby całkowite są reprezentowane przez komputer. Wyraźnie „zachowanie” obejmuje przestrzeganie różnych aksjomatów (łączność i przemienność dodawania itp.) oraz warunków wstępnych dotyczących operacji (nie można dzielić przez zero). Zazwyczaj liczby całkowite są reprezentowane w strukturze danych jako liczby binarne , najczęściej jako uzupełnienie do dwóch , ale mogą to być zakodowane binarnie dziesiętnie lub jako uzupełnienie do jedynek , ale użytkownik jest oderwany od konkretnego wyboru reprezentacji i może po prostu użyć danych jako typy danych.

ADT składa się nie tylko z operacji, ale także z wartości danych źródłowych i ograniczeń operacji. „Interfejs” zazwyczaj odnosi się tylko do operacji i być może niektórych ograniczeń dotyczących operacji, w szczególności warunków wstępnych i warunków końcowych, ale nie innych ograniczeń, takich jak relacje między operacjami.

Na przykład abstrakcyjny stos , który jest strukturą typu „ostatnie weszło-pierwsze wyszło” można zdefiniować za pomocą trzech operacji: push, która wstawia element danych na stos; pop, który usuwa z niego element danych; i peeklub top, który uzyskuje dostęp do elementu danych na szczycie stosu bez usuwania. Abstrakcyjna kolejka , która jest strukturą „pierwsze weszło-pierwsze wyszło”, miałaby również trzy operacje: enqueue, która wstawia element danych do kolejki; dequeue, który usuwa z niego pierwszy element danych; i front, który uzyskuje dostęp i obsługuje pierwszy element danych w kolejce. Nie byłoby sposobu na rozróżnienie tych dwóch typów danych, chyba że zostanie wprowadzone ograniczenie matematyczne, które dla stosu określa, że ​​każdy zdejmowany element zawsze zwraca ostatnio wypchnięty element, który jeszcze nie został zdemontowany. Podczas analizy efektywności algorytmów że stosowanie stosy, jeden może również określić, że wszystkie operacje wykonuje tym samym czasie bez względu na to jak wiele elementów danych zostały wciśnięte w stosie, i że stos wykorzystuje stałą ilość przestrzeni dyskowej dla każdego elementu.

Wstęp

Abstrakcyjne typy danych to czysto teoretyczne byty, używane (między innymi) do uproszczenia opisu abstrakcyjnych algorytmów, klasyfikacji i oceny struktur danych oraz formalnego opisu systemów typów języków programowania. Jednak ADT może być zaimplementowane przez określone typy danych lub struktury danych , na wiele sposobów i w wielu językach programowania; lub opisane w formalnym języku specyfikacji . ADT są często implementowane jako moduły : interfejs modułu deklaruje procedury, które odpowiadają operacjom ADT, czasami z komentarzami opisującymi ograniczenia. Ta strategia ukrywania informacji pozwala na zmianę implementacji modułu bez zakłócania programów klienckich .

Termin abstrakcyjny typ danych można również traktować jako uogólnione podejście wielu struktur algebraicznych , takich jak kraty, grupy i pierścienie. Pojęcie abstrakcyjnych typów danych jest związane z pojęciem abstrakcji danych , ważnej w programowaniu obiektowym i projektowaniu metodologii kontraktowych do tworzenia oprogramowania .

Definiowanie abstrakcyjnego typu danych

Abstrakcyjny typ danych jest zdefiniowany jako model matematyczny obiektów danych, które tworzą typ danych, a także funkcji operujących na tych obiektach. Nie ma standardowych konwencji ich definiowania. Można dokonać szerokiego podziału na „imperatywne” i „funkcjonalne” style definicji.

Definicja stylu imperatywnego

W filozofii imperatywnych języków programowania abstrakcyjna struktura danych jest rozumiana jako jednostka, która jest zmienna — co oznacza, że ​​może znajdować się w różnych stanach w różnym czasie. Niektóre operacje mogą zmienić stan ADT; dlatego kolejność, w której operacje są oceniane, jest ważna, a ta sama operacja na tych samych jednostkach może mieć różne skutki, jeśli jest wykonywana w różnym czasie — tak jak instrukcje komputera lub polecenia i procedury języka imperatywnego. Aby podkreślić ten pogląd, zwyczajowo mówi się, że operacje są wykonywane lub stosowane , a nie oceniane . Styl imperatywny jest często używany przy opisywaniu algorytmów abstrakcyjnych. (Zobacz The Art of Computer Programming autorstwa Donalda Knutha, aby uzyskać więcej informacji)

Zmienna abstrakcyjna

Definicje ADT w stylu imperatywnym często zależą od koncepcji zmiennej abstrakcyjnej , którą można uznać za najprostsze nietrywialne ADT. Abstrakcyjna zmienna V to zmienna encja, która dopuszcza dwie operacje:

  • store( V , x ) gdzie x jest wartością nieokreślonego charakteru;
  • fetch( V ), która daje wartość,

z ograniczeniem, że

  • fetch( V ) zawsze zwraca wartość x stosowane w najnowszym store( V , x ) działania na tej samej zmiennej V .

Podobnie jak w wielu językach programowania, operacja store( V , x ) jest często zapisywana jako V ← x (lub podobna notacja) i fetch( V ) jest implikowana, gdy zmienna V jest używana w kontekście, w którym wymagana jest wartość. Tak więc, na przykład, V ← V + 1 jest powszechnie rozumiane jako skrót od store( V , fetch( V ) + 1 ).

W tej definicji zakłada się domyślnie, że przechowywanie wartości w zmiennej U nie ma wpływu na stan odrębnej zmiennej V . Aby to założenie było jasne, można dodać ograniczenie, które:

  • jeśli U i V są różnymi zmiennymi, sekwencja { store( U , x ); store( V , y ) } jest równoważne { store( V , y ); store( U , x )}.

Bardziej ogólnie, definicje ADT często zakładają, że każda operacja, która zmienia stan jednej instancji ADT nie ma wpływu na stan jakiejkolwiek innej instancji (w tym innych instancji tego samego ADT) - chyba że aksjomaty ADT sugerują, że te dwie instancje są połączone ( aliased ) w tym sensie. Na przykład, rozszerzając definicję zmiennej abstrakcyjnej o rekordy abstrakcyjne , operacja wybierająca pole ze zmiennej rekordu R musi dać zmienną V, która jest aliasem do tej części R .

Definicja abstrakcyjnej zmiennej V mogą również ograniczyć przechowywanych wartości x należących do określonego zbioru X , zwany zakres lub typ z V . Podobnie jak w językach programowania, takie ograniczenia mogą uprościć opis i analizę algorytmów oraz poprawić ich czytelność.

Zauważ, że ta definicja nie implikuje niczego o wyniku oceny fetch( V ) gdy V jest niezainicjalizowane , to znaczy przed wykonaniem jakiejkolwiek storeoperacji na V . Algorytm, który to robi, jest zwykle uważany za nieprawidłowy, ponieważ jego efekt nie jest zdefiniowany. (Istnieją jednak pewne ważne algorytmy, których skuteczność silnie zależy od założenia, że ​​jest fetchto legalne i zwraca pewną dowolną wartość z zakresu zmiennej.)

Tworzenie instancji

Niektóre algorytmy wymagają tworzenia nowych wystąpień niektórych ADT (takich jak nowe zmienne lub nowe stosy). Aby opisać takie algorytmy, zwykle włącza się do definicji ADT createoperację (), która daje instancję ADT, zwykle z aksjomatami równoważnymi

  • wynik create() różni się od dowolnego wystąpienia używanego przez algorytm.

Ten aksjomat może zostać wzmocniony, aby wykluczyć również częściowe aliasowanie z innymi instancjami. Z drugiej strony, ten aksjomat nadal pozwala implementacjom create() na uzyskanie wcześniej utworzonej instancji, która stała się niedostępna dla programu.

Przykład: abstrakcyjny stos (konieczny)

Jako inny przykład, imperatywna definicja stosu abstrakcyjnego może określać, że stan stosu S może być modyfikowany tylko przez operacje

  • push( S , x ), gdzie x jest pewną wartością nieokreślonego charakteru;
  • pop( S ), co w rezultacie daje wartość,

z ograniczeniem, że

  • Dla dowolnej wartości x i dowolnej zmiennej abstrakcyjnej V sekwencja operacji { push( S , x ); V ← pop( S ) } jest równoważne V ← x .

Ponieważ przypisanie V ← x , z definicji nie może zmienić stanu S , warunek ten implikuje, że V ← pop( S ) przywraca S do stanu, który miał przed push( S , x ). Z tego warunku oraz z własności zmiennych abstrakcyjnych wynika na przykład, że sekwencja

{ push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S ) }

gdzie x , y i z są dowolnymi wartościami, a U , V , W są parami odrębnymi zmiennymi, jest równoważne

{ U ← y ; V ← z ; W ← x }

Tutaj zakłada się niejawnie, że operacje na wystąpieniu stosu nie modyfikują stanu żadnego innego wystąpienia ADT, w tym innych stosów; to jest,

  • Dla dowolnych wartości x , y i dowolnych odrębnych stosów S i T sekwencja { push( S , x ); push( T , y ) } jest równoważne { push( T , y ); push( S , x )}.

Streszczenie definicja stos zwykle zawiera również logiczna -valued funkcji empty( S ) i create(), działanie, które zwraca wystąpienia stos z axioms równoważnych

  • create() ≠ S dla dowolnego poprzedniego stosu S (nowo utworzony stos różni się od wszystkich poprzednich stosów);
  • empty( create()) (nowo utworzony stos jest pusty);
  • not empty( push( S , x )) (włożenie czegoś do stosu powoduje, że nie jest on pusty).

Styl jednoinstancyjny

Czasami ADT jest definiowane tak, jakby tylko jedno jego wystąpienie istniało podczas wykonywania algorytmu, a wszystkie operacje zostały zastosowane do tego wystąpienia, co nie jest wyraźnie zapisane. Na przykład, streszczenie stos powyżej mogły zostać zdefiniowane z operacji push( x ) i pop(), które działają na tym tylko istniejącego komina. Definicje ADT w tym stylu można łatwo przepisać, aby dopuścić wiele współistniejących wystąpień ADT, dodając jawny parametr wystąpienia (jak S w poprzednim przykładzie) do każdej operacji, która używa lub modyfikuje niejawne wystąpienie.

Z drugiej strony, niektórych ADT nie można sensownie zdefiniować bez założenia wielu wystąpień. Dzieje się tak, gdy pojedyncza operacja przyjmuje dwa różne wystąpienia ADT jako parametry. Rozważmy na przykład rozszerzenie definicji stosu abstrakcyjnego o operację compare( S , T ), która sprawdza, czy stosy S i T zawierają te same elementy w tej samej kolejności.

Definicja stylu funkcjonalnego

Innym sposobem zdefiniowania ADT, bliższym duchowi programowania funkcjonalnego , jest rozważenie każdego stanu struktury jako oddzielnej jednostki. W tym widoku każda operacja modyfikująca ADT jest modelowana jako funkcja matematyczna, która przyjmuje stary stan jako argument i zwraca nowy stan jako część wyniku. W przeciwieństwie do operacji imperatywnych funkcje te nie mają skutków ubocznych . Dlatego kolejność ich oceny jest nieistotna, a ta sama operacja zastosowana do tych samych argumentów (w tym tych samych stanów wejściowych) zawsze zwróci te same wyniki (i stany wyjściowe).

W szczególności w ujęciu funkcjonalnym nie ma możliwości (ani potrzeby) zdefiniowania „zmiennej abstrakcyjnej” z semantyką zmiennych imperatywnych (czyli z fetchi storeoperacjami). Zamiast przechowywać wartości w zmiennych, przekazuje się je jako argumenty do funkcji.

Przykład: stos abstrakcyjny (funkcjonalny)

Na przykład kompletna definicja stosu abstrakcyjnego w stylu funkcjonalnym może wykorzystywać trzy operacje:

  • push: przyjmuje stan stosu i dowolną wartość, zwraca stan stosu;
  • top: przyjmuje stan stosu, zwraca wartość;
  • pop: przyjmuje stan stosu, zwraca stan stosu.

W definicji stylu funkcjonalnego nie ma potrzeby wykonywania createoperacji. W rzeczywistości nie istnieje pojęcie „instancji stosu”. Stany stosu można traktować jako potencjalne stany struktury pojedynczego stosu, a stany z dwoma stosami, które zawierają te same wartości w tej samej kolejności, są uważane za stany identyczne. Ten widok faktycznie odzwierciedla zachowanie niektórych konkretnych implementacji, takich jak połączone listy z hash cons .

Zamiast create() definicja abstrakcyjnego stosu w stylu funkcjonalnym może zakładać istnienie specjalnego stanu stosu, pustego stosu , oznaczonego specjalnym symbolem, takim jak Λ lub „()”; lub zdefiniuj bottomoperację (), która nie przyjmuje argumentów i zwraca ten specjalny stan stosu. Zauważ, że aksjomaty implikują, że

  • push(Λ, x ) ≠ Λ.

W definicji stosu w stylu funkcjonalnym nie jest potrzebny emptypredykat: zamiast tego można sprawdzić, czy stos jest pusty, sprawdzając, czy jest równy Λ.

Zauważ, że te aksjomaty nie definiują efektu top( s ) lub pop( s ), chyba że s jest stanem stosu zwracanym przez a push. Ponieważ pushpozostawia stos niepusty, te dwie operacje są niezdefiniowane (stąd nieprawidłowe), gdy s = Λ. Z drugiej strony aksjomaty (i brak efektów ubocznych) implikują, że push( s , x ) = push( t , y ) wtedy i tylko wtedy, gdy x = y i s = t .

Podobnie jak w niektórych innych działach matematyki, zwyczajowo przyjmuje się również, że stanami stosu są tylko te, których istnienie można udowodnić na podstawie aksjomatów w skończonej liczbie kroków. W powyższym przykładzie abstrakcyjnego stosu ta reguła oznacza, że ​​każdy stos jest skończoną sekwencją wartości, która staje się pustym stosem (Λ) po skończonej liczbie pops. Powyższe aksjomaty same w sobie nie wykluczają istnienia stosów nieskończonych (które można popedytować w nieskończoność, za każdym razem dając inny stan) lub stosów kołowych (które powracają do tego samego stanu po skończonej liczbie pops). W szczególności nie wykluczają stanów s takich, że pop( s ) = s lub push( s , x ) = s dla niektórych x . Ponieważ jednak nie można uzyskać takich stanów stosu za pomocą danych operacji, zakłada się, że "nie istnieją".

Czy uwzględnić złożoność

Oprócz zachowania w zakresie aksjomatów, możliwe jest również uwzględnienie w definicji operacji ADT ich złożoności algorytmicznej . Alexander Stepanov , projektant C++ Standard Template Library , uwzględnił gwarancje złożoności w specyfikacji STL, argumentując:

Powodem wprowadzenia pojęcia abstrakcyjnych typów danych było umożliwienie wymiennych modułów oprogramowania. Nie możesz mieć wymiennych modułów, chyba że te moduły mają podobne zachowanie złożoności. Jeśli zastąpię jeden moduł innym modułem o tym samym zachowaniu funkcjonalnym, ale z różnymi kompromisami złożoności, użytkownik tego kodu będzie niemile zaskoczony. Mógłbym mu powiedzieć wszystko, co mi się podoba o abstrakcji danych, a on nadal nie będzie chciał używać kodu. Asercje złożoności muszą być częścią interfejsu.

—  Aleksander Stiepanow

Zalety abstrakcyjnego wpisywania danych

Kapsułkowanie

Abstrakcja daje obietnicę, że każda implementacja ADT ma pewne właściwości i możliwości; Wiedza o tym jest wszystkim, co jest wymagane do korzystania z obiektu ADT.

Lokalizacja zmiany

Kod, który używa obiektu ADT nie będzie musiał być edytowany, jeśli implementacja ADT zostanie zmieniona. Ponieważ wszelkie zmiany w implementacji muszą nadal być zgodne z interfejsem, a kod używający obiektu ADT może odnosić się tylko do właściwości i zdolności określonych w interfejsie, zmiany mogą być wprowadzane w implementacji bez konieczności wprowadzania jakichkolwiek zmian w kodzie, w którym używane jest ADT .

Elastyczność

Różne implementacje ADT, mające wszystkie te same właściwości i możliwości, są równoważne i mogą być używane nieco zamiennie w kodzie, który używa ADT. Daje to dużą elastyczność podczas używania obiektów ADT w różnych sytuacjach. Na przykład, różne implementacje ADT mogą być bardziej wydajne w różnych sytuacjach; możliwe jest użycie każdego w sytuacji, w której są one preferowane, zwiększając w ten sposób ogólną wydajność.

Typowe operacje

Niektóre operacje, które są często określane dla ADT (prawdopodobnie pod innymi nazwami) są

  • compare( s , t ), które sprawdza, czy stany dwóch instancji są w pewnym sensie równoważne;
  • hash( s ), która oblicza pewną standardową funkcję mieszającą ze stanu instancji;
  • print( s ) lub show( s ), które tworzą czytelną dla człowieka reprezentację stanu instancji.

W definicjach ADT w stylu imperatywnym często można znaleźć również:

  • create(), która daje nowe wystąpienie ADT;
  • initialize( E ), który przygotowuje się w nowo utworzonej instancji s do dalszych operacji lub resetuje ją w pewnym „stanie wyjściowym”;
  • copy( s , t ), co stawia instancje s w stanie równoważnym do t ;
  • clone( t ), który wykonuje s ← create( ), copy( s , t ) i zwraca s ;
  • free( s ) lub destroy( s ) , które odzyskują pamięć i inne zasoby używane przez s .

freeOperacja nie jest zazwyczaj istotne lub znaczące, ponieważ teoretyczne ADTS są podmioty, które nie „Wykorzystanie pamięci”. Jednak może to być konieczne, gdy trzeba przeanalizować pamięć używaną przez algorytm korzystający z ADT. W takim przypadku potrzebne są dodatkowe aksjomaty, które określają, ile pamięci używa każda instancja ADT, jako funkcja jej stanu, i jaka jej część jest zwracana do puli przez free.

Przykłady

Niektóre popularne ADT, które okazały się przydatne w wielu różnych zastosowaniach, to:

Każde z tych ADT można zdefiniować na wiele sposobów i wariantów, niekoniecznie równoważnych. Na przykład, abstrakcyjny stos może, ale nie musi, mieć countoperację, która mówi, ile elementów zostało wypchniętych, a jeszcze nie zdjętych. Ten wybór ma znaczenie nie tylko dla jego klientów, ale także dla wdrożenia.

Abstrakcyjny graficzny typ danych

W 1979 roku zaproponowano rozszerzenie ADT o grafikę komputerową: abstrakcyjny graficzny typ danych (AGDT). Został wprowadzony przez Nadię Magnenat Thalmann i Daniela Thalmanna . AGDT zapewniają zalety ADT wraz z możliwościami budowania obiektów graficznych w ustrukturyzowany sposób.

Realizacja

Dalsze informacje: nieprzezroczysty typ danych

Implementacja ADT oznacza zapewnienie jednej procedury lub funkcji dla każdej abstrakcyjnej operacji. Instancje ADT są reprezentowane przez pewną konkretną strukturę danych, która jest manipulowana przez te procedury, zgodnie ze specyfikacją ADT.

Zwykle istnieje wiele sposobów na zaimplementowanie tego samego ADT przy użyciu kilku różnych konkretnych struktur danych. W ten sposób, na przykład, abstrakcyjny stos może być zaimplementowany przez połączoną listę lub przez tablicę .

Aby zapobiec uzależnieniu klientów od implementacji, ADT jest często pakowane jako nieprzezroczysty typ danych w jednym lub kilku modułach , których interfejs zawiera tylko sygnaturę (liczbę i typy parametrów oraz wyniki) operacji. Implementacja modułu — a mianowicie treść procedur i użyta konkretna struktura danych — może być wtedy ukryta przed większością klientów modułu. Umożliwia to zmianę wdrożenia bez wpływu na klientów. Jeśli implementacja jest ujawniona, jest nazywana przezroczystym typem danych.

Podczas implementacji ADT każde wystąpienie (w definicjach w stylu imperatywnym) lub każdy stan (w definicjach w stylu funkcjonalnym) jest zwykle reprezentowane przez pewnego rodzaju uchwyt .

Nowoczesne języki zorientowane obiektowo, takie jak C++ i Java , obsługują formę abstrakcyjnych typów danych. Kiedy klasa jest używana jako typ, jest to typ abstrakcyjny, który odwołuje się do ukrytej reprezentacji. W tym modelu ADT jest zazwyczaj implementowane jako klasa , a każde wystąpienie ADT jest zwykle obiektem tej klasy. Interfejs modułu zazwyczaj deklaruje konstruktory jako zwykłe procedury, a większość innych operacji ADT jako metody tej klasy. Jednak takie podejście nie jest łatwe do zahermetyzowania wielu wariantów reprezentacyjnych znalezionych w ADT. Może również podważyć rozszerzalność programów zorientowanych obiektowo. W czystym programie zorientowanym obiektowo, który używa interfejsów jako typów, typy odnoszą się do zachowań, a nie reprezentacji.

Przykład: implementacja abstrakcyjnego stosu

Jako przykład, oto implementacja powyższego abstrakcyjnego stosu w języku programowania C .

Interfejs w stylu imperatywnym

Interfejs w stylu imperatywnym może wyglądać tak: 

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

Ten interfejs można wykorzystać w następujący sposób: 

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

Ten interfejs można zaimplementować na wiele sposobów. Implementacja może być arbitralnie nieefektywna, ponieważ formalna definicja ADT powyżej nie określa, ile miejsca może wykorzystać stos, ani jak długo powinna trwać każda operacja. Nie określa również, czy stan stosu s nadal istnieje po wywołaniu x ← pop( s ).

W praktyce formalna definicja powinna określać, że przestrzeń jest proporcjonalna do liczby elementów wypchniętych, a jeszcze nie wypchniętych; i że każda z powyższych operacji musi zakończyć się w stałym czasie, niezależnie od tej liczby. Aby zachować zgodność z tymi dodatkowymi specyfikacjami, implementacja może używać połączonej listy lub tablicy (z dynamiczną zmianą rozmiaru) wraz z dwiema liczbami całkowitymi (liczba elementów i rozmiar tablicy).

Interfejs w stylu funkcjonalnym

Definicje ADT w stylu funkcjonalnym są bardziej odpowiednie dla funkcjonalnych języków programowania i na odwrót. Można jednak zapewnić interfejs w stylu funkcjonalnym nawet w języku imperatywnym, takim jak C. Na przykład: 

typedef struct stack_Rep stack_Rep;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

Biblioteki ADT

Wiele nowoczesnych języków programowania, takich jak C++ i Java, jest dostarczanych ze standardowymi bibliotekami, które implementują kilka popularnych ADT, takich jak te wymienione powyżej.

Wbudowane abstrakcyjne typy danych

Specyfikacja niektórych języków programowania jest celowo niejasna, jeśli chodzi o reprezentację pewnych wbudowanych typów danych, definiując tylko operacje, które można na nich wykonać. Dlatego te typy mogą być postrzegane jako „wbudowane narzędzia ADT”. Przykładami są tablice w wielu językach skryptowych, takich jak Awk , Lua i Perl , które można uznać za implementację listy abstrakcyjnej.

Zobacz też

Uwagi

Cytaty

Bibliografia

Dalsza lektura

Zewnętrzne linki