c circular queue data structure
Deze tutorial over C ++ Circular Queue-gegevensstructuur legt uit wat circulaire wachtrij is, wat de basisbewerkingen zijn, samen met implementatie en toepassingen:
Een circulaire wachtrij is een uitbreiding van de basiswachtrij die we eerder hebben besproken. Het is ook bekend als 'Ringbuffer'.
Wat is een circulaire wachtrij in C ++?
Een circulaire wachtrij is een lineaire gegevensstructuur die wordt gebruikt om gegevensitems op te slaan. Het voert bewerkingen uit door de FIFO-benadering (First In, First Out) te volgen en de laatste positie in de wachtrij wordt weer verbonden met de eerste positie om een cirkel te vormen.
Zoek hier de volledige C ++-trainingsserie
Wat je leert:
Circulaire wachtrij in C ++
Het volgende diagram toont een cirkelvormige wachtrij.
De bovenstaande afbeelding toont een cirkelvormige datastructuur van grootte 10. De eerste zes elementen staan al in de wachtrij en we zien dat de eerste positie en de laatste positie zijn samengevoegd. Door deze indeling wordt er geen ruimte verspild, zoals in een lineaire wachtrij.
java 8 interviewvragen en antwoorden
In een lineaire wachtrij nadat de wachtrij vol is, verwijderen we de elementen van een ander uiteinde en wordt de status van de wachtrij nog steeds als vol weergegeven en kunnen we niet meer elementen invoegen.
In de cirkelvormige wachtrij, wanneer de wachtrij vol is, en wanneer we elementen van de voorkant verwijderen omdat de laatste en eerste posities zijn verbonden, kunnen we de elementen aan de achterkant invoegen die vrij waren door het element te verwijderen.
In de volgende sectie zullen we leren over de basisbewerkingen van de circulaire wachtrij.
Basisbewerkingen
Enkele van de basisbewerkingen van de circulaire wachtrij zijn als volgt:
Voorkant: Geeft de voorste positie in de ronde wachtrij terug.
Achter: Retourneert de achterste positie in de ronde wachtrij.
In wachtrij plaatsen: Enqueue (waarde) wordt gebruikt om een element in de circulaire wachtrij in te voegen. Het element wordt altijd achteraan in de wachtrij ingevoegd.
We volgen de volgende reeks stappen om een nieuw element in de circulaire wachtrij in te voegen.
# 1) Controleer of de circulaire wachtrij vol is: test ((rear == SIZE-1 && front == 0) || (rear == front-1)), waarbij ‘SIZE’ de grootte van de circulaire wachtrij is.
#twee) Als de circulaire wachtrij vol is, wordt een bericht weergegeven als 'Wachtrij is vol'. Als de wachtrij niet vol is, controleer dan of (achterkant == SIZE - 1 && voorkant! = 0). Als het waar is, stel dan achter = 0 in en voeg element in.
Uitschrijven: Dequeue-functie wordt gebruikt om een element uit de wachtrij te verwijderen. In de circulaire wachtrij wordt het element altijd verwijderd van de frontend. Hieronder wordt de volgorde weergegeven voor het verwijderen van wachtrij in een cirkelvormige wachtrij.
Stappen:
# 1) Controleer of de ronde wachtrij leeg is: controleer of (front == - 1).
populairste tools voor big data-analyse
#twee) Als het leeg is, geeft u het bericht 'Wachtrij is leeg' weer. Als de wachtrij niet leeg is, voer dan stap 3 uit.
# 3) Controleer of (voorkant == achterkant). Als het waar is, stel dan front = rear = -1 in, anders check if (front == size-1), als het waar is, stel dan front = 0 in en retourneer het element.
Illustratie
In dit gedeelte zullen we een gedetailleerde illustratie doornemen van het toevoegen / verwijderen van elementen in de circulaire wachtrij.
Beschouw de volgende cirkelvormige wachtrij van 5 elementen zoals hieronder weergegeven:
Vervolgens voegen we item 1 in de wachtrij in.
Vervolgens voegen we een item in met waarde 3.
Wanneer we de elementen invoegen om een wachtrij vol te maken, ziet de weergave eruit zoals hieronder weergegeven.
Nu verwijderen we de twee elementen, d.w.z. item 1 en item 3 uit de wachtrij, zoals hieronder wordt weergegeven.
Vervolgens voegen we element 11 in of plaatsen het in de wachtrij in de cirkelvormige wachtrij, zoals hieronder weergegeven.
Laten we opnieuw element 13 in de cirkelvormige wachtrij invoegen. De wachtrij ziet er uit zoals hieronder weergegeven.
We zien dat we in de cirkelvormige wachtrij elementen in een cirkel verplaatsen of invoegen. Daarom kunnen we de hele ruimte van de wachtrij gebruiken totdat deze vol raakt.
Implementatie
Laten we de circulaire wachtrij implementeren met C ++.
Uitgang:
Hierboven ziet u de uitvoer van circulaire wachtrijbewerkingen. Eerst voegen we de elementen toe en verwijderen we vervolgens twee elementen. Vervolgens voegen we nog drie elementen in de circulaire wachtrij in of zetten we deze in de wachtrij. We zien dat in tegenstelling tot lineaire wachtrij, de elementen aan het einde van de wachtrij worden toegevoegd.
Implementatie van gekoppelde lijsten
Laten we nu de implementatie van de gekoppelde lijst van een circulaire wachtrij bespreken. Hieronder ziet u de implementatie van de gekoppelde lijst van de circulaire wachtrij in C ++. Merk op dat we struct gebruiken om elk knooppunt weer te geven. De bewerkingen zijn hetzelfde als eerder besproken, behalve dat we ze in dit geval moeten uitvoeren met betrekking tot de gekoppelde lijstknooppunten.
De uitvoer toont de circulaire wachtrij na enqueue-bewerking, dequeue en ook na de tweede enqueue-bewerking.
Uitgang:
De volgende implementatie is een Java-programma om circulaire wachtrij te demonstreren met behulp van de gekoppelde lijst.
Uitgang:
De output van het bovenstaande programma is vergelijkbaar met het vorige programma.
Toepassingen
Laten we enkele toepassingen van de circulaire wachtrij bespreken.
- CPU-planning: Besturingssysteemprocessen waarvoor een bepaalde gebeurtenis moet plaatsvinden of waarbij sommige andere processen moeten worden voltooid voor uitvoering, wordt vaak in een circulaire wachtrij gehouden, zodat ze na elkaar worden uitgevoerd wanneer aan alle voorwaarden is voldaan of wanneer alle gebeurtenissen plaatsvinden.
- Geheugen management: Het gebruik van gewone wachtrijen verspilt geheugenruimte, zoals reeds vermeld in onze bovenstaande bespreking. Het gebruik van een circulaire wachtrij voor geheugenbeheer is gunstig voor een optimaal geheugengebruik.
- Computergestuurd verkeerslichtsysteem: Geautomatiseerde verkeerssignalen worden vaak toegevoegd aan een cirkelvormige wachtrij, zodat ze zichzelf herhalen nadat het opgegeven tijdsinterval is verstreken.
Gevolgtrekking
Cirkelvormige wachtrijen verhelpen het grote nadeel van een normale wachtrij, waarbij we geen elementen kunnen invoegen wanneer de achterste aanwijzer aan het einde van de wachtrij staat, zelfs wanneer we de elementen verwijderen en de ruimte wordt geleegd. In een cirkelvormige rij worden elementen cirkelvormig gerangschikt, zodat er helemaal geen ruimte verloren gaat.
We hebben ook de grote operaties van de circulaire wachtrij gezien. Cirkelvormige wachtrijen zijn vooral handig voor planningsdoeleinden en toepassingen zoals verkeerssignaalsystemen waarbij de seinen om de beurt oplichten.
hoe u het standaard subnetmasker kunt vinden
In onze volgende tutorial zullen we leren over de dubbele wachtrijen die simpelweg 'deque' worden genoemd.
Bezoek hier om C ++ vanaf het begin te leren
Aanbevolen literatuur
- Wachtrijgegevensstructuur in C ++ met illustratie
- Prioriteitswachtrijgegevensstructuur in C ++ met illustratie
- Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Data Mart-zelfstudie - Typen, voorbeelden en implementatie van Data Mart
- Stapel gegevensstructuur in C ++ met illustratie
- Voorbeelden van datamining: meest voorkomende toepassingen van datamining 2021
- Binaire boomgegevensstructuur in C ++
- Prioriteitswachtrij in STL