Stiva si coada implementate ca liste alocate dinamic

Stiva este o structura de date abstracta pentru care atat operatia de inserare a unui element cat si operatia de extragere a unui element se realizeaza de la un singur capat, denumit varful stivei. Deci singurul element la care avem acces direct din stiva este cel din varf.

Stiva este necesara pentru memorarea unor informatii si regasirea acestora intr-o anumita ordine, descrisa de principiul LIFO (last in first out). Stiva este folosita atunci cand programul trebuie sa amane executia unor operatii, pentru a le executa ulterior, in ordinea inversa a aparitiilor lor. Un bun exemplu de utilizare a stivelor il reprezinta evaluarea unor expresii matematice (prin aducerea unei expresii matematice la forma poloneza, spre exemplu).

Astfel, stiva poate fi privita ca o lista liniara, preferabil dublu inlantuita (pentru a putea sterge cu usurinta ultimul element si pentru a putea trece la elemental de sub el fara a fi nevoie de a parcurge din nou intreaga lista). Operatiile posibile in lista ar fi doar:

Adaugarea unui element la finalul listei .

Consultarea sau modificarea ultimului element.

Stergerea ultimului element din lista.

Coada este o structura de date abstracta pentru care operatia de inserare a unui element se realizeaza de la un capat, in timp ce operatia de extragere a unui element se realizeaza de la celalalt. Utilitatea structurii de tip coada reiese din modul sau de functionare: este necesara utilizarea unei cozi atunci cand informatiile trebuie prelucrate exact in ordinea in care au fost retinute in coada. Un bun exemplu de folosire a unei cozi il reprezinta imprimanta, cand un utilizator face mai multe cereri de imprimare in acelasi timp, ele sunt memorate intr-o coada de tiparire = Queue. Imprimanta le va tipari in ordinea in care vor aparea. Datorita acestui lucru, putem spune ca o coada functioneaza dupa principiul FIFO (first in first out).

Este foarte avantajos sa privim coada ca o lista liniara alocata simplu inlantuit unde prelucram mereu primul element, iar elementele care se adauga, se pun la sfarsitul listei. Dupa ce s-a incheiat prelucrarea primului element si nu mai este necesar, primul element este sters iar al doilea devine primul, economisind in felul acesta foarta multa memorie. Operatii premise:

Adaugare la sfarsitul listei.

Consultarea sau modificarea primului element.

Stergerea primului element al listei.