Wachtrijgegevensstructuur in C ++ met illustratie

queue data structure c with illustration

Een korte inleiding tot wachtrij in C ++ met illustratie.

De wachtrij is een basisgegevensstructuur, net als een stapel. In tegenstelling tot stack die de LIFO-benadering gebruikt, gebruikt wachtrij de FIFO-benadering (first in, first out). Met deze aanpak is het eerste item dat aan de wachtrij wordt toegevoegd, het eerste item dat uit de wachtrij wordt verwijderd. Net als Stack is ook de wachtrij een lineaire datastructuur.

snel sorteerprogramma in c ++

In een real-world analogie kunnen we ons een buswachtrij voorstellen waar de passagiers in een rij of een rij op de bus wachten. De eerste passagier in de rij gaat als eerste de bus in, want die passagier was toevallig degene die het eerst was gekomen.

​ Lees hier de populaire C ++ trainingsserie.

Wat je leert:

• Wachtrij in C ++
  • Basisbewerkingen
    • In de wachtrij zetten
    • Uitschrijven
  • Illustratie
  • Matrix-implementatie voor wachtrij
  • Stack Vs. Wachtrij
  • Toepassingen van wachtrij
  • Gevolgtrekking
  • Aanbevolen literatuur

Wachtrij in C ++

In softwaretermen kan de wachtrij worden gezien als een set of verzameling elementen, zoals hieronder wordt weergegeven. De elementen zijn lineair gerangschikt.

We hebben twee uiteinden, namelijk 'voorkant' en 'achterkant' van de wachtrij. Als de wachtrij leeg is, worden beide pointers op -1 gezet.

De 'achterste' aanwijzer is de plaats van waaruit de elementen in de wachtrij worden geplaatst. De bewerking van het toevoegen / invoegen van elementen in de wachtrij wordt 'enqueue' genoemd.

De 'front-end pointer' is de plaats waar de elementen uit de wachtrij worden verwijderd. De bewerking om elementen uit de wachtrij te verwijderen / verwijderen, wordt 'dequeue' genoemd.

Als de waarde van de achterste pointer size-1 is, zeggen we dat de wachtrij vol is. Als de voorkant nul is, is de wachtrij leeg.

Basisbewerkingen

De gegevensstructuur van de wachtrij omvat de volgende bewerkingen:

• EnQueue: Voegt een item toe aan de wachtrij. Het toevoegen van een item aan de wachtrij gebeurt altijd achterin de wachtrij.
• DeQueue: Verwijdert een item uit de wachtrij. Een item wordt altijd vooraan in de wachtrij verwijderd of uit de wachtrij gehaald.
• is leeg: Controleert of de wachtrij leeg is.
• is vol: Controleert of de wachtrij vol is.
• kijkje: Haalt een element vooraan in de wachtrij zonder het te verwijderen.

In de wachtrij zetten

In dit proces worden de volgende stappen uitgevoerd:

• Controleer of de wachtrij vol is.
• Indien vol, produceer een overloopfout en sluit af.
• Anders verhoog je de ‘achterkant’.
• Voeg een element toe aan de locatie aangeduid met ‘achterzijde’.
• Succes teruggeven.

Uitschrijven

De wachtrijbewerking bestaat uit de volgende stappen:

• Controleer of de wachtrij leeg is.
• Indien leeg, toon een underflow-fout en sluit af.
• Anders wordt het toegangselement aangeduid met ‘voorkant’.
• Verhoog de ‘voorkant’ om naar de volgende toegankelijke gegevens te verwijzen.
• Succes teruggeven.

Vervolgens zullen we een gedetailleerde illustratie zien van invoeg- en verwijderingsbewerkingen in de wachtrij.

Illustratie

Dit is een lege wachtrij en dus hebben we achteraan en leeg ingesteld op -1.

Vervolgens voegen we 1 toe aan de wachtrij en als resultaat beweegt de achterste aanwijzer één locatie vooruit.

In de volgende afbeelding voegen we element 2 toe aan de wachtrij door de achterste aanwijzer nog een stap vooruit te verplaatsen.

In de volgende afbeelding voegen we element 3 toe en verplaatsen we de achterste aanwijzer met 1.

Op dit punt heeft de achterste aanwijzer waarde 2 terwijl de voorste aanwijzer op 0 staat^thplaats.

Vervolgens verwijderen we het element dat wordt aangeduid door de voorste aanwijzer. Omdat de voorste aanwijzer op 0 staat, is het element dat wordt verwijderd 1.

Dus het eerste element dat in de wachtrij is ingevoerd, d.w.z. 1 is toevallig het eerste element dat uit de wachtrij is verwijderd. Als gevolg hiervan wordt de voorste aanwijzer nu na de eerste wachtrij naar voren verplaatst naar de volgende locatie, namelijk 1.

Matrix-implementatie voor wachtrij

Laten we de datastructuur van de wachtrij implementeren met C ++.

Uitgang:

Wachtrij is leeg !!
Wachtrij gemaakt:
10 20 30 40 50
Wachtrij is vol !!
Voorkant = 0
Wachtrij-elementen: 10 20 30 40 50
Achter = 4

Verwijderd => 10 uit myqueue
Voorkant = 1
Wachtrij-elementen: 20 30 40 50
Achter = 4

De bovenstaande implementatie toont de wachtrij weergegeven als een array. We specificeren de max_size voor de array. We definiëren ook de bewerkingen voor enqueue en dequeue, evenals de bewerkingen isFull en isEmpty.

Hieronder wordt de Java-implementatie van de wachtrijgegevensstructuur weergegeven.

Uitgang:

Wachtrij gemaakt als:
10 20 30 40
Element 10 uit wachtrij gehaald

Voorzijde is 20
Achterste item is 40

De bovenstaande implementatie is vergelijkbaar met de C ++ -implementatie.

Laten we vervolgens de wachtrij in C ++ implementeren met behulp van een gekoppelde lijst.

Implementatie van gekoppelde lijst voor wachtrij:

Uitgang:

Wachtrij aangemaakt:
10 20 30 40 50
Element verwijderd uit wachtrij is: 10
Wachtrij na één verwijdering:
20 30 40 50

beste opruimtool voor Windows 10

Stack Vs. Wachtrij

Stapels en wachtrijen zijn secundaire gegevensstructuren die kunnen worden gebruikt om gegevens op te slaan. Ze kunnen worden geprogrammeerd met behulp van de primaire datastructuren zoals arrays en gekoppelde lijsten. Nadat we beide datastructuren in detail hebben besproken, is het tijd om de belangrijkste verschillen tussen deze twee datastructuren te bespreken.

Toepassingen van wachtrij

Laten we de verschillende toepassingen van de wachtrij-datastructuur hieronder bespreken.

• De datastructuur van de wachtrij wordt gebruikt in verschillende CPU- en schijfplanning. Hier hebben we meerdere taken die tegelijkertijd een CPU of schijf vereisen. De CPU- of schijftijd wordt voor elke taak gepland met behulp van een wachtrij.
• De wachtrij kan ook worden gebruikt voor print spooling waarbij het aantal printopdrachten in een wachtrij wordt geplaatst.
• Het afhandelen van interrupts in real-time systemen gebeurt met behulp van een wachtrij datastructuur. De interrupts worden afgehandeld in de volgorde waarin ze binnenkomen.
• Breedte-eerste zoekactie waarbij de aangrenzende knooppunten van een boom worden doorlopen voordat naar het volgende niveau wordt gegaan, gebruikt een wachtrij voor implementatie.
• Telefoonsystemen van callcenters gebruiken wachtrijen om de oproepen vast te houden totdat ze worden beantwoord door de servicemedewerkers.

Over het algemeen kunnen we zeggen dat de datastructuur van de wachtrij wordt gebruikt wanneer we de resources of items nodig hebben om te worden onderhouden in de volgorde waarin ze aankomen, d.w.z. First in, First Out.

Gevolgtrekking

De wachtrij is een FIFO-gegevensstructuur (First In, First Out) die meestal wordt gebruikt in resources waar planning vereist is. Het heeft twee wijzers aan de achterkant en voorkant aan twee uiteinden en deze worden gebruikt om respectievelijk een element in te voeren en een element van / naar de wachtrij te verwijderen.

In onze volgende tutorial zullen we meer te weten komen over enkele uitbreidingen van de wachtrij, zoals prioriteitswachtrij en circulaire wachtrij.

​ Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.

Aanbevolen literatuur

• Prioritaire wachtrijgegevensstructuur in C ++ met illustratie
• Prioriteitswachtrij in STL
• Stapel gegevensstructuur in C ++ met illustratie
• Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Inleiding tot gegevensstructuren in C ++
• Parametrering van JMeter-gegevens met behulp van door de gebruiker gedefinieerde variabelen