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

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

9 maja 2011

2

2

2

2

1

Max_Length

Top

Rysunek 1. Tablicowa implementacja stosu

z pustego stosu i zawierać procedury wypisywania elementów stosu –

procedure

Write_Stack

i tworzenia stosu pustego –

procedure

Make_Null_Stack

.

Wskazówka

Wskazówka

Wskazówka

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

Aho, Hopcroft, Ullman,

2003

).

D

D

D

Dynamiczna

ynamiczna

ynamiczna

ynamiczna iiiim

m

m

mplementacja stosu

plementacja stosu

plementacja stosu

plementacja 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 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

;

Zadanie obliczeniowe

Zadanie obliczeniowe

Zadanie obliczeniowe

Zadanie obliczeniowe 2

2

2

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

.

Wskazówka

Wskazówka

Wskazówka

Wskazówka. Program

Lista_Liniowa

.