Antoni M. Zajączkowski: Algorytmy i podstawy programowania stosy, kolejki, listy 9 maja 2011 STOSY, KOLEJKI, LISTY STOSY, KOLEJKI, LISTY STOSY, KOLEJKI, LISTY STOSY, KOLEJKI, LISTY Wezmy pod uwagę skończony ciąg a1,a2,& ,an , n e" 0, przy czym przyjmiemy, że ele- menty ai są tego samego typu. Ciąg ten możemy traktować jako pewną strukturę danych, uporządkowaną liniowo, w której element ai poprzedza element ai+1, i = 1,2,& ,n -1. Struktura ta może być pusta, ponieważ dopuszczamy przypadek n = 0 . W zależności od tego w jaki sposób organizujemy obsługę tej struktury, czyli w jaki sposób organizowany jest dostęp do jej elementów, nazywamy ją stosem (stack), kolejką (queue), stosem kolejką stosem kolejką stosem kolejką albo listą (list). Te trzy struktury należą do klasy struktur logicznie liniowych, albo krótko listą struktur logicznie liniowych listą struktur logicznie liniowych listą struktur logicznie liniowych struktur liniowych (logically linear structures), czyli takich, w których określony jest porzą- struktur liniowych struktur liniowych struktur liniowych dek liniowy (Beidler, 1997). 1. Stosy 1. Stosy 1. Stosy 1. Stosy Stos jest ciągiem elementów tego samego typu o następujących własnościach: S1. Stos jest pusty, gdy nie zawiera elementów. S2. Wszystkie operacje zmieniające zawartość stosu mogą odbywać się tylko na jednym końcu stosu. Koniec ten nazywamy wierzchołkiem, albo szczytem (top) stosu. Drugi ko- wierzchołkiem szczytem wierzchołkiem szczytem wierzchołkiem szczytem niec stosu nazywamy dnem (bottom) stosu. W związku z tym, stosy nazywamy czasami li- dnem li- dnem li- dnem li- stami popychanymi ostatni wchodzi, pierw- stami popychanymi ostatni wchodzi, pierw- stami popychanymi ostatni wchodzi, pierw- stami popychanymi (pushdown list) i zaliczamy do struktur typu ostatni wchodzi, pierw- szy wychodzi LIFO (last in, first out). szy wychodzi LIFO szy wychodzi LIFO szy wychodzi LIFO S3. Operacja usuń Pop usuwa obiekt znajdujący się na wierzchołku stosu. Po usuń usuń usuń wykonaniu tej operacji następny element znajdzie się na wierzchołku stosu. Jeżeli przed wykonaniem tej operacji stos miał tylko jeden element, to po jej wykonaniu staje się stosem pustym. Operacja nie może być wykonana w przypadku pustego stosu. S4. Operacja wstaw Push wstawia nowy obiekt na wierzchołek stosu. Jeżeli stos nie wstaw wstaw wstaw był pusty, poprzednio wstawione elementy przesuwane są o jedną pozycję w dół. Tablicowa implementacja stosu Tablicowa implementacja stosu Tablicowa implementacja stosu Tablicowa implementacja stosu Stos można implementować przy wykorzystaniu pewnej tablicy jednowymiarowej. Ponieważ tablica musi być skończona, wstawianie elementów na stos może doprowadzić do sytuacji, gdy cała tablica jest wypełniona i nie można już wstawić nowego elementu. Przy tablicowej implementacji stosu można zastosować deklaracje: Max_Size : constant Positive := 8; -- Niewielki stos do testowania subtype Element is Positive; -- Elementy wstawiane na stos type Stack_Array is array (Positive range 1..Max_Size) of Element; type Stack_Record is record Top : Natural; List : Stack_Array; end record; Zadanie obliczeniowe 1. Napisać, uruchomić i przetestować program w języku Ada imple- Zadanie obliczeniowe 1. Zadanie obliczeniowe 1. Zadanie obliczeniowe 1. mentujący stos jako tablicę jednowymiarową oraz realizujący operacje na tym stosie. Należy w tym programie zapewnić wykonywanie operacji wstawiania i usuwania elementów ze stosu - procedure Push i procedure Pop oraz obliczania elementu na wierzchołku stosu - function Top_Element i sprawdzania czy stos jest pusty - function Stack_Empty, albo czy stos jest pełny function Stack_Full. Poza funct funct funct tym, program musi uniemożliwiać wstawianie elemenu na pełny stos i usuwanie elementu 1 1 1 1 Antoni M. Zajączkowski: Algorytmy i podstawy programowania stosy, kolejki, listy 9 maja 2011 z pustego stosu i zawierać procedury wypisywania elementów stosu procedure Write_Stack i tworzenia stosu pustego procedure Make_Null_Stack. Wskazówka. Dogodnie jest reprezentować stos jak na rysunku 1 (Aho, Hopcroft, Ullman, Wskazówka Wskazówka Wskazówka 2003). 1 Top Max_Length Rysunek 1. Tablicowa implementacja stosu Dynamiczna implementacja stosu Dynamiczna implementacja stosu Dynamiczna implementacja stosu Dynamiczna implementacja stosu Stos można implementować jako dynamiczną strukturę danych podobną do listy jednokierunkowej. W przypadku stosu implementowanego w ten sposób elementy wstawiane i zdejmowane ze stosu są typu rekordowego. Każdy z takich rekordów zawiera składową, która jest wskaznikiem do elementu poprzednio wstawionego na stos. Poniżej podano możliwą deklarację rekordu, który jest elementem stosu type Stack_Element; type Stack_Ptr is access Stack_Element; type Stack_Element is record Data : Positive; Next : Stack_Ptr; end record; Zadanie obliczeniowe 2. Zadanie obliczeniowe 2. Zadanie obliczeniowe 2. Napisać, uruchomić i przetestować program w języku Ada imple- Zadanie obliczeniowe 2. mentujący stos jako dynamiczną strukturę danych oraz realizujący operacje na tym stosie takie same jak w poprzednim zadaniu, z wyłączeniem funkcji Stack_Full. Wskazówka. Program Lista_Liniowa. Wskazówka Wskazówka Wskazówka 2 2 2 2