Stiva ("stack") este o structura de date omogena, unidimensionala,
care are particularitatea ca toate insertiile si suprimarile de elemente se
executa la un singur capat care se numeste varful stivei. Implementarea
in limbajele de nivel inalt (Pascal, C) se face cu ajutorul tipului tablou sau
structurilor de date dinamice (pointerilor). La nivel hardware toate
calculatoarele ofera o implementare fizica a uneia sau mai multor stive. In
limbaje de nivel inalt stiva nu apare ca si tip predefinit, ea putand fi
imaginata ca un tip de date abstract, implementat de utilizator, care, de
regula, are asociate urmatoarele cinci operatii:
Initializare
|
se face stiva vida
|
VarfStiva
|
furnizeaza elementul din varful stivei
|
Pop
|
suprima elementul din varful stivei (implementata ca si functie
poate returna elementul)
|
Push (X)
|
insereaza elementul X in varful stivei;
|
Stiva Vida
|
functie booleana care verifica daca stiva este vida (necesara
inaintea lui pop)
|
Coada ("queue") este tot o structura de date omogena,
unidimensionala, in care elementele sunt inserate la un capat (spate) si sunt
suprimate la celalalt (fata). Operatiile asociate cozilor sunt analoage celor
asupra stivelor, cu diferenta ca insertiile se fac la spatele cozii si ca
operatiile difera ca terminologie:
Initializare
|
face coada vida
|
Primul_element
|
returneaza primul element
|
Adauga (X)
|
insereaza elementul X in spatele cozii
|
Scoate
|
suprima primul element al cozii si, daca este implementata ca si
functie, returneaza si valoarea acestui element
|
Coada Vida
|
functie booleana care verifica daca este vida coada
|
Aceste structuri de date sunt utile in realizarea compilatoarelor, a
sistemelor de operare si a altor programe complexe.
Implementarea se va face cu ajutorul tipului tablou, in care baza stivei
va fi sfarsitul tabloului (indexul sau cel mai mare), stiva crescand in
sensul descresterii indexului in tablou. Un cursor (indice) numit VarfStiva
indica pozitia curenta a primului element al stivei.
Structura de date abstracta va fi urmatoarea:
type
stiva = record
VarfStiva : integer;
elemente : array [1..dimMaxStiva] of TipElement
end;
|
TipElement fiind un tip declarat anterior.
Avem stiva declarata ca:
Cele cinci operatii asociate stivelor sunt:
procedure initializare;
begin
s.VarfStiva := dimMaxStiva + 1;
end;
function StivaVida : boolean;
begin
StivaVida := s.VarfStiva > dimMaxStiva;
end;
function VarfStiva : TipElement;
begin
if StivaVida then writeln ('Eroare - stiva vida');
else VarfStiva:= s.elemente[s.VarfStiva];
end;
function pop : TipElement;
begin
if StivaVida then writeln ('Eroare - stiva vida')
else
begin
pop := s.elemente[s.VarfStiva];
s.VarfStiva := s.VarfStiva + 1
end
end;
procedure push (X : TipElement);
begin
if s.VarfStiva = 1 then write ('Eroare - stiva este plina')
else
begin
s.VarfStiva := s.VarfStiva - 1;
s.elemente[s.VarfStiva] := X
end
end;
|
Pentru coada se poate utiliza o structura de tablou circular in care prima
pozitie urmeaza ultimei. Primul element si ultimul element al cozii vor fi
indicate de doi indici, primul si ultimul, care vor putea fi
testati pentru sesizarea cozii pline sau vide.
In continuare se prezinta implementarea celor cinci operatii care
manipuleaza o structura de tip coada definita astfel:
type
coada = record
elemente : array [1..dimMacCoada] of TipElement;
primul, ultimul : integer
end;
|
iar coada va fi:
Mai este necesara si o functie care furnizeaza pozitia urmatoare cele
curente in coada:
function Avans (var i : integer) : integer;
begin
Avans := (i mod dimMaxCoada) + 1;
end;
procedure Initializare;
begin
c.primul := 1;
c. ultimul := dimMaxCoada;
end;
function CoadaVida : boolean;
begin
CoadaVida := Avans(c.ultimul) = c.primul;
end;
function Primul_Element : TipElement;
begin
if CoadaVida then writeln ('Eroare - coada este vida')
else Primul_Element := c.elemente[c.primul]
end;
procedure Adauga (X : TipElement);
begin
if Avans (Avans (c.ultimul)) = c.primul then
writeln ('Eroare - coada este plina')
else
begin
c.ultimul := Avans (c.ultimul);
c.elementepc.ultimul] := X
end
end;
function Scoate : TipElement;
begin
if CoadaVida then writeln ('Eroare - coada este vida')
else
begin
Scoate := c.elemente[c.primul];
c.primul := Avans (c.primul)
end
end;
|
-
Se considera urmatoarea structura de date:
UnText : array [1..10] of string;
|
In acest tablou se citeste un text de la tastatura format din cuvinte
scrise cu litere mici, alcatuit din una la maxim 10 linii care se termina cu
'.'. Cu ajutorul unei stive, sa se indice care dintre cuvine sunt
palindroame (cuvinte care parcurse de la sfarsit catre inceput dau cuvantul
initial, ex. - aerisirea, rotor, capac etc.).
-
Sa se scrie un program care administreaza o coada de masini la o statie
de benzina. Programul va genera din 5 in 5 secunde cate o masina care intra
la coada si, cand utilizatorul apasa o tasta , o masina pleaca (din fata).
Sa se afiseze mereu (dupa fiecare miscare) numarul de masini din coada si,
daca sunt mai mult de 20 de masini, altele sa nu fie admise pana cand nu se
elibereaza loc pentru acestea. Se vor folosi procedurile predefinite:
GetTime (var h, m, s, c)
|
da timpul sistem
|
KeyPressed
|
functie booleana care este true daca a fost apasata o tasta.
|