Stos (abstrakcyjny typ danych) - Stack (abstract data type)
W informatyce , A stos jest abstrakcyjny typ danych , który służy jako zbioru elementów, z dwóch podstawowych operacji podstawowych:
- Push , który dodaje element do kolekcji, oraz
- Pop , który usuwa ostatnio dodany element, który nie został jeszcze usunięty.
Kolejność, w jakiej elementy schodzą ze stosu, daje jej alternatywną nazwę, LIFO ( ostatnie weszło , pierwsze wyszło ). Dodatkowo operacja podglądu może dać dostęp do góry bez modyfikowania stosu. Nazwa „stos” dla tego typu konstrukcji pochodzi z analogii do zestawu fizycznych elementów ułożonych jeden na drugim. Taka struktura ułatwia zdejmowanie przedmiotu ze szczytu stosu, podczas gdy dotarcie do przedmiotu znajdującego się głębiej w stosie może wymagać wcześniejszego zdjęcia wielu innych przedmiotów.
Traktowana jako liniowa struktura danych lub bardziej abstrakcyjnie sekwencyjna kolekcja, operacje push i pop występują tylko na jednym końcu struktury, określanym jako wierzchołek stosu. Ta struktura danych umożliwia zaimplementowanie stosu jako pojedynczo połączonej listy i wskaźnika do górnego elementu. Stos może być zaimplementowany tak, aby miał ograniczoną pojemność. Jeśli stos jest pełny i nie zawiera wystarczającej ilości miejsca, aby zaakceptować jednostkę, która ma zostać wypchnięta, wówczas uważa się, że stos znajduje się w stanie przepełnienia . Operacja pop usuwa element ze szczytu stosu.
Aby zaimplementować wyszukiwanie w głąb, potrzebny jest stos .
Historia
Stosy pojawiły się w literaturze informatycznej w 1946 roku, kiedy Alan M. Turing użył terminów „zakopać” i „odkopać” jako sposób wywoływania i powracania z podprogramów. Podprogramy został już wdrożony w Konrad Zuse „s Z4 w 1945 roku.
Klaus Samelson i Friedrich L. Bauer z Uniwersytetu Technicznego w Monachium zaproponowali ideę stosu w 1955 i złożyli patent w 1957. W marcu 1988, kiedy Samelson zmarł, Bauer otrzymał nagrodę IEEE Computer Pioneer Award za wynalezienie stosu zasada. Podobne koncepcje opracował niezależnie Charles Leonard Hamblin w pierwszej połowie 1954 roku i Wilhelm Kämmerer w 1958 roku.
Stosy są często opisywane za pomocą analogii do sprężynowego stosu talerzy w stołówce. Czyste talerze są umieszczane na górze stosu, spychając te, które już tam są. Gdy płyta zostanie wyjęta ze stosu, ta pod nią wyskoczy, aby stać się nową płytą górną.
Nieistotne operacje
W wielu implementacjach stos zawiera więcej operacji niż podstawowe operacje „push” i „pop”. Przykładem nieistotnej operacji jest „szczyt stosu” lub „wgląd”, który obserwuje górny element bez usuwania go ze stosu. Można to zrobić za pomocą „pop”, a następnie „push”, aby zwrócić te same dane na stos, więc nie jest to uważane za operację podstawową. Jeśli stos jest pusty, po wykonaniu operacji „stack top” lub „pop” wystąpi stan niedopełnienia. Dodatkowo wiele implementacji zapewnia sprawdzenie, czy stos jest pusty i zwraca jego rozmiar.
Stosy oprogramowania
Realizacja
Stos można łatwo zaimplementować za pomocą tablicy lub połączonej listy . W obu przypadkach to, co identyfikuje strukturę danych jako stos, nie jest implementacją, ale interfejsem: użytkownik może tylko pop lub wepchnąć elementy do tablicy lub listy połączonej, z kilkoma innymi operacjami pomocniczymi. Poniżej zademonstrujemy obie implementacje przy użyciu pseudokodu .
Szyk
Tablicy można użyć do zaimplementowania (ograniczonego) stosu w następujący sposób. Pierwszym elementem, zwykle przy zerowym przesunięciu , jest spód, co powoduje array[0], że pierwszy element jest zepchnięty na stos, a ostatni odpada. Program musi śledzić rozmiar (długość) stosu, używając zmiennej top, która rejestruje liczbę elementów wepchniętych do tej pory, wskazując tym samym miejsce w tablicy, w którym ma zostać wstawiony następny element (zakładając zero- w oparciu o konwencję indeksową). W ten sposób sam stos może być skutecznie zaimplementowany jako trzyelementowa konstrukcja:
structure stack:
maxsize : integer
top : integer
items : array of item
procedure initialize(stk : stack, size : integer):
stk.items ← new array of size items, initially empty
stk.maxsize ← size
stk.top ← 0
Operacja push dodaje element i zwiększa górny indeks po sprawdzeniu przepełnienia:
procedure push(stk : stack, x : item):
if stk.top = stk.maxsize:
report overflow error
else:
stk.items[stk.top] ← x
stk.top ← stk.top + 1
Podobnie, pop zmniejsza górny indeks po sprawdzeniu niedomiaru i zwraca element, który był poprzednio najwyższym:
procedure pop(stk : stack):
if stk.top = 0:
report underflow error
else:
stk.top ← stk.top − 1
r ← stk.items[stk.top]
return r
Korzystając z tablicy dynamicznej , można zaimplementować stos, który może rosnąć lub zmniejszać się w miarę potrzeb. Rozmiar stosu to po prostu rozmiar tablicy dynamicznej, co jest bardzo wydajną implementacją stosu, ponieważ dodawanie elementów do lub usuwanie elementów z końca tablicy dynamicznej wymaga zamortyzowanego czasu O(1).
Połączona lista
Inną opcją implementacji stosów jest użycie listy połączonej pojedynczo . Stos jest wtedy wskaźnikiem do „nagłówka” listy, z być może licznikiem do śledzenia rozmiaru listy:
structure frame:
data : item
next : frame or nil
structure stack:
head : frame or nil
size : integer
procedure initialize(stk : stack):
stk.head ← nil
stk.size ← 0
Wypychanie i wyskakiwanie elementów odbywa się na początku listy; przepełnienie nie jest możliwe w tej implementacji (chyba że pamięć jest wyczerpana):
procedure push(stk : stack, x : item):
newhead ← new frame
newhead.data ← x
newhead.next ← stk.head
stk.head ← newhead
stk.size ← stk.size + 1
procedure pop(stk : stack):
if stk.head = nil:
report underflow error
r ← stk.head.data
stk.head ← stk.head.next
stk.size ← stk.size - 1
return r
Stosy i języki programowania
Niektóre języki, takie jak Perl , LISP , JavaScript i Python , udostępniają operacje stosu push i pop w standardowych typach list/array. Niektóre języki, zwłaszcza te z rodziny Forth (w tym PostScript ), są zaprojektowane wokół stosów zdefiniowanych w języku, które są bezpośrednio widoczne i manipulowane przez programistę.
Poniżej znajduje się przykład manipulowania stosem w Common Lisp (" > " to znak zachęty interpretera Lisp; linie nie zaczynające się od " > " są odpowiedziami interpretera na wyrażenia):
> (setf stack (list 'a 'b 'c)) ;; set the variable "stack"
(A B C)
> (pop stack) ;; get top (leftmost) element, should modify the stack
A
> stack ;; check the value of stack
(B C)
> (push 'new stack) ;; push a new top onto the stack
(NEW B C)
Kilka typów kontenerów biblioteki standardowej C++ ma operacje push_back i pop_back z semantyką LIFO; dodatkowo klasa szablonu stosu dostosowuje istniejące kontenery, aby zapewnić ograniczony interfejs API z tylko operacjami push/pop. PHP posiada klasę SplStack . Biblioteka Javy zawiera Stackklasę będącą specjalizacją Vector. Poniżej znajduje się przykładowy program w języku Java , wykorzystujący tę klasę.
import java.util.Stack;
class StackDemo {
public static void main(String[]args) {
Stack<String> stack = new Stack<String>();
stack.push("A"); // Insert "A" in the stack
stack.push("B"); // Insert "B" in the stack
stack.push("C"); // Insert "C" in the stack
stack.push("D"); // Insert "D" in the stack
System.out.println(stack.peek()); // Prints the top of the stack ("D")
stack.pop(); // removing the top ("D")
stack.pop(); // removing the next top ("C")
}
}
Stos sprzętowy
Typowym zastosowaniem stosów na poziomie architektury jest sposób przydzielania i uzyskiwania dostępu do pamięci.
Podstawowa architektura stosu
Typowy stos to obszar pamięci komputera o stałym pochodzeniu i zmiennej wielkości. Początkowo rozmiar stosu wynosi zero. Wskaźnik stosu, zazwyczaj w formie rejestrów sprzętu, wskazuje na najbardziej niedawno wskazanej lokalizacji na stosie; gdy stos ma rozmiar zero, wskaźnik stosu wskazuje początek stosu.
Dwie operacje mające zastosowanie do wszystkich stosów to:
- Push operacja, w której umieszczony jest element danych w miejscu wskazywanym przez wskaźnik stosu, a adres do wskaźnika stosu jest regulowana przez rozmiar elementu danych;
- pop lub ciągnąć operacja: pozycja danych w bieżącej lokalizacji, wskazywanej przez wskaźnik stosu jest usuwany, a wskaźnik stosu jest regulowana przez rozmiar elementu danych.
Istnieje wiele odmian podstawowej zasady działania na stosie. Każdy stos ma ustaloną lokalizację w pamięci, od której się zaczyna. Gdy elementy danych są dodawane do stosu, wskaźnik stosu jest przesuwany, aby wskazać bieżący zasięg stosu, który rozszerza się od początku.
Wskaźniki stosu mogą wskazywać na początek stosu lub na ograniczony zakres adresów powyżej lub poniżej początku (w zależności od kierunku, w którym rośnie stos); jednak wskaźnik stosu nie może przekroczyć początku stosu. Innymi słowy, jeśli początek stosu znajduje się pod adresem 1000, a stos rośnie w dół (w kierunku adresów 999, 998 itd.), wskaźnik stosu nigdy nie może być zwiększany powyżej 1000 (do 1001, 1002 itd.). Jeśli operacja pop na stosie spowoduje przesunięcie wskaźnika stosu poza początek stosu, wystąpi niedopełnienie stosu . Jeśli operacja wypychania spowoduje zwiększenie lub zmniejszenie wskaźnika stosu poza maksymalny zasięg stosu, nastąpi przepełnienie stosu .
Niektóre środowiska, które w dużym stopniu opierają się na stosach, mogą zapewniać dodatkowe operacje, na przykład:
- Duplikuj : górny element jest usuwany, a następnie ponownie pchany (dwukrotnie), tak że dodatkowa kopia poprzedniego górnego elementu znajduje się teraz na górze, a oryginał znajduje się pod nim.
- Peek : najwyższy element jest sprawdzany (lub zwracany), ale wskaźnik stosu i rozmiar stosu nie zmieniają się (co oznacza, że element pozostaje na stosie). W wielu artykułach nazywa się to również operacją górną .
- Zamiana lub wymiana : dwa najwyższe pozycje na stosie wymiany.
- Rotate (lub Roll) : n najwyższych elementów jest przesuwanych na stosie w sposób rotacyjny. Na przykład, jeśli n =3, elementy 1, 2 i 3 na stosie są przesuwane odpowiednio na pozycje 2, 3 i 1 na stosie. Możliwych jest wiele wariantów tej operacji, z których najczęstsze nazywa się obracaniem w lewo i obracaniem w prawo.
Często wizualizuje się, że stosy rosną od dołu do góry (jak stosy w świecie rzeczywistym). Mogą być również wizualizowane rosnące od lewej do prawej, tak że „najwyższy” staje się „najbardziej po prawej” lub nawet rośnie od góry do dołu. Ważną cechą jest to, że spód stosu znajduje się w stałej pozycji. Ilustracja w tej sekcji jest przykładem wizualizacji wzrostu od góry do dołu: góra (28) to „dół” stosu, ponieważ „góra” (9) stosu to miejsce, z którego elementy są wypychane lub wyrzucane.
Obrót w prawo przesunie pierwszy element na trzecią pozycję, drugi na pierwszy, a trzeci na drugi. Oto dwie równoważne wizualizacje tego procesu:
apple banana banana ===right rotate==> cucumber cucumber apple
cucumber apple banana ===left rotate==> cucumber apple banana
Stos jest zwykle reprezentowany w komputerach przez blok komórek pamięci, przy czym „dół” znajduje się w stałej lokalizacji, a wskaźnik stosu przechowuje adres bieżącej „górnej” komórki stosu. Terminologia górna i dolna jest używana niezależnie od tego, czy stos faktycznie rośnie w kierunku niższych adresów pamięci, czy w kierunku wyższych adresów pamięci.
Pchnięcie elementu na stos dostosowuje wskaźnik stosu do rozmiaru elementu (albo zmniejszając lub zwiększając, w zależności od kierunku, w którym stos powiększa się w pamięci), wskazując go na następną komórkę i kopiując nowy górny element do obszar stosu. W zależności od dokładnej implementacji, pod koniec operacji wypychania wskaźnik stosu może wskazywać na następną nieużywaną lokalizację w stosie lub może wskazywać na najwyższy element w stosie. Jeśli stos wskazuje na bieżący najwyższy element, wskaźnik stosu zostanie zaktualizowany przed włożeniem nowego elementu na stos; jeśli wskazuje na następną dostępną lokalizację w stosie, zostanie zaktualizowany po włożeniu nowego elementu na stos.
Przebijanie stosu jest po prostu odwrotnością wypychania. Najwyższy element stosu jest usuwany, a wskaźnik stosu jest aktualizowany w kolejności odwrotnej do używanej w operacji wypychania.
Stos w pamięci głównej
Wiele CISC -Typ procesora projekty, w tym x86 , Z80 i 6502 , posiada rejestr dedykowany do stosowania jako stosu wywołań wskaźnik stosu z dedykowanego połączenia, powrotu, push i pop instrukcjami niejawnie aktualizować dedykowanego rejestru, zwiększając tym samym kodem gęstość. Niektóre procesory CISC, takie jak PDP-11 i 68000 , mają również specjalne tryby adresowania do implementacji stosów , zazwyczaj z częściowo dedykowanym wskaźnikiem stosu (tak jak A7 w 68000). W przeciwieństwie do tego, większość projektów procesorów RISC nie ma dedykowanych instrukcji stosu i dlatego większość, jeśli nie wszystkie, rejestry mogą być używane jako wskaźniki stosu w razie potrzeby.
Stos w rejestrach lub dedykowanej pamięci
Architektura zmiennoprzecinkowa x87 jest przykładem zbioru rejestrów zorganizowanych w stos, w którym możliwy jest również bezpośredni dostęp do poszczególnych rejestrów (względem aktualnego szczytu). Podobnie jak w przypadku maszyn opartych na stosie ogólnie, posiadanie szczytu stosu jako niejawnego argumentu pozwala na niewielki ślad kodu maszynowego z dobrym wykorzystaniem przepustowości magistrali i pamięci podręcznej kodu , ale także zapobiega niektórym typom optymalizacji możliwych na procesorach, które pozwalają losowy dostęp do pliku rejestru dla wszystkich (dwóch lub trzech) operandów. Struktura stosu sprawia również, że implementacje superskalarne ze zmianą nazw rejestrów (dla wykonania spekulatywnego ) są nieco bardziej skomplikowane do zaimplementowania, chociaż nadal jest to wykonalne, czego przykładem są współczesne implementacje x87 .
Sun SPARC , AMD Am29000 i Intel i960 to przykłady architektur wykorzystujących okna rejestrów w stosie rejestrów jako kolejną strategię unikania używania wolnej pamięci głównej dla argumentów funkcji i wartości zwracanych.
Istnieje również wiele małych mikroprocesorów, które implementują stos bezpośrednio w sprzęcie, a niektóre mikrokontrolery mają stos o stałej głębokości, który nie jest bezpośrednio dostępny. Przykładami są mikrokontrolery PIC , Computer Cowboys MuP21 , linia Harris RTX i Novix NC4016 . Wiele mikroprocesorów opartych na stosie zostało wykorzystanych do zaimplementowania języka programowania Forth na poziomie mikrokodu . Stosy były również wykorzystywane jako podstawa wielu komputerów mainframe i minikomputerów . Takie maszyny nazywano sztaplarkami , z których najsłynniejsza to Burroughs B5000 .
Zastosowania stosów
Ocena wyrażeń i analiza składni
Kalkulatory wykorzystujące odwrotną notację polską wykorzystują do przechowywania wartości strukturę stosu. Wyrażenia mogą być reprezentowane w notacjach prefiksowych, postfiksowych lub infiksowych, a konwersja z jednej formy do drugiej może być realizowana za pomocą stosu. Wiele kompilatorów używa stosu do analizowania składni wyrażeń, bloków programu itp. przed przetłumaczeniem na kod niskiego poziomu. Większość języków programowania to języki bezkontekstowe , dzięki czemu można je analizować za pomocą maszyn opartych na stosie.
Cofanie się
Innym ważnym zastosowaniem stosów jest śledzenie wsteczne . Rozważ prosty przykład znalezienia właściwej ścieżki w labiryncie. Istnieje szereg punktów, od punktu początkowego do miejsca docelowego. Zaczynamy od jednego punktu. Aby dotrzeć do ostatecznego celu, jest kilka ścieżek. Załóżmy, że wybieramy losową ścieżkę. Po podążaniu określoną ścieżką zdajemy sobie sprawę, że wybrana przez nas ścieżka jest zła. Musimy więc znaleźć sposób, w jaki możemy wrócić na początek tej ścieżki. Można to zrobić za pomocą stosów. Za pomocą stosów zapamiętujemy punkt, w którym osiągnęliśmy. Odbywa się to poprzez wepchnięcie tego punktu do stosu. W przypadku, gdy znajdziemy się na złej ścieżce, możemy zdjąć ostatni punkt ze stosu, a tym samym wrócić do ostatniego punktu i kontynuować nasze poszukiwanie właściwej ścieżki. Nazywa się to cofaniem.
Prototypowym przykładem algorytmu z wycofywaniem jest wyszukiwanie w głąb , które znajduje wszystkie wierzchołki grafu, do których można dotrzeć z określonego wierzchołka początkowego. Inne zastosowania nawrotu obejmują przeszukiwanie przestrzeni, które reprezentują potencjalne rozwiązania problemu optymalizacji. Branch and bound to technika wykonywania takich przeszukiwań wstecznych bez wyczerpującego przeszukiwania wszystkich potencjalnych rozwiązań w takiej przestrzeni.
Kompiluj zarządzanie pamięcią czasu
Wiele języków programowania jest zorientowanych na stos , co oznacza, że definiują większość podstawowych operacji (dodawanie dwóch liczb, drukowanie znaku) jako pobieranie ich argumentów ze stosu i umieszczanie wszelkich zwracanych wartości z powrotem na stosie. Na przykład PostScript ma stos zwrotów i stos operandów, a także stos stanu grafiki i stos słownika. Wiele maszyn wirtualnych jest również zorientowanych na stos, w tym maszyna z kodem p i wirtualna maszyna Java .
Prawie wszystkie konwencje wywoływania —sposób, w jaki podprogramy otrzymują swoje parametry i zwracają wyniki—używają specjalnego stosu („ stosu wywołań ”) do przechowywania informacji o wywoływaniu i zagnieżdżaniu procedury/funkcji w celu przełączenia do kontekstu wywoływanej funkcji i przywróć funkcję dzwoniącego po zakończeniu wywołania. Funkcje podążają za protokołem środowiska wykonawczego między wywołującym a wywoływanym, aby zapisać argumenty i zwrócić wartość na stosie. Stosy są ważnym sposobem obsługi zagnieżdżonych lub rekurencyjnych wywołań funkcji. Ten typ stosu jest używany niejawnie przez kompilator do obsługi instrukcji CALL i RETURN (lub ich odpowiedników) i nie jest manipulowany bezpośrednio przez programistę.
Niektóre języki programowania używają stosu do przechowywania danych lokalnych dla procedury. Miejsce na lokalne elementy danych jest przydzielane ze stosu po wejściu do procedury i zwalniane po zakończeniu procedury. Język programowania C jest zazwyczaj implementowany w ten sposób. Używanie tego samego stosu dla wywołań danych i procedur ma ważne implikacje dla bezpieczeństwa (patrz poniżej), o których programista musi być świadomy, aby uniknąć wprowadzania poważnych błędów bezpieczeństwa do programu.
Wydajne algorytmy
Kilka algorytmów używa stosu (oddzielnego od zwykłego stosu wywołań funkcji większości języków programowania) jako podstawowej struktury danych, za pomocą której organizują swoje informacje. Obejmują one:
- Skan Grahama , algorytm dla wypukłego kadłuba dwuwymiarowego układu punktów. Wypukły kadłub podzbioru danych wejściowych jest utrzymywany w stosie, który służy do znajdowania i usuwania wklęsłości na granicy, gdy do kadłuba dodawany jest nowy punkt.
- Część algorytmu SMAWK do znajdowania minimów wierszy macierzy monotonicznej wykorzystuje stosy w sposób podobny do skanowania Grahama.
- Wszystkie najbliższe mniejsze wartości , problem znalezienia, dla każdej liczby w tablicy, najbliższej poprzedzającej liczby, która jest od niej mniejsza. Jeden algorytm dla tego problemu używa stosu do utrzymania kolekcji kandydatów dla najbliższej mniejszej wartości. Dla każdej pozycji w tablicy stos jest zdejmowany, dopóki na jego szczycie nie zostanie znaleziona mniejsza wartość, a następnie wartość w nowej pozycji jest odkładana na stos.
- Algorytm łańcuch najbliższego sąsiedztwa , sposób aglomeratów materiałem grupowanie hierarchiczne opiera się na utrzymaniu w stos klastrów, z których każdy jest najbliższym sąsiadem poprzednika w stos. Gdy ta metoda znajdzie parę klastrów, które są wzajemnymi najbliższymi sąsiadami, zostaną one zerwane i połączone.
Bezpieczeństwo
Niektóre środowiska komputerowe wykorzystują stosy w sposób, który może narażać je na naruszenia bezpieczeństwa i ataki. Programiści pracujący w takich środowiskach muszą zachować szczególną ostrożność, aby uniknąć pułapek związanych z tymi implementacjami.
Na przykład niektóre języki programowania używają wspólnego stosu do przechowywania zarówno danych lokalnych w wywoływanej procedurze, jak i informacji o łączeniu, które pozwalają procedurze powrócić do wywołującego. Oznacza to, że program przenosi dane do iz tego samego stosu, który zawiera krytyczne adresy powrotu dla wywołań procedur. Jeśli dane zostaną przeniesione do niewłaściwej lokalizacji na stosie lub zbyt duży element danych zostanie przeniesiony do lokalizacji na stosie, która nie jest wystarczająco duża, aby go pomieścić, informacje zwrotne dla wywołań procedur mogą zostać uszkodzone, powodując awarię programu.
Złośliwe strony mogą próbować przeprowadzić atak polegający na rozbijaniu stosu , korzystając z tego typu implementacji, dostarczając zbyt duże dane wejściowe do programu, który nie sprawdza długości danych wejściowych. Taki program może skopiować dane w całości do lokalizacji na stosie iw ten sposób może zmienić adresy zwrotne dla procedur, które go wywołały. Atakujący może eksperymentować, aby znaleźć określony rodzaj danych, które można dostarczyć do takiego programu, tak aby adres zwrotny bieżącej procedury został zresetowany tak, aby wskazywał obszar w samym stosie (i w danych dostarczonych przez atakującego), który z kolei zawiera instrukcje wykonywania nieautoryzowanych operacji.
Ten rodzaj ataku jest odmianą ataku przepełnienia bufora i jest niezwykle częstym źródłem naruszeń bezpieczeństwa w oprogramowaniu, głównie dlatego, że niektóre z najpopularniejszych kompilatorów używają współdzielonego stosu zarówno dla wywołań danych, jak i procedur, i nie weryfikują długości elementy danych. Często programiści nie piszą kodu, aby zweryfikować rozmiar elementów danych, a gdy zbyt duży lub zbyt mały element danych jest kopiowany na stos, może wystąpić naruszenie bezpieczeństwa.
Zobacz też
Bibliografia
-
Ten artykuł zawiera materiał z domeny publicznej z dokumentu NIST : Black, Paul E. „Bounded stack” . Słownik algorytmów i struktur danych .
Dalsza lektura
- Donalda Knutha . The Art of Computer Programming , tom 1: Podstawowe algorytmy , wydanie trzecie. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sekcja 2.2.1: Stosy, kolejki i deques, s. 238–243.