Colecția Stack

Clasa Stack<T> reprezintă o colecție care folosește algoritmul LIFO ("ultimul venit - primul plecat"). În această organizare, fiecare element adăugat este plasat deasupra elementului anterior. Extracția din colecție se face în ordine inversă - este extras elementul care se află deasupra tuturor în stivă.

Stiva este o structură de date frecvent întâlnită în viața reală. Exemple banale de stive sunt teancurile de cărți sau farfurii, unde fiecare carte sau farfurie nouă este plasată deasupra celei anterioare.

Iar extragerea din acest teanc se face în ordine inversă - mai întâi elementul de deasupra și așa mai departe. Un alt exemplu este îmbrăcămintea: să presupunem că o persoană iese afară pe vreme de iarnă și își pune mai întâi un tricou, apoi o cămașă, un pulover și, în final, o geacă.

Când persoana se dezbracă, o face în ordine inversă: mai întâi geaca, apoi puloverul și așa mai departe.

Crearea unei stive

Pentru a crea o stivă, se poate folosi unul dintre cei trei constructori ai săi. În primul rând, putem crea o stivă goală:

Stack<string> people = new Stack<string>();

La crearea unei stive goale, se poate specifica capacitatea stivei:

Stack<string> people = new Stack<string>(16);

De asemenea, se poate inițializa stiva cu elemente dintr-o altă colecție sau array:

var employees = new List<string> { "Tom", "Sam", "Bob" };
Stack<string> people = new Stack<string>(employees);
foreach (var person in people) Console.WriteLine(person);

Console.WriteLine(people.Count); // 3

Pentru parcurgerea stivei se poate folosi ciclul standard foreach. În ciclul foreach, conform algoritmului stivei LIFO, datele sunt extrase în ordine inversă față de adăugare. Rezultatul în consolă în acest caz:

Bob
Sam
Tom
3

Pentru a obține numărul de elemente din stivă se folosește proprietatea Count.

Metodele Stack

Clasa Stack<T> are următoarele metode importante:

• void Clear(): șterge toate elementele din stivă
• bool Contains(T item): verifică dacă elementul item este prezent în stivă și returnează true dacă este
• void Push(T item): adaugă un element în stivă, deasupra
• T Pop(): extrage și returnează primul element din stivă
• T Peek(): returnează primul element din stivă fără a-l șterge

Să vedem un exemplu practic:

var people = new Stack<string>();
people.Push("Tom");
// people = { Tom }
people.Push("Sam");
// people = { Sam, Tom }
people.Push("Bob");
// people = { Bob, Sam, Tom }

// obținem primul element din stivă fără a-l șterge
string headPerson = people.Peek();
Console.WriteLine(headPerson);  // Bob

string person1 = people.Pop();
// people = { Sam, Tom }
Console.WriteLine(person1);  // Bob

string person2 = people.Pop();
// people = { Tom }
Console.WriteLine(person2);  // Sam

string person3 = people.Pop();
// people = { }
Console.WriteLine(person3);  // Tom

Funcționarea stivei poate fi reprezentată prin următoarea ilustrație:

Este de remarcat că, dacă folosim metodele Peek sau Pop pentru a obține primul element dintr-o stivă goală, programul va arunca o excepție. Prin urmare, înainte de a obține un element, putem verifica numărul de elemente din stivă:

if(people.Count > 0)
{
   var person = people.Peek();
   people.Pop();
}

Sau putem folosi perechea de metode:

• bool TryPop(out T result): șterge primul element din stivă și îl atribuie variabilei result, returnează true dacă stiva nu este goală și elementul a fost obținut cu succes
• bool TryPeek(out T result): atribuie variabilei result primul element din stivă fără a-l șterge, returnează true dacă elementul a fost obținut cu succes

Aplicarea metodelor:

var people = new Stack<string>();
people.Push("Tom");
// people = { Tom }

// ștergem elemente
var success1 = people.TryPop(out var person1);  // success1 = true
if (success1) Console.WriteLine(person1); // Tom

var success2 = people.TryPeek(out var person2);  // success2 = false
if (success2) Console.WriteLine(person2);