Antoni M. Zaj czkowski: : Algorytmy i podstawy programowania – stosy, kolejki, listy

8 maja 2009

1

Max_Length

Top

Rysunek. Tablicowa implementacja

stosu

S

TOSY

,

KOLEJKI

,

LISTY

We my pod uwag sko czony ci g

,

, przy czym przyjmiemy, e ele-

menty s tego samego typu. Ci g ten mo emy traktowa jako pewn struktur danych,
uporz dkowan liniowo, w której element

poprzedza element

,

.

Struktura ta mo e by pusta, poniewa dopuszczamy przypadek

.

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
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 tym, program musi uniemo liwia

wstawianie elemenu na pełny stos i usuwanie elementu z

pustego stosu i zawiera procedur wypisywania

elementów stosu – procedure Write_Stack.

Wskazówka. Dogodnie jest reprezentowa stos jak na rysunku (

Aho, Hopcroft, Ullman,

2003

).