Share
Până acum, am analizat colecțiile care oferă o stocare foarte importantă a datelor, în esență abstracții pe o matrice. În această secțiune, ne vom uita la ceea ce se întâmplă atunci când adăugăm câteva comportamente de bază care schimbă în totalitate utilitatea colecțiilor.
O stivă este o colecție care returnează obiecte către apelant într-un model Last-In-Out-Out (LIFO). Ce înseamnă acest lucru este faptul că ultimul obiect adăugat colecției va fi primul obiect returnat.
Stivele diferă de listă și de colecțiile de tip array. Ele nu pot fi indexate direct, obiectele sunt adăugate și eliminate prin diferite metode, iar conținutul lor este mai opac decât liste și matrice. Ceea ce vreau să spun este că, în timp ce o colecție bazată pe listă oferă o metodă Contains, un stiva nu o face. În plus, un stiva nu poate fi enumerată. Pentru a înțelege de ce este acest lucru, să aruncăm o privire asupra a ceea ce este un stack și asupra modului în care utilizarea unui teanc conduce aceste diferențe.
Una dintre cele mai comune analogii pentru un stack este stiva de placi restaurant. Acesta este un dispozitiv simplu cu arc pe care sunt așezate plăci curate. Arcul asigură că, indiferent de numărul de plăci din stivă, placa superioară poate fi accesată cu ușurință. Plăcile curate sunt adăugate în partea superioară a teancului și, atunci când un client îndepărtează o placă, el sau ea scoate cea mai mare plăcuță (cea mai recentă plăcuță adăugată).
Începem cu un raft gol.
O stivă de plăci goale (arcul nu ține plăci) Apoi adăugăm o placă roșie, albastră și verde rack-ului în ordinea aceea.
Punctul cheie pentru a înțelege aici este că, pe măsură ce se adaugă plăci noi, ele se adaugă la partea de sus a stivei. Dacă un client preia o placă, el sau ea va primi cea mai recentă plăcuță adăugată (plăcuța verde). Următorul client va primi placa albastră, iar în final placa roșie va fi îndepărtată.
Acum, când înțelegem cum funcționează o stivă, să definim câțiva termeni noi. Atunci când un element este adăugat în teanc, acesta este "împins" folosind Apăsați metodă. Când un element este scos din teanc, acesta este "oprit" folosind opțiunea Pop metodă. Elementul de sus din stiva, cel mai recent adăugat, poate fi "cercetat" la utilizarea funcției Arunca o privire metodă. Peeking vă permite să vizualizați elementul fără a îl elimina din stivă (la fel cum clientul de pe placa de placă ar putea vedea culoarea plăcii superioare). Având în vedere acești termeni, să analizăm punerea în aplicare a Grămadă clasă.
Grămadă clasa defineste Apăsați, Pop, și Arunca o privire metode, a Numara proprietate, și utilizează LinkedList pentru a stoca valorile conținute în stivă.
public Stack clasic LinkedList _items = new LinkedList (); public void Push (valoarea T) arunca noua NotImplementedException (); public T Pop () arunca noua NotImplementedException (); public T Peek () arunca noua NotImplementedException (); public int Count get;
| Comportament | Adaugă un element în partea de sus a stivei. |
| Performanţă | O (1) |
Din moment ce folosim o listă legată ca magazin de asistență, tot ce trebuie să faceți este să adăugați noul articol la sfârșitul listei.
public void Push (valoare T) _items.AddLast (valoare);
| Comportament | Elimină și returnează ultimul element adăugat în stivă. Dacă stiva este goală, un InvalidOperationException este aruncat. |
| Performanţă | O (1) |
Apăsați adaugă elemente în partea din spate a listei, așa că le vom "arunca" din spate. Dacă lista este goală, este aruncată o excepție.
Accentsconagua
public T Pop () if (_items.Count == 0) arunca noua InvalidOperationException ("Stiva este goala"); Rezultat T = _items.Tail.Value; _items.RemoveLast (); rezultatul retur; | Comportament | Returnează ultimul element adăugat la stivă, dar lasă elementul din teanc. Dacă stiva este goală, un InvalidOperationException este aruncat. |
| Performanţă | O (1) |
public T Peek () if (_items.Count == 0) arunca noua InvalidOperationException ("Stiva este goala"); returnați _items.Tail.Value; | Comportament | Returnează numărul de elemente din stivă. |
| Performanţă | O (1) |
Din moment ce se presupune că stiva este o structură de date opacă, de ce avem a Numara proprietate? Știind dacă un teanc este gol (Numărătoare == 0) este foarte util, mai ales din moment ce Pop aruncă o excepție atunci când stiva este goală.
public int Număr get return _items.Count;
Exemplul clasic de stivă este calculatorul cu notație polară inversă (RPN).
Sintaxa RPN este destul de simplă. Folosește:
mai degrabă decât tradițional:
Cu alte cuvinte, în loc de a spune "4 + 2", am spune "4 2 +". Dacă doriți să înțelegeți semnificația istorică a sintaxei RPN, vă încurajez să mergeți la Wikipedia sau motorul dvs. de căutare preferat.
Modul RPN este evaluat și motivul pentru care un teanc este atât de util la implementarea unui calculator RPN poate fi văzut în următorul algoritm:
pentru fiecare valoare de intrare dacă valoarea este un număr întreg împingeți valoarea pe stackul de operand altfel dacă valoarea este un operator pop valorile din stânga și din dreapta din stivă evaluează operatorul împinge rezultatul pe răspunsul stivei de la stivă.
Deci având în vedere șirul de intrare "4 2 +", operațiile ar fi:
împinge (4) împinge (2) împinge (pop () + pop ())
Acum stiva conține o singură valoare: șase (răspunsul).
Următoarea este o implementare completă a unui calculator simplu care citește o ecuație (de exemplu, "4 2 +") din intrarea consolei, împarte intrarea în fiecare spațiu (["4", "2" și "+" , și efectuează algoritmul RPN pe intrare. Buclele continuă până când intrarea este cuvântul "părăsiți".
void RpnLoop () în timp ce (adevărat) Console.Write (">"); string input = Console.ReadLine (); dacă (input.Trim (). ToLower () == "quit") break; // Stackul de numere întregi care nu au fost încă operate. Valorile stivei = Stack nou (); foreach (token șir în input.Split (new char [] ")) // Dacă valoarea este o valoare int ... int; dacă (int.TryParse (token, out value)) // ... împingeți stivă values.Push (value); else // În caz contrar, evaluați expresia ... int rhs = values.Pop (); int lhs = values.Pop (); // ... și afișați rezultatul în stivă. (lhs - rhs); pauză (lhs - rhs); pauză (lhs - rhs); pauză (lhs - rhs) (lhs / rhs); break; case "%": values.Push (lhs% rhs); break; implicit: aruncați ArgumentException nou (string.Format (" 0 ", token)); // Ultimul element din stivă este rezultatul Console.WriteLine (values.Pop ()); Cozile sunt foarte asemănătoare cu stivele - acestea oferă o colecție opacă din care pot fi adăugate obiecte (enqueued) sau eliminate (dequeued) într-o manieră care adaugă valoare unei colecții bazate pe listă.
Cozile sunt o colecție First-In-Out-Out (FIFO). Aceasta înseamnă că articolele sunt eliminate din coadă în aceeași ordine în care au fost adăugate. Poți să te gândești la o coadă ca o linie la un magazin de checkout pentru magazin, care intră în linie și sunt întreținute în ordinea în care ajung.
Cozi sunt utilizate în mod obișnuit în aplicații pentru a furniza un buffer pentru a adăuga elemente pentru prelucrare ulterioară sau pentru a oferi acces ordonat la o resursă partajată. De exemplu, dacă o bază de date este capabilă să se ocupe de o singură conexiune, ar putea fi utilizată o coadă pentru a permite firului să aștepte rândul său (în ordine) pentru a accesa baza de date.
Coadă, ca Grămadă, este susținută de a LinkedList. În plus, oferă metodele Puneți în coadă (pentru a adăuga elemente), Dequeue (pentru a elimina elementele), Arunca o privire, și Numara. Ca Grămadă, nu va fi tratată ca o colecție de scopuri generale, adică nu va fi implementată ICollection.
clasa publica publica LinkedList _items = new LinkedList (); public void Enqueue (valoarea T) arunca noua NotImplementedException (); public T Dequeue () arunca noua NotImplementedException (); public T Peek () arunca noua NotImplementedException (); public int Count get;
| Comportament | Adaugă un element la sfârșitul coadă. |
| Performanţă | O (1) |
Această implementare adaugă elementul la începutul listei legate. Elementul ar putea fi adăugat la fel de ușor la sfârșitul listei. Tot ce contează cu adevărat este că elementele sunt enqueued la un capăt al listei și degradați de la cealaltă (FIFO). Observați că acesta este opusul clasei Stack, în care elementele sunt adăugate și eliminate din același scop (LIFO).
Public voie Enqueue (valoare T) _items.AddFirst (valoare);
| Comportament | Elimină și returnează cel mai vechi element din coadă. Un InvalidOperationException este aruncat dacă coada este goală. |
| Performanţă | O (1) |
De cand Puneți în coadă a adăugat elementul la începutul listei, Dequeue trebuie să eliminați elementul de la sfârșitul listei. Dacă coada nu conține elemente, este aruncată o excepție.
public T Dequeue () if (_items.Count == 0) arunca noua InvalidOperationException ("Coada este goala"); T last = _items.Tail.Value; _items.RemoveLast (); retur ultima; | Comportament | Returnează următorul element care ar fi returnat dacă s-a sunat Dequeue. Coada de așteptare este lăsată neschimbată. O operație InvalidOperationException este aruncată dacă coada este goală. |
| Performanţă | O (1) |
public T Peek () if (_items.Count == 0) arunca noua InvalidOperationException ("coada este goala"); returnați _items.Tail.Value; | Comportament | Returnează numărul de articole aflate în coadă. Returnează 0 dacă coada este goală. |
| Performanţă | O (1) |
public int Număr get return _items.Count;
O coadă de așteptare dublă, sau deque, extinde comportamentul coadă, permițând adăugarea sau eliminarea elementelor de pe ambele părți ale coadă. Acest nou comportament este util în mai multe domenii de probleme, în special sarcini și planificarea firului. Este, de asemenea, util pentru implementarea altor structuri de date. Vom vedea un exemplu de utilizare ulterioară a unei scheme de implementare a unei alte date.
Deque clasa este susținută de o listă dublată. Acest lucru ne permite să adăugăm și să eliminăm elemente din partea din față sau din spate a listei și să accesăm Primul și Ultimul proprietăți. Schimbările principale dintre clasa Queue și clasa Deque sunt că Puneți în coadă, Dequeue, și Arunca o privire metodele au fost dublate Primul și Ultimul variantele.
clasa publică Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (valoare T) arunca noua NotImplementedException (); public void EnqueueLast (valoarea T) arunca noua NotImplementedException (); public T DequeueFirst () arunca noua NotImplementedException (); public T DequeueLast () arunca noua NotImplementedException (); public T PeekFirst () arunca noua NotImplementedException (); public T PeekLast () arunca noua NotImplementedException (); public int Count get;
| Comportament | Adaugă valoarea introdusă în capul coadă. Acesta va fi următorul element dequeued de DequeueFirst. |
| Performanţă | O (1) |
public void EnqueueFirst (valoare T) _items.AddFirst (valoare);
| Comportament | Adaugă valoarea adăugată la coada coadă. Acesta va fi următorul element dequeued de DequeueLast. |
| Performanţă | O (1) |
public void EnqueueLast (valoare T) _items.AddLast (valoare);
| Comportament | Elimină și returnează primul element din lista de decriptare. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T DequeueFirst () if (_items.Count == 0) arunca noua InvalidOperationException ("DequeueFirst numit când deque este gol"); T temp = _items.Head.Value; _items.RemoveFirst (); temperatura de revenire; | Comportament | Îndepărtează și returnează ultimul element din deque. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T DequeueLast () if (_items.Count == 0) arunca noua InvalidOperationException ("DequeueLast numit când deque este gol"); T temp = _items.Tail.Value; _items.RemoveLast (); temperatura de revenire; | Comportament | Returnează primul element în deque, dar lasă colecția neschimbată. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T PeekFirst () if (_items.Count == 0) arunca noua InvalidOperationException ("PeekFirst numit când deque este gol"); returnați _items.Head.Value; | Comportament | Returnează ultimul element din deque, dar lasă colecția neschimbată. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T PeekLast () if (_items.Count == 0) arunca noua InvalidOperationException ("PeekLast numit când deque este gol"); returnați _items.Tail.Value; | Comportament | Returneaza numarul de elemente aflate in prezent in deque sau 0 daca deque este gol. |
| Performanţă | O (1) |
public int Număr get return _items.Count;
Deques sunt adesea folosite pentru a implementa alte structuri de date.
Am văzut un teanc implementat folosind a LinkedList, asa ca acum sa ne uitam la unul implementat folosind a Deque.
S-ar putea să te întrebi de ce aș alege să pun în aplicare a Grămadă folosind un Deque mai degrabă decât a LinkedList. Motivul este unul de performanță și de reutilizare a codului. O listă legată are costul cheltuielilor de tip nod și localizarea redusă a datelor - elementele sunt alocate în heap și locațiile de memorie pot să nu se afle una lângă cealaltă, provocând un număr mai mare de pierderi de memorie cache și pagini la CPU și hardware de memorie niveluri. O implementare mai performantă a unei coada de așteptare ar putea să utilizeze mai degrabă o matrice decât magazinul de susținere decât o listă. Acest lucru ar permite o cheltuială mai mică per nod și ar putea îmbunătăți performanța prin abordarea unor probleme legate de localități.
Punerea în aplicare a Grămadă sau Coadă ca o matrice este o implementare mai complexă. Prin implementarea Deque în această manieră mai complexă și folosind-o ca bază pentru alte structuri de date, putem realiza avantajele de performanță pentru toate structurile în timp ce trebuie doar să scriem codul o singură dată. Aceasta accelerează timpul de dezvoltare și reduce costurile de întreținere.
Vom examina un exemplu de a Deque ca o matrice mai târziu în această secțiune, dar mai întâi să ne uităm la un exemplu de a Grămadă implementat cu ajutorul unui Deque.
public Stack de clasă Deque _items = new Deque (); public void Push (valoarea T) _items.EnqueueFirst (valoare); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Număr get return _items.Count;
Observați că toate verificările de eroare sunt acum amânate la Deque precum și orice optimizare sau remediere a erorilor făcute Deque se va aplica automat la Grămadă clasă. Punerea în aplicare a Coadă este la fel de ușor și ca atare este lăsat ca un exercițiu pentru cititor.
Așa cum am menționat anterior, există avantaje pentru folosirea unei matrice, mai degrabă decât a unei liste legate, ca magazin de susținere pentru Deque (un deque de numere întregi). În mod conceptual, acest lucru pare simplu, dar, de fapt, există mai multe probleme care trebuie abordate pentru ca acest lucru să funcționeze.
Să analizăm grafic unele dintre aceste aspecte și apoi să vedem cum putem să le rezolvăm. Pe parcurs, țineți minte problemele privind politica de creștere discutate în secțiunea ArrayList și că aceleași probleme se aplică aici.
Când colecția este creată, este o matrice de lungime 0. Să ne uităm la modul în care unele acțiuni afectează matricea internă. Pe măsură ce treceți prin aceasta, observați că verdele "h" și roșu "t" din figuri se referă la "cap" și "coadă", respectiv. Capul și coada sunt indicele matricei care indică primul și ultimul element din coadă. Pe măsură ce adăugăm și eliminăm elemente, interacțiunea dintre cap și coadă devine mai clară.
Deque deq = nou Deque (); deq.EnqueueFirst (1);
Adăugarea unei valori în fața deque deq.EnqueueLast (2);
Adăugarea unei valori la sfârșitul dequeului deq.EnqueueFirst (0);
Adăugând o altă valoare în partea din față a deque; indexul capului se înfășoară Observați ce sa întâmplat în acest moment. Indicele capului a înfășurat până la capătul matricei. Acum, primul element din deque, ce ar fi returnat DequeueFirst, este valoarea la indexul matricei trei (zero).
deq.EnqueueLast (3);
Adăugarea unei valori la sfârșitul dequeului În acest moment, matricea este umplută. Când se adaugă un alt element, vor apărea următoarele:
EnqueueFirst - Elementul este adăugat la indexul zero (operația de copiere lasă acest lucru deschis).EnqueueLast - Elementul este adăugat la sfârșitul matricei. deq.EnqueueLast (4);
Adăugarea unei valori la sfârșitul dequeului extins Acum, să vedem ce se întâmplă când articolele sunt eliminate din Deque.
deq.DequeueFirst ();
Eliminarea primului element din dequetele extinse deq.DequeueLast ();
Eliminarea ultimului element din deque expanded Punctul critic care trebuie luat în considerare este că, indiferent de capacitatea matricei interne, conținutul logic al lui Deque sunt elementele de la indexul de cap la indexul coadă, ținând cont de necesitatea de a se înfășura în jurul matricei. O matrice care oferă comportamentul înfășurării de la cap până la coadă este adesea cunoscută ca un tampon circular.
Cu această înțelegere a modului în care funcționează logica matricei, să ne aruncăm în dreptul codului.
Metodele și proprietățile Deque bazate pe matrice sunt identice cu cele bazate pe listă, astfel încât acestea nu vor fi repetate aici. Cu toate acestea, lista a fost înlocuită cu o matrice și acum există trei proprietăți care conțin informații despre dimensiune, cap și coadă.
clasa publică Deque T [] _items = new T [0]; // Numărul de articole din coadă. int _size = 0; // Indexul primului (cel mai vechi) element din coadă. int _head = 0; // Indexul ultimului (cel mai nou) element din coadă. int _tail = -1; ...
Atunci când matricea internă trebuie să crească, algoritmul de a mări dimensiunea matricei, de a copia conținutul matricei și de a actualiza valorile indexului intern trebuie să ruleze. Puneți în coadă metoda efectuează acea operație și este apelată de ambele EnqueueFirst și EnqueueLast. startingIndex parametru este utilizat pentru a determina dacă să părăsească slotul matrice la index zero deschis (în cazul EnqueueFirst).
Acordați o atenție specială modului în care datele sunt dezvelite în cazurile în care plimbarea de la cap la coadă necesită deplasarea la zero a capătului matricei.
void privat allocateNewArray (int startIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = nou T [newLength]; dacă (_size> 0) int targetIndex = startIndex; // Copiați conținutul ... // Dacă matricea nu are nici o împachetare, copiați intervalul valid. // Altfel, copiați de la cap până la sfârșitul matricei și apoi de la 0 la coadă. // Dacă coada este mai mică decât capul, am înfășurat. dacă (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0] ... newArray [N]. pentru (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1] ... pentru (index int = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0] ... newArray [N] pentru (int index = _head; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; _head = startingIndex; _tail = targetIndex - 1; // Compensate for the extra bump. else // Nothing in the array. _head = 0; _tail = -1; _items = newArray;
| Comportament | Adaugă valoarea introdusă în capul coadă. Acesta va fi următorul element dequeued de DequeueFirst. |
| Performanţă | O (1) în majoritatea cazurilor; O (n) atunci când este necesară creșterea. |
public void EnqueueFirst (element T) // Dacă matricea trebuie să crească. dacă (_items.Length == _size) allocateNewArray (1); // Deoarece știm că matricea nu este plină și capul este mai mare decât 0, // știm că slotul din față al capului este deschis. dacă (_head> 0) _head--; altfel // În caz contrar, trebuie să înfășurăm până la capătul matricei. _head = _items.Length - 1; _items [_head] = element; _size ++;
| Comportament | Adaugă valoarea adăugată la coada coadă. Acesta va fi următorul element dequeued de DequeueLast. |
| Performanţă | O (1) în majoritatea cazurilor; O (n) atunci când este necesară creșterea. |
public void EnqueueLast (element T) // Dacă matricea trebuie să crească. dacă (_items.Length == _size) allocateNewArray (0); // Acum avem o matrice dimensionată corect și putem să ne concentrăm asupra problemelor de împachetare. // Dacă _tailul este la sfârșitul matricei trebuie să înfășurăm. dacă (_tail == _items.Length - 1) _tail = 0; altceva _tail ++; _items [_tail] = element; _size ++;
| Comportament | Elimină și returnează primul element din lista de decriptare. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T DequeueFirst () if (_size == 0) arunca noua InvalidOperationException ("Deque este gol"); Valoarea T = _items [_head]; dacă (_head == _items.Length - 1) // Dacă capul este la ultimul index al matricei, împachetați-l. _head = 0; altceva // Mutare în slotul următor. _head ++; _mărimea--; valoare returnată; | Comportament | Îndepărtează și returnează ultimul element din deque. O invalidOperationException este aruncat daca deque este gol. |
| Performanţă | O (1) |
public T DequeueLast () if (_size == 0) arunca noua InvalidOperationException ("Deque este gol"); Valoare T = _items [_tail]; dacă (_tail == 0) // Dacă coada se află la primul indice din matrice, înfășurați-o în jurul. _tail = _items.Length - 1; altceva // Mutare în slotul anterior. _coadă--; _mărimea--; valoare returnată; | Comportament | Returnează primul element în deque, dar lasă colecția neschimbată. Un InvalidOperationException este aruncat dacă deque este gol. |
| Performanţă | O (1) |
public T PeekFirst () if (_size == 0) arunca noua InvalidOperationException ("Deque este gol"); retur _items [_head]; | Comportament | Returnează ultimul element din deque, dar lasă colecția neschimbată. Un InvalidOperationException este aruncat dacă deque este gol. |
| Performanţă | O (1) |
public T PeekLast () if (_size == 0) arunca noua InvalidOperationException ("Deque este gol"); return _items [_tail]; | Comportament | Returnează numărul de elemente aflate în prezent în deque sau 0 dacă deque este gol. |
| Performanţă | O (1) |
public int Număr get return _size;
