A. Consideratii teoretice

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.


B. Exemple

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:

s : stiva;

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:

c : coada;

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;

C. Teme

  1. 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.).

  2. 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.