queue(7) Miscellaneous Information Manual queue(7)

queue - implementări ale listelor legate și ale cozilor de așteptare

Fișierul de antet <sys/queue.h> oferă un set de macrocomenzi care definesc și operează cu următoarele structuri de date:

liste legate individual
liste dublu legate
cozi de așteptare legate individual
cozi de așteptare dublu legate
cozi circulare dublu legate

Toate structurile suportă următoarele funcționalități:

•
Inserarea unei noi intrări în capul listei.
•
Inserarea unei noi intrări după orice element din listă.
•
O(1) eliminarea unei intrări din capul listei.
•
Deplasare înainte prin listă.

Dimensiunea codului și timpul de execuție depind de complexitatea structurii de date utilizate, astfel încât programatorii trebuie să aibă grijă să o aleagă pe cea potrivită.

Listele legate individual sunt cele mai simple și acceptă doar funcționalitatea de mai sus. Listele legate individual sunt ideale pentru aplicațiile cu seturi de date mari și cu puține sau deloc eliminări sau pentru implementarea unei cozi LIFO. Listele legate individual adaugă următoarele funcționalități:

•
O(n) eliminarea oricărei intrări din listă.

Cozi de așteptare legate individual (STAILQ)

Cozile de așteptare legate individual adaugă următoarea funcționalitate:

•
Se pot adăuga intrări la sfârșitul unei liste.
•
O(n) eliminarea oricărei intrări din listă.
•
Acestea pot fi concatenate.

Cu toate acestea:

•
Toate inserările de liste trebuie să precizeze capul de listă.
•
Fiecare intrare de cap necesită doi indicatori în loc de unul.

Cozile de așteptare legate individual sunt ideale pentru aplicațiile cu seturi mari de date și cu puține sau deloc eliminări sau pentru implementarea unei cozi FIFO.

Toate tipurile de structuri de date dublu legate (liste și cozi de coadă) permit în plus:

•
Inserarea unei noi intrări înaintea oricărui element din listă.
•
O(1) eliminarea oricărei intrări din listă.

Cu toate acestea:

•
Fiecare element necesită doi indicatori în loc de unul.

Listele dublu legate sunt cele mai simple dintre structurile de date dublu legate. Acestea adaugă următoarele funcționalități față de cele de mai sus:

•
Acestea pot fi parcurse în sens invers.

Cu toate acestea:

•
Pentru a parcurge în sens invers, trebuie să se precizeze o intrare pentru a începe parcurgerea și lista în care aceasta este conținută.

Cozi de așteptare dublu legate (TAILQ)

Cozile de așteptare adaugă următoarea funcționalitate:

•
Se pot adăuga intrări la sfârșitul unei liste.
•
Acestea pot fi parcurse în sens invers, de la coadă la cap.
•
Acestea pot fi concatenate.

Cu toate acestea:

•
Toate inserările și eliminările din listă trebuie să precizeze capul de listă.
•
Fiecare intrare de cap necesită doi indicatori în loc de unul.

Cozile circulare adaugă următoarele funcționalități față de cele de mai sus:

•
Prima și ultima intrare sunt conectate.

Cu toate acestea:

•
Condiția de încheiere pentru parcurgere este mai complexă.

BSD.

Macrocomenzile <sys/queue.h> au apărut pentru prima dată în 4.4BSD.

Unele BSD-uri oferă SIMPLEQ în loc de STAILQ. Ele sunt identice, dar din motive istorice au fost denumite diferit pe diferite BSD-uri. STAILQ provine de pe FreeBSD, iar SIMPLEQ provine de pe NetBSD. Din motive de compatibilitate, unele sisteme furnizează ambele seturi de macrocomenzi. glibc furnizează atât STAILQ, cât și SIMPLEQ, care sunt identice, cu excepția unui echivalent SIMPLEQ lipsă pentru STAILQ_CONCAT().

circleq(3), insque(3), list(3), slist(3), stailq(3), tailq(3)

Traducerea în limba română a acestui manual a fost făcută de Remus-Gabriel Chelu <remusgabriel.chelu@disroot.org>

Această traducere este documentație gratuită; citiți Licența publică generală GNU Versiunea 3 sau o versiune ulterioară cu privire la condiții privind drepturile de autor. NU se asumă NICIO RESPONSABILITATE.

Dacă găsiți erori în traducerea acestui manual, vă rugăm să trimiteți un e-mail la translation-team-ro@lists.sourceforge.net.

31 octombrie 2023 Pagini de manual de Linux 6.06