Stive

Stiva (in engleza Stack) este o colectie ale carei elemente sunt considerate, la nivel conceptual, ca sunt puse unul peste altul, astfel incat orice element adaugat se pune in varful stivei ("peste" cele deja existente), iar extragerea unui element se poate face numai din varful stivei, in ordinea inversa in care elementele au fost introduse.

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 Stack

Clasa java.util.Stack este derivata din clasa java.util.Vector si are ca instante stive de obiecte.
 
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.
 
Exemplu 
In fisierul TestStack.java este dat un exemplu de aplicatie in care se testeaza clasa java.util.Stack. La lansarea in executie a aplicatiei se dau ca parametri in linia de comanda cateva cuvinte, care sunt puse in stiva, apoi sunt extrase si afisate in ordine inversa celei initiale. S-au folosit atat metodele clasei Stack (push, pop, search, empty) cat si metode mostenite de la superclase, cum sunt size si toString.

Cozi

Coada este o structura FIFO (First In First Out - primul intrat este primul iesit). Orice element nou adaugat devine ultimul din coada, in timp ce extragerea de elemente se face din "capul" cozii.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati