Saturday, February 16, 2019 15:41

Queue

Queue este o structură liniară de date în care sunt definite două operațiuni: adăugarea unui element în coadă (enqueue) și extragerea elementului poziționat în față (dequeue). Aceste două operațiuni necesită un timp constant pentru a fi executate, deoarece Queue este de obicei implementată cu o listă asociată. Vă reamintesc că lista conectată poate adăuga și elimina rapid elemente din ambele capete. Comportamentul Queue este FIFO (primul venit, primul plecat – first in, first out). Operațiile de căutare și accesarea prin index nu sunt acceptate. Queue poate modela în mod firesc o listă de persoane în așteptare, sarcini sau alte obiecte care trebuie procesate în aceeași ordine în care au fost adăugate (enqueued).

Ca un exemplu de folosire a unei Queue, pot să subliniez implementarea algoritmului BFS (lățirea primei căutări – breadth-first search), în care începem dintr-un element inițial, iar toți vecinii lui sunt adăugați la o coadă. După aceea, ele sunt prelucrate în ordinea în care au fost adăugate și vecinii lor sunt adăugați la coada de așteptare. Această operație este repetată până când ajungem la elementul pe care îl căutăm sau până când vom procesa toate elementele.

Apelul de a adăuga elemente în Queue (sau versiunea Push) este Enqueue():

Operația inversă de eliminare a elementelor se realizează utilizând metoda Dequeue():

În mod similar, apelul metodei Peek() vă permite să vizualizați valoarea primului element fără a îl elimina. Această structură specifică de date este foarte des utilizată în conjuncție cu structurile de date Stack.

Rețineți că structura de date Queue poate fi definită ca și Queue generală și ca și Queue specifică pentru un anumit tip Queue<T>.

Cele mai importante metode ale structurii de date Queue sunt:

Copy(), CopyTo() – Permite copierea elementelor Queue. Putem să avem un Queue, dar trebuie să ciclăm peste elemente în ordine inversă. Apelăm CopyTo() și apoi ciclăm peste array în sens invers. Folosim CopyTo() cu o variabilă de tip int. Alocăm numărul elementelor int[] cu același număr întreg ca și proprietatea Count a Queue.

Ieșirea va arăta astfel:

Clear() – Utilizați această metodă pentru a elimina toate elementele din Queue. Acest lucru poate fi folosit în loc de a atribui referința la o nouă Queue.
Contains() – Puteți utiliza Contains() pentru a căuta prin Queue după un element care se potrivește parametrului căutat. Această metodă efectuează o căutare liniară.
Dequeue() – Înlătura obiectul de la începutul Queue. Nu ciclează prin elemente.
Peek() – Returnează obiectul de la începutul Queue(T) fără a-l elimina. Aceasta înseamnă că doar ne uităm la obiect.
ToArray() – Convertește Queue(T) într-o matrice. Acesta este similar cu CopyTo(), dar oferă noua referință a array-ului.

Cea mai importantă proprietate a coadă este:

Count – Returnează numărul elementelor. Este nevoie de timp constant și nu enumeră elementele.

Comments

comments

Tags: ,

Leave a Reply