Antoni M. Zajączkowski: : Algorytmy i podstawy programowania stosy, kolejki, listy 8 maja 2009 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 spo- sób organizowany jest dostęp do jej elementów, nazywamy ją stosem (stack), kolejką (queue), albo listą (list). Te trzy struktury należą do klasy struktur logicznie liniowych, albo krótko struktur liniowych (logically linear structures), czyli takich, w których określony jest porządek liniowy (Beidler, 1997). 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 dostępu do elementów stosu mogą odbywać się na jednym końcu stosu. Koniec ten nazywamy wierzchołkiem, albo szczytem (top) stosu. Drugi koniec stosu nazywamy dnem (bottom) stosu. W związku z tym, stosy nazywamy czasami listami popychanymi (pushdown list) i zaliczamy do struktur typu ostatni wchodzi, pierwszy wychodzi LIFO (last in, first out). S3. Operacja usuń Pop usuwa obiekt znajdujący się na wierzchołku stosu. Następny obiekt 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 był pusty, poprzednio wstawione elementy przesuwane są o jedną pozycję w dół. Zadanie obliczeniowe. Napisać, uruchomić i przetestować program w języku Ada implementujący stos jako tablicę jednowymiarową oraz realizujący operacje na tym stosie. W tym celu można posłużyć się deklaracjami: type Stack_Array is array (Positive range 1..Max_Length) of Element; type Stack_Record is record Top : Natural; List : Stack_Array; end record; Należy w tym programie zapewnić wykonywanie operacji wstawiania i usuwania elementów ze stosu - procedure 1 Push i procedure Pop oraz obliczania elementu na wierzchołku stosu - function Top_Element i Top sprawdzania czy stos jest pusty - function Stack_Empty, albo czy stos jest pełny function Stack_Full. Poza tym, program musi uniemożliwiać Max_Length wstawianie elemenu na pełny stos i usuwanie elementu z Rysunek. Tablicowa implementacja pustego stosu i zawierać procedurę wypisywania stosu elementów stosu procedure Write_Stack. Wskazówka. Dogodnie jest reprezentować stos jak na rysunku (Aho, Hopcroft, Ullman, 2003).