1. Een wachtrij kan worden gedefinieerd als een geordende lijst die het mogelijk maakt om invoegbewerkingen uit te voeren aan één opgeroepen kant ACHTERKANT en verwijder bewerkingen die moeten worden uitgevoerd aan een ander gebeld eind VOORKANT .
2. De wachtrij wordt de First In First Out-lijst genoemd.
3. Mensen die in de rij staan voor een treinkaartje vormen bijvoorbeeld een wachtrij.
Toepassingen van wachtrij
Vanwege het feit dat de wachtrij acties uitvoert op basis van 'first in first out', wat redelijk eerlijk is voor de volgorde van acties. Er zijn verschillende toepassingen van wachtrijen die hieronder worden besproken.
- Wachtrijen worden veel gebruikt als wachtlijsten voor een enkele gedeelde bron zoals printer, schijf, CPU.
- Wachtrijen worden gebruikt bij asynchrone gegevensoverdracht (waarbij gegevens niet met dezelfde snelheid tussen twee processen worden overgedragen) voor bijvoorbeeld. pijpen, bestand IO, sockets.
- Wachtrijen worden gebruikt als buffers in de meeste toepassingen, zoals MP3-mediaspeler, CD-speler, enz.
- Wachtrijen worden gebruikt om de afspeellijst in mediaspelers bij te houden en nummers aan de afspeellijst toe te voegen of te verwijderen.
- Wachtrijen worden in besturingssystemen gebruikt voor het afhandelen van interrupts.
Complexiteit
| Data structuur | Tijdcomplexiteit | Ruimtecompleetheid | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Gemiddeld | Slechtst | Slechtst | |||||||
| Toegang | Zoekopdracht | Plaatsing | Verwijdering | Toegang | Zoekopdracht | Plaatsing | Verwijdering | ||
| Wachtrij | in) | in) | ik(1) | ik(1) | Op) | Op) | O(1) | O(1) | Op) |