Stiva este o structură de date liniară în care sunt definite trei operații: adăugarea unui element în partea superioară a stivei (Push – împingere), eliminarea unui element din partea superioară a stivei (Pop – scoatere) și inspectarea elementului din partea de sus, fără a fi eliminat (Peek – inspectează). Toate aceste operațiuni sunt foarte rapide – este nevoie de un timp constant pentru a le executa. Stiva nu acceptă operațiunile de căutare și acces prin index. Stiva este o structură de date care are un comportament LIFO (ultimul venit, primul plecat – last in, first out). Se utilizează atunci când trebuie să modelăm un astfel de comportament – de exemplu, dacă trebuie să păstrăm calea către poziția curentă într-o căutare recursivă. Utilizați o stivă atunci când trebuie să implementați comportamentul „last in, first out” (LIFO).
Ca și lista, o stivă are o metodă de a adăuga și a returna elemente, cu o mică diferență de comportament.
Pentru a adăuga o structură de date în stivă, trebuie să apelați metoda Push(), care este echivalentul lui Add() al unei liste. Preluarea unei valori este ușor diferită. Stiva are o metodă numită Pop(), care returnează și elimină ultimul obiect adăugat. Dacă doriți să verificați valoarea de sus a unei stive fără a o elimina, utilizați apelul la metoda Peek().
Există două formate de definire a unei stive în C#:
1 2 |
Stack stiva = new Stack(); Stack<string> stiva = new Stack<string>(); |
Diferența dintre ele constă în faptul că structura Stack simplă va funcționa cu obiecte (Object), în timp ce Stack va accepta doar un tip specificat.
Iată codul C# pentru a adăuga și traversa printr-o structură de date Stack:
1 2 3 4 5 6 7 |
Stack<string> stiva = new Stack<string>(); stiva.Push("unu"); stiva.Push("doi"); stiva.Push("trei"); while (stiva.Count > 0) Console.WriteLine(stiva.Pop()); |
Dacă executați codul C# de mai sus, veți vedea că lista este returnată în ordinea: „trei”, „doui”, „unu”.
Acestea sunt principalele metode ale unui Stack:
Push() – De obicei, prima acțiune pe care trebuie să o faceți în Stack este să adăugați elemente în ea. Cuvântul Push este un termen informatic care înseamnă „adăugare în partea de sus”.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
using System; using System.Collections.Generic; class Program { static Stack<int> ReturneazaStiva() { Stack<int> stiva = new Stack<int>(); stiva.Push(100); stiva.Push(1000); stiva.Push(10000); return stiva; } static void Main() { var stiva = ReturneazaStiva(); Console.WriteLine("--- continutul stivei ---"); foreach (int i in stiva) Console.WriteLine(i); } } |
Pop(), Peek() – Aici folosim Pop și Peek. Când apelați Pop(), elementul din partea superioară a Stack-ului este returnat, iar apoi este eliminat din colecție.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
using System; using System.Collections.Generic; class Program { static void Main() { // Obtine stiva Stack<int> stiva = ReturneazaStiva(); // preia si elimina primul element. int pop = stiva.Pop(); // Afiseaza la consola. Console.WriteLine("--- Element scos din partea de sus a stivei ---"); Console.WriteLine(pop); // Observa primul element al stivei. int peek = stiva.Peek(); Console.WriteLine("--- Elementul curent din partea de sus a stivei ---"); Console.WriteLine(peek); } static Stack<int> ReturneazaStiva() { Stack<int> stiva = new Stack<int>(); stiva.Push(100); stiva.Push(1000); stiva.Push(10000); return stiva; } } |
Clear() – este o metodă fără parametri. Șterge conținutul stivei.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Collections.Generic; class Program { static void Main() { // preia stiva Stack<int> stiva = GetStack(); // NUmara numarul de elemente din stiva int numar = stiva.Count; Console.WriteLine("--- Numar de elemente ---"); Console.WriteLine(numar); // Sterge stiva stiva.Clear(); Console.WriteLine("--- Elementele stivei au fost sterse ---"); Console.WriteLine(stiva.Count); } static Stack<int> ReturneazaStiva() { Stack<int> stiva = new Stack<int>(); stiva.Push(100); stiva.Push(1000); stiva.Push(10000); return stiva; } } |
Contains() – Căută în stivă un anumit element. Metoda Contains() a Stivei returneaza adevărat (True) dacă elementul este găsit.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
using System; using System.Collections.Generic; class Program { static void Main() { // Un exemplu de array de tip string. string[] valori = { "unu", "doi", "trei" }; // Copiaza array-ul in stiva. var stiva = new Stack<string>(valori); // Afiseaza stiva. Console.WriteLine("--- Continutul stivei ---"); foreach (string valoare in stiva) Console.WriteLine(valoare); // Verifica daca stiva contine elementul "trei" Console.WriteLine("--- Rezultatul metodei Contains ---"); bool contine = stiva.Contains("trei"); Console.WriteLine(contine); } } |
Cea mai importantă proprietate a unui Stack este:
Count – indică numărul de elemente dintr-o stivă.
Valoarea null este permisă în stive cu tipuri de referință, cum ar fi string. Puteți și să atribui stivei valoarea null în loc de a apela Clear(). La alocarea la valoarea null, conținutul nu este modificat. În schimb, referința este dezrădăcinată de colectorul de gunoi (garbage collector). Când apelați Pop() sau Peek() pe stivă, execuția va genera o excepție, dacă Stack-ul are zero elemente. Pentru a rezolva această problemă, trebuie să verificați proprietatea Count. Aici vom „prinde” excepția ridicată de această situație (nu am învățat încă despre excepții, considerați-le doar un tip special de erori):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
using System; using System.Collections.Generic; class Program { static void Main() { // Creaza o stiva goala var stiva = new Stack<int>(); try { // Aceasta va genera o exceptie. int pop = stiva.Pop(); } catch (Exception ex) { Console.WriteLine("--- Exceptie generata de Pop ---"); Console.WriteLine(ex.ToString()); } // Aici apelam Pop in siguranta. if (stiva.Count > 0) int sigur = stiva.Pop(); else Console.WriteLine("--- Evitati exceptiile folosing metoda Count! ---"); } } |
Tags: stack, structuri de date