Stive

Stiva (în engleză Stack) este o colecție ale cărei elemente sunt considerate, la nivel conceptual, că sunt puse unul peste altul, astfel încât orice element adăugat se pune în vârful stivei ("peste" cele deja existente), iar extragerea unui element se poate face numai din vârful stivei, în ordinea inversă celei în care elementele au fost introduse.

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 Stack

Clasa java.util.Stack extinde clasa java.util.Vector și are ca instanțe stive de obiecte.
 
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.
 
Exemplu
In fișierul TestStack.java este dat un exemplu de aplicație în care se testează clasa java.util.Stack. La lansarea în execuție a aplicației se dau ca parametri în linia de comandă câteva cuvinte, care sunt puse în stivă, apoi sunt extrase și afișate în ordine inversă celei inițiale. S-au folosit atât metodele clasei Stack (push, pop, search, empty) cât și metode moștenite de la superclase, cum sunt size si toString.

Cozi

Coada este o structură FIFO (First In First Out - primul intrat este primul ieșit). Orice element nou adăugat devine ultimul din coadă, în timp ce extragerea de elemente se face din "capul" cozii.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați