COADA.

Coada (queue) este o structură de date abstractă în care operația de adăugare se realizează la un capăt, iar cea de eliminare se realizează la celălalt capăt.

În timpul operațiilor cu coada avem acces la un singur element, cel aflat la începutul cozii – elementul care urmează să se elimine.

Operații cu coada

Cu o coadă se pot face următoarele operații:

• inițializarea cozii – crearea unei cozi vide;
• verificarea faptului că o coadă este sau nu vidă;
• adăugarea unui nou element în coadă.
  Operația se numește push;
• eliminarea unui element din coadă.
  Operația se numește pop;
• identificarea valorii elementului de la începutul cozii – accesul la acel element.
  Operația se numește front.

Operațiile cu coada sunt similare cu modul în care funcționează coada la casa de bilete a unui cinematograf. Spectatorii vin și se așează în ordine la coadă, ordinea în care cumpără biletele este aceea în care au sosit.

Deoarece operațiile de eliminare se fac în aceeași ordine ca cele de adăugare, coada este o structură de date de tip FIFO – First In First Out.

Modalități de implementare a cozii

• implementare statică, prin intermediul tablourilor;
• implementare dinamică, prin intermediul listelor alocate dinamic(folosind pointeri);
• folosirea containerului queue din STL.

Implementarea statică a cozii

Vom folosi un tablou unidimensional alocat static Q și două variabile simple prin care identificăm începutul (st) și sfârșitul cozii (dr). Numele variabilelor provine de la stânga și dreapta, deoarece adăugarea unui element în coadă se face adăugând un element în tabloul suport Q, iar eliminare se face mărind variabila st – ignorând elementele din față, fără a le șterge efectiv.

În continuare considerăm o coadă cu elemente întregi.

Declarații

const int DIM = 1000;

int Q[DIM], st, dr;

Inițializarea cozii – crearea unei cozi vide

st = 0 , dr = 0;

Verificarea faptului că este vidă coada

st >= dr // coadă vidă

st < dr // coadă nevidă

Adăugarea unui element – PUSH

Q[dr++] = VALOARE ;

Eliminarea unui element – POP

st++;

Identificarea valorii de la începutul cozii – FRONT

Q[st]

STIVA.

Stiva (stack) este o structură de date liniară abstractă, pentru care sunt definite operațiile de adăugare și eliminare a unui element. Aceste operații se realizează la un singur capăt al structurii, numit vârful stivei.

În timpul operațiilor cu stiva avem acces numai la elementul din vârful stivei.

Operații cu stiva

Cu o stivă se pot face următoarele operații:

• inițializarea stivei – crearea unei stive vide;
• verificarea faptului că o stivă este sau nu vidă;
• adăugarea unui nou element pe stivă – elementul devine vârful stivei.
  Operația se numește push;
• eliminarea unui element de pe stivă – se va elimina vârful stivei. Un nou element devine vârf al stivei, sau ea devine vidă.
  Operația se numește pop;
• identificarea valorii elementului din vârful stivei – accesul la acel element.
  Operația se numește top.

Imaginați-vă o stivă de lăzi într-un depozit. Dacă adăugăm încă o ladă, o vom plasa în vârful stivei. Dacă luăm o ladă, o vom lua pe cea din vârful stivei – altfel s-ar răsturna stiva!!

Deoarece operațiile cu elementele stivei se fac la același capăt, spunem că stiva este o structură de date de tip LIFO – Last In First Out (ultimul intrat, primul ieșit).

Modalități de implementare a stivei

Stiva poate fi implementată în limbajul C++ în mai multe moduri:

• implementare statică, prin intermediul tablourilor;
• implementare dinamică, prin intermediul listelor alocate dinamic;
• folosirea containerului stack din STL.

Implementarea statică a stivei

Vom folosi un tablou alocat static și o variabilă simplă prin care identificăm vârful stivei. În continuare considerăm o stivă cu elemente întregi.

Declarații

const int DIM = 100;

int S[DIM], vf;

Inițializarea stivei – crearea unei stive vide

vf = 0;

Verificarea faptului că stiva este vidă

vf == 0 // stivă vidă

vf > 0 // stivă nevidă

Adăugarea unui element – PUSH

S[vf++] = VALOARE ;

Eliminarea unui element – POP

vf --;

Identificarea valorii din vârful stivei – TOP

S[vf-1]