Antoni M. Zajączkowski: Algorytmy i podstawy programowania – stosy, kolejki, listy 28 marca 2012

STO

T SY, KOLEJ

E KI, LISTY

T

Weźmy pod uwagę skończony ciąg a , a ,

, a , n ≥ 0 , przy czym przyjmiemy, że ele-1

2

n

…

menty a są tego samego typu. Ciąg ten możemy traktować jako pewną strukturę danych, i

uporządkowaną liniowo, w której element a poprzedza element a

, i = 1,2,

, n − 1 .

i

i

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ą stose s m ( stack), kole

l j

e ką

k ( queue),

albo list

s ą ( list). Te trzy struktury należą do klasy struktur logiczni n e

i liln

i i

n o

i w

o y

w ch, albo krótko

st

s rukt

k ur

u liniowy

w ch ( logically linear structures), czyli takich, w których określony jest porzą-

dek liniowy (Beidler, 1997).

1.

1 Stosy

s

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 szc z zy

z tem ( top) stosu. Drugi ko-

niec stosu nazywamy dnem ( bottom) stosu. W związku z tym, stosy nazywamy czasami lil-st

s ami

m po

p py

p chanymi

m ( pushdown list) i zaliczamy do struktur typu „ost s atni wc

w hodzi

z , pi

p er

e w-

szy

z wy

w chodzi

z ” – LI

L F

I O ( last in, first out).

S3. Operacja usu

s ń

u – Pop usuwa obiekt znajdujący się na wierzchołku stosu. Po 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 wst

s aw – Push wstawia nowy obiekt na wierzchołek stosu. Jeżeli stos nie był pusty, poprzednio wstawione elementy przesuwane są o jedną pozycję w dół.

Tablicowa

w imp

m l

p eme

m n

e t

n acja st

s osu

s

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;

Za

Z dani

n e oblicze

z n

e i

n owe

w 1. Napisać, uruchomić i przetestować program w języku Ada imple-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 – func n tion Stack_Full. Poza

tym, program musi uniemożliwiać wstawianie elemenu na pełny stos i usuwanie elementu 1

Antoni M. Zajączkowski: Algorytmy i podstawy programowania – stosy, kolejki, listy 28 marca 2012

z pustego stosu i zawierać procedury wypisywania elementów stosu – procedure Write_Stack i tworzenia stosu pustego – procedure Make_Null_Stack.

Wsk

s a

k zó

z wk

w a

k . Dogodnie jest reprezentować stos jak na rysunku 1 (Aho, Hopcroft, Ullman, 2003).

1

Top

Max_Length

Rysunek 1. Tablicowa implementacja stosu

Dyna

n mi

m czn

z a

n imp

m l

p eme

m n

e t

n acja st

s osu

s

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 wskaźnikiem 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;

Za

Z dani

n e oblicze

z n

e i

n owe

w 2. Napisać, uruchomić i przetestować program w języku Ada imple-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.

Wsk

s a

k zó

z wk

w a

k . Program Lista_Liniowa.

2