De wachtrij kan worden beschreven als een niet-primitieve lineaire gegevensstructuur die de FIFO-volgorde volgt waarin gegevenselementen vanaf het ene uiteinde (achterkant) worden ingevoegd en van het andere uiteinde (voorkant) worden verwijderd. De andere variaties van de wachtrij zijn de wachtrij voor wachtrijen met dubbele rij, wachtrij met dubbele bestemming en prioriteitswachtrij.
Vergelijkingstabel
| Basis voor vergelijking | Lineaire wachtrij | Circulaire wachtrij |
|---|---|---|
| basis- | Organiseert de gegevenselementen en instructies in een volgorde achter elkaar. | Rangschikt de gegevens in het cirkelvormige patroon waarbij het laatste element is verbonden met het eerste element. |
| Volgorde van taakuitvoering | Taken worden uitgevoerd in volgorde waarin ze eerder waren geplaatst (FIFO). | Volgorde van uitvoering van een taak kan veranderen. |
| Invoegen en verwijderen | Het nieuwe element wordt aan de achterkant toegevoegd en van de voorkant verwijderd. | Invoegen en verwijderen kan op elke positie worden gedaan. |
| Prestatie | Inefficiënt | Werkt beter dan de lineaire wachtrij. |
Definitie van lineaire rij
Een lineaire wachtrij is rationeel een primeur in de lijst met eerst uitbestede items. Het is zogenaamd lineair omdat het lijkt op een rechte lijn waarbij de elementen achter elkaar worden geplaatst. Het bevat een homogene verzameling elementen waarin nieuwe elementen aan het ene uiteinde worden toegevoegd en van een ander uiteinde worden verwijderd. Het concept van de wachtrij kan worden begrepen aan de hand van het voorbeeld van een wachtrij van het publiek dat buiten de kassa staat te wachten om het theaterkaartje te bemachtigen. In deze wachtrij voegt de persoon zich bij de achterzijde van de wachtrij om het ticket te nemen en wordt het ticket aan het begin van de wachtrij uitgegeven.
Er zijn verschillende bewerkingen in de wachtrij uitgevoerd
- Eerst wordt de wachtrij geïnitialiseerd naar nul (dus leeg).
- Bepaal of de wachtrij leeg is of niet.
- Bepaal of de wachtrij vol is of niet.
- Insertie van het nieuwe element vanaf het achtereind (Enqueue).
- Verwijderen van het element van de voorkant (wachtstand).
De wachtrij kan op twee manieren worden geïmplementeerd
- Statisch (arrays gebruiken)
- Dynamisch (pointers gebruiken)
De beperking van de lineaire wachtrij is dat hiermee een scenario wordt gemaakt waarin geen nieuw element in de wachtrij kan worden toegevoegd, zelfs als de wachtrij de lege spaties bevat. Deze bovenstaande situatie wordt geïllustreerd in de onderstaande figuur. Hier wijst de achterzijde naar de laatste index terwijl alle vakken nog steeds leeg zijn, er kan geen nieuw element worden toegevoegd.
Definitie van circulaire wachtrij
Een circulaire wachtrij is een variant van de lineaire wachtrij die effectief de beperking van de lineaire wachtrij overwint. In de circulaire wachtrij wordt het nieuwe element toegevoegd aan de eerste positie van de wachtrij als de laatste bezet is en er ruimte beschikbaar is. Als het gaat om een lineaire wachtrij, kan de invoeging alleen vanaf de achterkant worden uitgevoerd en vanaf de voorkant worden verwijderd. In een volledige wachtrij ontstaat na het uitvoeren van een reeks opeenvolgende verwijderingen in de wachtrij een bepaalde situatie waarin geen nieuw element verder kan worden toegevoegd, zelfs als de beschikbare ruimte omdat de underflow-conditie (Achter = max - 1) nog steeds bestaat.
Circulaire wachtrij verbindt de twee uiteinden via een wijzer waar het allereerste element na het laatste element komt. Het houdt ook de voor- en achterkant bij door wat extra logica te implementeren, zodat het de elementen kan traceren die moeten worden ingevoegd en verwijderd. Hiermee genereert de circulaire wachtrij niet de overloopvoorwaarde totdat de wachtrij vol is in feitelijk.
Enkele voorwaarden gevolgd door de circulaire wachtrij:
- Voorkant moet naar het eerste element wijzen.
- De wachtrij is leeg als Front = Rear.
- Wanneer een nieuw element wordt toegevoegd, wordt de wachtrij verhoogd met waarde één (Achter = Achter + 1).
- Wanneer een element uit de wachtrij wordt verwijderd, wordt de voorkant met één opgehoogd (Front = Front + 1).
Belangrijkste verschillen tussen de lineaire wachtrij en de circulaire wachtrij
- De lineaire wachtrij is een geordende lijst waarin gegevenselementen in de volgorde worden gerangschikt. De circulaire wachtrij slaat de gegevens daarentegen circulair op.
- Lineaire wachtrij volgt de FIFO-volgorde voor het uitvoeren van de taak (het element toegevoegd in de eerste positie wordt verwijderd in de eerste positie). Omgekeerd kan in de circulaire wachtrij de volgorde van bewerkingen die op een element worden uitgevoerd, veranderen.
- Het invoegen en verwijderen van de elementen is vastgelegd in een lineaire rij, dat wil zeggen toevoeging vanaf het achtereinde en verwijdering vanaf het vooreinde. Aan de andere kant is de circulaire wachtrij in staat om het element vanaf elk punt in te voegen en te verwijderen totdat het onbewoond is.
- Lineaire wachtrij verspilt de geheugenruimte terwijl circulaire wachtrij efficiënt gebruik van ruimte maakt.
Implementatie van de lineaire wachtrij
Het onderstaande algoritme illustreert de toevoeging van elementen in een wachtrij:
De wachtrij heeft drie gegevensvariabelen nodig, waaronder één array om de wachtrij op te slaan en andere om de begin- en eindpositie van de eerste -1 op te slaan.
insert (item, queue, n, rear) {if (rear == n) print vervolgens "wachtrij-overloop"; else {rear = rear + 1; wachtrij [achterzijde] = item; }} Het onderstaande algoritme illustreert het verwijderen van elementen in een wachtrij:
delete_circular (item, wachtrij, achterzijde, voorkant) {if (achterzijde == voorkant) en print vervolgens "wachtrij underflow"; else {front = front + 1; item = wachtrij [voorzijde]; }} Implementatie van de circulaire wachtrij
Een algoritme om de toevoeging van het element in de circulaire wachtrij te interpreteren:
insert_circular (item, wachtrij, achterkant, voorkant) {rear = (rear + 1) mod n; if (front == rear) print dan "wachtrij is vol"; else {wachtrij [achterzijde] = item; }} Algoritme verklaart de verwijdering van het element in de circulaire wachtrij:
delete_circular (item, wachtrij, achterkant, voorkant) {if (front == rear) en print vervolgens ("wachtrij is leeg"); else {front = front + 1; item = wachtrij [voorzijde]; }} Conclusie
De lineaire wachtrij is inefficiënt in bepaalde gevallen waarbij de elementen moeten worden verplaatst naar de lege ruimten om de invoegbewerking uit te voeren. Dat is de reden dat het de opslagruimte verspilt terwijl de circulaire wachtrij geschikt gebruik maakt van opslagruimte wanneer de elementen op elke positie worden toegevoegd als er een lege ruimte is.
