Stiva este o structura de date LIFO (Last In First Out - ultimul
intrat este primul iesit). Principalele operatii asupra stivei sunt:
- crearea stivei;
- punerea unui element in varful stivei (operatia
push);
- extragerea elementului din varful stivei (operatia
pop);
- vizitarea elementului din varful stivei fara a-l
extrage.
Se observa cu usurinta ca ultimele trei operatii au complexitatea O(1).
Stiva este o structura de date larg utilizata in informatica. Dintre multiplele utilizari, mentionam ca stiva este folosita atat la implementarea algoritmilor recursivi, cat si ca structura auxiliara la traversarea unor structuri de date mai complicate, cum sunt arborii si grafurile.
Stiva este un caz particular de lista, in care adaugarea sau eliminarea elementelor se face numai in unul din capetele acesteia. In cazul cand stiva se realizeaza sub forma de lista implementata ca tablou, punerea si eliminarea elementelor se face la capatul "din dreapta" (pe pozitia din tablou cu cea mai mare valoare a indicelui). In acest fel, la efectuarea acestor operatii, nu este necesar sa se deplaseze celelalte elemente ale listei.
Clasa java.util.Stack are un singur constructor
public Stack() - creeaza o stiva vida. Metodele clasei Stack sunt urmatoarele: public Object push(Object item) - pune elementul item in varful stivei si intoarce o referinta catre acest element; public Object pop() - extrage elementul din varful stivei si intoarce o referinta catre elementul extras; public Object peek() - intoarce o referinta catre elementul din varful stivei, fara a-l extrage; public boolean empty() - intoarce true daca stiva este vida; public int search(Object o) - cauta in stiva obiectul o si intoarce "adancimea" la care se gaseste acest obiect fata de varful stivei (elementul din varful stivei se gaseste la adancimea 1). Daca obiectul o nu exista in stiva, intoarce -1. Intrucat clasa Stack extinde clasa Vector, mosteneste si toate metodele
acesteia, deci asupra instantelor clasei Stack se pot face si operatiile
specifice listelor si - mai general - asupra colectiilor.
|
Coada se poate implementa ca o lista, in care adaugarea de elemente se face la unul din capete, iar extragerea se face de la capatul opus.
Complexitatea operatiilor depinde de modul de implementare a cozii.
Daca pentru coada care contine n elemente se foloseste o
lista implementata ca tablou (cum sunt cele din clasele ArrayList sau Vector),
pot sa apara urmatoarele situatii:
a/ capul cozii se gaseste la indicele 0, iar sfarsitul
cozii se gaseste la indicele n-1, unde este lungimea
cozii. In acest caz, complexitatea operatiei de punere in coada este O(1),
iar complexitatea operatiei de extragere din coada este O(n),
deoarece dupa extragere trebuie deplasate toate elementele ramase;
b/ capul cozii se gaseste in pozitia n-1,
iar ultimul element din coada se gaseste in pozitia de indice 0. In acest
caz, complexitatea punerii in coada este O(n), iar cea a
extragerii din coada este O(1).
Vom arata ulterior ca pentru coada este preferabil sa se foloseasca o structura de lista inlantuita, in care caz atat punerea in coada cat si extragerea din coada au complexitatea O(1).
Coada este o structura de date frecvent folosita in informatica. Ea este utila atunci cand anumite servicii trebuie oferite in ordinea in care au fost primite solicitarile.