Antoni M. Zajączkowski: Algorytmy i podstawy programowania – stosy, kolejki, listy
9 maja 2011
1
1
1
1
S
S
S
S
TOSY
TOSY
TOSY
TOSY
,,,,
KOLEJKI
KOLEJKI
KOLEJKI
KOLEJKI
,,,,
LISTY
LISTY
LISTY
LISTY
Weźmy pod uwagę skończony ciąg
1
2
,
,
,
n
a
a
a
…
,
0
n ≥
, przy czym przyjmiemy, że ele-
menty
i
a
są tego samego typu. Ciąg ten możemy traktować jako pewną strukturę danych,
uporządkowaną liniowo, w której element
i
a
poprzedza element
1
i
a
+
,
1, 2,
,
1
i
n
=
−
…
.
Struktura ta może być pusta, ponieważ dopuszczamy przypadek
0
n =
.
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
stosem
stosem
stosem (
stack
), kolejką
kolejką
kolejką
kolejką (
queue
),
albo listą
listą
listą
listą (
list
). Te trzy struktury należą do klasy struktur logicznie liniowych
struktur logicznie liniowych
struktur logicznie liniowych
struktur logicznie liniowych, albo krótko
struktur
struktur
struktur
struktur liniowych
liniowych
liniowych
liniowych (
logically linear structures
), czyli takich, w których określony jest porzą-
dek liniowy (
Beidler, 1997
).
1.
1.
1.
1.
Stosy
Stosy
Stosy
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
wierzchołkiem
wierzchołkiem
wierzchołkiem, albo szczytem
szczytem
szczytem
szczytem (
top
) stosu. Drugi ko-
niec stosu nazywamy dnem
dnem
dnem
dnem (
bottom
) stosu. W związku z tym, stosy nazywamy czasami li
lili
li----
stami popy
stami popy
stami popy
stami popychanymi
chanymi
chanymi
chanymi (
pushdown list
) i zaliczamy do struktur typu „ostatni wchodzi, pierw
ostatni wchodzi, pierw
ostatni wchodzi, pierw
ostatni wchodzi, pierw----
szy wycho
szy wycho
szy wycho
szy wychodzi
dzi
dzi
dzi” – LIFO
LIFO
LIFO
LIFO (
last in, first out
).
S3. Operacja usuń
usuń
usuń
usuń –
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 wstaw
wstaw
wstaw
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ół.
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.
Zadanie obliczeniowe 1.
Zadanie obliczeniowe 1.
Zadanie obliczeniowe 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 –
funct
funct
funct
funct
ion
Stack_Full
. Poza
tym, program musi uniemożliwiać wstawianie elemenu na pełny stos i usuwanie elementu
