In de informatica is een wachtrij een lineaire datastructuur waarbij de componenten aan het ene uiteinde worden geplaatst en aan het andere uiteinde worden verwijderd volgens het 'first-in, first-out' (FIFO)-principe. Deze datastructuur kan worden gebruikt voor het besturen van een actiereeks of het opslaan van gegevens. C is een computertaal met wachtrijmogelijkheden in de vorm van arrays of gekoppelde lijsten.
Kenmerken:
- Een wachtrij is een soort lineaire gegevensstructuur die kan worden opgebouwd met een array of een gekoppelde lijst.
- Elementen worden naar de achterkant van de wachtrij verplaatst terwijl ze aan de voorkant worden verwijderd.
- Enqueue (een element aan de achterkant toevoegen) en dequeue (een element aan de voorkant verwijderen) zijn twee wachtrijbewerkingen.
- Wanneer elementen vaak worden toegevoegd en verwijderd, kan een wachtrij als een cirkelvormige wachtrij worden gebouwd om verspilling van geheugen te voorkomen.
Array gebruiken:
Om een wachtrij in C te implementeren met behulp van een array, definieert u eerst de maximale grootte van de wachtrij en declareert u een array van die grootte. De gehele getallen voor en achter zijn respectievelijk ingesteld op 1. De variabele front vertegenwoordigt het voorste element van de wachtrij en de variabele back vertegenwoordigt het element back.
Voordat we het nieuwe element naar de eindpositie van de wachtrij duwen, moeten we de back-variabele met 1 verhogen. De wachtrij is nu vol en er kunnen geen andere extra elementen worden toegevoegd wanneer de back-positie de maximale capaciteit van de wachtrij bereikt. We voegen een element toe aan de voorkant van de wachtrij en verhogen de frontvariabele met slechts één om een element uit de wachtrij te verwijderen. Als de voor- en achterposities gelijk zijn en er geen componenten meer kunnen worden verwijderd, kunnen we zeggen dat de wachtrij leeg is.
tostring-methode in Java
Hieronder ziet u een voorbeeld van een wachtrij geschreven in C die gebruik maakt van een array:
C-programmeertaal:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } De uitvoer van de code zal zijn:
Uitgang:
selecteer meerdere tabellen sql
10 20 30 Queue is empty-1
Uitleg:
- Eerst plaatsen we drie elementen 10, 20 en 30 in de wachtrij.
- Vervolgens halen we het voorste element van de wachtrij, dat is 10, uit de wachtrij en drukken het af.
- Vervolgens halen we het voorste element van de wachtrij uit de wachtrij en drukken het opnieuw af, namelijk 20.
- Vervolgens halen we de wachtrij eruit en drukken we het voorste element van de wachtrij opnieuw af, namelijk 30.
- Ten slotte maken we een dequeue van een lege wachtrij die 'Wachtrij is leeg' als resultaat geeft en -1 retourneert.
Gekoppelde lijst gebruiken:
Een andere alternatieve benadering voor het construeren van een wachtrij in de programmeertaal C is het gebruik van een gekoppelde lijst. Elk van de knooppunten in de wachtrij wordt met deze methode uitgedrukt door een knooppunt dat de elementwaarde bevat en een verwijzing naar het volgende knooppunt in de wachtrij. Om respectievelijk de eerste en laatste knooppunten in de wachtrij bij te houden, worden voor- en achteraanwijzers gebruikt.
We vestigen een nieuw knooppunt met de elementwaarde en stellen de volgende pointer in op NULL om een element aan de wachtrij toe te voegen. Naar het nieuwe knooppunt plaatsen we de voor- en achteraanwijzers als de wachtrij leeg is. Als dat niet het geval is, werken we de achterste aanwijzer bij en stellen we de volgende aanwijzer van het oude achterste knooppunt zo in dat deze naar het nieuwe knooppunt wijst.
Wanneer u een knooppunt uit een wachtrij verwijdert, wordt eerst het voorgaande knooppunt verwijderd, vervolgens wordt de voorste aanwijzer bijgewerkt naar het volgende knooppunt in de wachtrij, en ten slotte wordt het geheugen vrijgegeven dat het verwijderde knooppunt in beslag nam. Als de vooraanwijzer na verwijdering NULL is, is de wachtrij leeg.
regressie-expressie in Java
Hier is een voorbeeld van een wachtrij geïmplementeerd in C met behulp van een gekoppelde lijst:
C-programmeertaal:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } De uitvoer van de code zal zijn:
Uitgang:
10 20 30 Queue is empty-1
Uitleg:
- Eerst plaatsen we drie elementen 10, 20 en 30 in de wachtrij.
- Vervolgens halen we het voorste element van de wachtrij, dat is 10, uit de wachtrij en drukken het af.
- Vervolgens halen we het voorste element van de wachtrij uit de wachtrij en drukken het opnieuw af, namelijk 20.
- Vervolgens halen we de wachtrij eruit en drukken we het voorste element van de wachtrij opnieuw af, namelijk 30.
- Ten slotte proberen we uit de lege wachtrij te komen, waardoor het bericht 'Wachtrij is leeg' wordt afgedrukt en -1 wordt geretourneerd.
Voordelen:
- Wachtrijen zijn met name handig voor het implementeren van algoritmen waarbij elementen in een precieze volgorde moeten worden verwerkt, zoals zoeken in de breedte en taakplanning.
- Omdat wachtrijbewerkingen een tijdcomplexiteit van O(1) hebben, kunnen ze snel worden uitgevoerd, zelfs bij enorme wachtrijen.
- Wachtrijen zijn bijzonder flexibel omdat ze eenvoudig kunnen worden geïmplementeerd met behulp van een array of een gekoppelde lijst.
Nadelen:
- Een wachtrij kan, in tegenstelling tot een stapel, niet met één enkele aanwijzer worden geconstrueerd, waardoor wachtrij-implementatie iets ingewikkelder wordt.
- Als de wachtrij is opgebouwd als een array, kan deze snel vol raken als er te veel elementen worden toegevoegd, wat kan leiden tot prestatieproblemen of mogelijk een crash.
- Wanneer u een gekoppelde lijst gebruikt om de wachtrij te implementeren, kan de geheugenoverhead van elk knooppunt aanzienlijk zijn, vooral voor kleine elementen.
Conclusie:
Toepassingen die gebruik maken van wachtrijen, een cruciale datastructuur, omvatten besturingssystemen, netwerken en games, om er maar een paar te noemen. Ze zijn ideaal voor algoritmen die elementen in een bepaalde volgorde moeten verwerken, omdat ze eenvoudig te maken zijn met behulp van een array of een gekoppelde lijst. Wachtrijen hebben echter nadelen waarmee rekening moet worden gehouden bij het selecteren van een gegevensstructuur voor een bepaalde toepassing, zoals geheugengebruik en complexiteit van de implementatie.