Stiva este o structura de date LIFO (Last In First Out -
ultimul intrat este primul ieșit). Principalele operații asupra stivei
sunt:
- crearea stivei;
- punerea unui element în vârful stivei (operația push);
- extragerea elementului din vârful stivei (operația pop);
- vizitarea elementului din vârful stivei fără a-l extrage.
Se observă cu usurință că ultimele trei operații au complexitatea O(1).
Stiva este o structură de date larg utilizată in informatică. Dintre multiplele utilizări, menționăm că stiva este folosită atât la implementarea algoritmilor recursivi, cât și ca structură auxiliară la traversarea unor structuri de date mai complicate, cum sunt arborii și grafurile.
Stiva este un caz particular de listă, în care adăugarea sau eliminarea elementelor se face numai în unul din capetele acesteia. În cazul când stiva se realizează sub forma de listă implementată ca tablou, punerea și eliminarea elementelor se face la capătul "din dreapta" (pe poziția din tablou cu cea mai mare valoare a indicelui). În acest fel, la efectuarea acestor operații, nu este necesar să se deplaseze celelalte elemente ale listei.
Clasa java.util.Stack are un singur constructor public Stack() - creează o stivă vidă. Metodele clasei Stack sunt următoarele: public Object push(Object item) - pune elementul item în vârful stivei și intoarce o referință către acest element; public Object pop() - extrage elementul din vârful stivei și întoarce o referință către elementul extras; public Object peek() - întoarce o referință către elementul din vârful stivei, fără a-l extrage; public boolean empty() - întoarce true dacă stiva este vidă; public int search(Object o) - caută în stivă obiectul o și întoarce "adâncimea" la care se găsește acest obiect față de vârful stivei (elementul din vârful stivei se găsește la adancimea 1). Dacă obiectul o nu există în stivă, întoarce -1. Întrucât clasa Stack extinde clasa Vector, moștenește și toate
metodele acesteia, deci asupra instanțelor clasei Stack se pot face și
operațiile specifice listelor și - mai general - asupra colecțiilor.
|
Coada se poate implementa ca o listă, în care adăugarea de elemente se face la unul din capete, iar extragerea se face de la capătul opus.
Complexitatea operațiilor depinde de modul de implementare a cozii.
Dacă pentru coada care conține n elemente se folosește o
listă implementată ca tablou (cum sunt cele din clasele ArrayList sau
Vector), pot sa apară urmatoarele situații:
a/ capul cozii se gasește la indicele 0, iar sfârșitul cozii se
găsește la indicele n-1, unde n este
lungimea cozii. În acest caz, complexitatea operației de punere în coadă
este O(1), iar complexitatea operației de extragere din
coadă este O(n), deoarece după extragere trebuie
deplasate toate elementele rămase;
b/ capul cozii se găsește în poziția n-1, iar ultimul
element din coadă se găsește în poziția de indice 0. În acest caz,
complexitatea punerii în coadă este O(n), iar cea a
extragerii din coadă este O(1).
Vom arăta ulterior că pentru coadă este preferabil să se folosească o structură de listă dublu înlănțuită, în care caz atât punerea în coadă cât și extragerea din coadă au complexitatea O(1).
Coada este o structură de date frecvent folosită in informatică. Ea este utilă atunci când anumite servicii trebuie oferite în ordinea în care au fost primite solicitările.