Invoering
Een wachtrij is een verzameling items, waarbij het eerste item dat aan de lijst wordt toegevoegd, het eerste item moet zijn dat vervolgens moet worden verwijderd. Dus als items aan de collectie worden toegevoegd, groeit deze in omvang, d.w.z. in lengte. Wanneer een item moet worden verwijderd, moet dit het eerste zijn dat wordt toegevoegd. Als items continu worden verwijderd, is de volgende verwijderde het tweede item; de derde wordt daarna verwijderd, enzovoort.
Nadat het eerste item van de oorspronkelijke lijst is verwijderd, wordt het tweede het eerste item. Nadat het tweede item is verwijderd, wordt het derde het eerste item, enzovoort.
Een goed voorbeeld uit de praktijk van een wachtrij is wanneer mensen in de rij gaan staan om te wachten op service of goed. De eerste persoon wordt het eerst geserveerd voor de laatste. De wachtrij waarover in deze tutorial wordt gesproken, is echter de softwarewachtrij, zoals ontworpen in C++.
FIFO
FIFO staat voor First-In, First-Out. Het is een andere manier om de wachtrij te waarderen. Dit betekent dat het eerste item dat in de lijst komt, het eerste item is dat wordt verwijderd, wanneer verwijdering moet plaatsvinden. Het begin van de lijst wordt de kop of voorkant genoemd; het einde van de lijst wordt de achterkant of staart genoemd.
Essentiële handelingen
Een softwarewachtrij moet minimaal de volgende bewerkingen hebben:
duw
Deze bewerking voegt een nieuw element toe aan de achterkant van de wachtrij. Deze operatie heet officieel 'enqueue'.
verschuiving
Deze bewerking verwijdert het eerste element van de wachtrij en het tweede element wordt het nieuwe eerste element. Deze operatie heet officieel dequeue. In C++ heet het pop.
In dit artikel wordt uitgelegd hoe u de C++-wachtrijgegevensstructuur gebruikt. U moet C++-aanwijzingen en -referenties kennen om de rest van dit artikel te begrijpen.
Klasse en objecten
Een klasse is een verzameling variabelen en functies die samenwerken, waarbij aan de variabelen geen waarden zijn toegewezen. Wanneer waarden aan de variabelen worden toegewezen, wordt de klasse een object. Verschillende waarden die aan dezelfde klasse worden gegeven, resulteren in verschillende objecten; dat wil zeggen, verschillende objecten zijn dezelfde klasse met verschillende waarden. Het maken van een object uit een klasse zou het object instantiëren.
De naam, wachtrij, is een klasse. Een object dat is gemaakt op basis van de wachtrijklasse heeft een door de programmeur gekozen naam.
Een functie die bij een klasse hoort, is nodig om een object uit de klasse te instantiëren. In C++ heeft die functie dezelfde naam als de naam van de klasse. Objecten die vanuit de klasse zijn gemaakt (geïnstantieerd) hebben verschillende namen die door de programmeur zijn gegeven.
Een object uit de klasse maken betekent het object construeren; het betekent ook instantiëren.
Een C++-programma dat de wachtrijklasse gebruikt, begint met de volgende regels bovenaan het bestand:
#erbij betrekken#erbij betrekken
namespace std; gebruiken;
De eerste regel is voor invoer/uitvoer. De tweede regel is om het programma alle functies van de wachtrijklasse te laten gebruiken. Met de derde regel kan het programma de namen in de standaardnaamruimte gebruiken.
Een functie overbelasten
Wanneer twee of meer verschillende functiehandtekeningen dezelfde naam hebben, wordt die naam overbelast genoemd. Wanneer een functie wordt aangeroepen, bepalen het aantal en het type argumenten welke functie daadwerkelijk wordt uitgevoerd.
Bouw
rij<type>naam()De volgende declaratie start een wachtrij met de naam que van het type int.
rij<int>Dat;De wachtrij is leeg. De aangifte begint met het gereserveerde woord, wachtrij gevolgd door punthaken met het gegevenstype. Dan heb je de programmeur de naam voor de wachtrij.
Bouwen met initialisatielijst
De volgende definitie laat zien hoe u een wachtrij met initialisatielijst maakt:
rij<vlot>Dat({1.1, 2.2, 3.3, 4.4});Een wachtrij vernietigen
Als u een wachtrij wilt vernietigen, laat u deze gewoon buiten het bereik vallen.
Toegang tot wachtrij-elementen
duwen (waarde)
Een wachtrij is een First-In-First-Out-lijst. Elke waarde wordt dus van achteren toegevoegd. Het volgende codesegment maakt een lege wachtrij aan, waarna vanaf de achterkant vijf float-waarden worden toegevoegd:
rij<vlot>Dat;Dat.duw(1.1);
Dat.duw(2.2);
Dat.duw(3.3);
Dat.duw(4.4);
Dat.duw(5.5);
maat() const
Dit retourneert het aantal elementen in de wachtrij. De volgende code illustreert:
rij<vlot>Dat;Dat.duw(1.1);Dat.duw(2.2);Dat.duw(3.3);Dat.duw(4.4);Dat.duw(5.5);
kosten<<Dat.maat() << 'N';
De uitvoer is 5.
voorkant()
Dit retourneert een verwijzing naar het eerste element van de wachtrij, zonder het element te verwijderen. De uitvoer van de volgende code is 1.1.
rij<vlot>Dat;Dat.duw(1.1);Dat.duw(2.2);Dat.duw(3.3);Dat.duw(4.4);Dat.duw(5.5);
kosten<<Dat.voorkant() << 'N';
Het element wordt niet uit de wachtrij verwijderd.
front() const
Wanneer de wachtrijconstructie wordt voorafgegaan door const, wordt de expressie front() const uitgevoerd in plaats van front(). Het wordt bijvoorbeeld gebruikt in de volgende code.
constrij<vlot>Dat({1.1, 2.2, 3.3, 4.4, 5.5});kosten<<Dat.voorkant() << 'N';
Er wordt een constante referentie geretourneerd. Het element wordt niet uit de vector verwijderd. De wachtrij-elementen kunnen niet worden gewijzigd.
rug()
Dit retourneert een verwijzing naar het laatste element van de wachtrij, zonder het element te verwijderen. De uitvoer van de volgende code is 5.5.
rij<vlot>Dat;Dat.duw(1.1);Dat.duw(2.2);Dat.duw(3.3);Dat.duw(4.4);Dat.duw(5.5);
kosten<<Dat.rug() << 'N';
back() cons
Wanneer de wachtrijconstructie wordt voorafgegaan door const, wordt de expressie back() const uitgevoerd in plaats van back(). Het wordt bijvoorbeeld gebruikt in de volgende code.
constrij<vlot>Dat({1.1, 2.2, 3.3, 4.4, 5.5});kosten<<Dat.rug() << 'N';
Er wordt een constante referentie geretourneerd. Het element wordt niet uit de wachtrij verwijderd. Met de voorgaande cons voor de wachtrijconstructie kunnen de elementen in de wachtrij niet worden gewijzigd.
Wachtrijcapaciteit
maat() const
- zie hierboven
lege() const
Dit retourneert 1 voor waar als er geen elementen in de wachtrij zijn, of 0 voor onwaar als de wachtrij leeg is. De volgende code illustreert dit:
rij<vlot>dat1({1.1, 2.2, 3.3, 4.4, 5.5});kosten<<dat1.leeg() << 'N';
rij<vlot>dat2;
kosten<<dat2.leeg() << 'N';
De uitvoer is:
01
Wachtrij modifiers
pop ()
Een wachtrij is FIFO, dus elk element dat moet worden verwijderd, moet van de bovenkant (kop) van de wachtrij worden verwijderd. Deze lidfunctie verwijdert het eerste element zonder het terug te geven. De volgende code illustreert dit:
rij<vlot>Dat({1.1, 2.2, 3.3, 4.4, 5.5});kosten<<Dat.voorkant() << 'N';
Dat.knal();
kosten<<Dat.maat() << 'N';
De uitvoer is:
1.14
a.swap(b)
Twee wachtrijen kunnen worden verwisseld, zoals geïllustreerd in dit codesegment:
rij<vlot>dat1({1.1, 2.2, 3.3, 4.4, 5.5});rij<vlot>dat2({10, twintig});
dat1.ruil(dat2);
kosten<< 'Eerste element en grootte van que1:
'<<dat1.voorkant() <<','<<dat1.maat() << 'N';
kosten<< 'Eerste element en grootte van que2'<<
dat2.voorkant() <<','<<dat2.maat() << 'N';
De uitvoer is:
Eerste element en grootte van que1: 10, 2
Eerste element en grootte van que2: 1.1, 5
Merk op dat de lengte van een wachtrij indien nodig wordt vergroot. Ook worden waarden die geen vervangingen hadden, vervangen door een standaardwaarde. De gegevenstypen moeten van hetzelfde type zijn.
Gelijkheid en relationele operatoren voor wachtrijen
Voor gewone tekens in C++, in oplopende volgorde, komen cijfers voor hoofdletters, die voor kleine letters komen. Het spatieteken komt voor nul en allemaal.
Gelijkheidsoperatoren
Retourneert 1 voor waar en 0 voor onwaar.
De == Operator
Retourneert 1 als de twee wachtrijen dezelfde grootte hebben en de corresponderende elementen gelijk zijn; anders geeft het 0 terug. Voorbeeld:
rij<const char*>dat1({'vriendelijk', 'iets anders'});rij<const char*>dat2({'slecht'});
intop een=dat1==dat2;
kosten<<op een<< 'N';
De uitvoer is: 0.
De != Operator
- het tegenovergestelde van het bovenstaande. Voorbeeld:
rij<const char*>dat1({'vriendelijk', 'iets anders'});rij<const char*>dat2({'slecht'});
intop een=dat1! =dat2;
kosten<<op een<< 'N';
De uitvoer is: 1.
Relationele operators
Retourneert 1 voor waar en 0 voor onwaar.
De
Retourneert 1 als de eerste wachtrij de initiële subset is van de tweede wachtrij, waarbij de elementen van de twee gelijke delen hetzelfde en in dezelfde volgorde zijn. Als beide wachtrijen even groot of verschillend zijn, en van links naar rechts bewegend, wordt in de eerste wachtrij een element aangetroffen dat kleiner is dan het overeenkomstige element in de tweede wachtrij, dan wordt er nog steeds 1 geretourneerd. Anders wordt 0 geretourneerd. Voorbeeld:
rij<const char*>dat1({'vriendelijk', 'iets anders'});rij<const char*>dat2({'slecht'});
intop een=dat1<dat2;
kosten<<op een<< 'N';
De uitvoer is 1. De > Operator - het tegenovergestelde van het bovenstaande. Voorbeeld: Uitgang: 0 De<= Operator - hetzelfde als Uitgang: 1 De >= Operator - het tegenovergestelde van het bovenstaande. Voorbeeld: Uitgang: 0 Een waarde is voor een gegevenstype, zoals een geïnstantieerd object voor een klasse is. De wachtrijconstructie kan ook een klasse als gegevenstype accepteren. Het volgende programma illustreert dit: De uitvoer is 5. De wachtrijlijst wordt technisch gezien een gekoppelde lijst genoemd. Er zijn twee soorten gekoppelde lijsten voor de wachtrij: enkelvoudig gekoppelde lijst en dubbel gekoppelde lijst. Een enkelvoudig gekoppeld lijstelement kan worden geïmplementeerd door een struct van twee leden. Eén lid houdt een aanwijzer naar het volgende element en het andere lid houdt de datum vast (enkelvoud voor gegevens). Een dubbel gekoppeld lijstelement kan worden geïmplementeerd door een struct van drie leden. Het middelste lid houdt het nulpunt vast, terwijl het eerste en derde lid wijzers naar hun aangrenzende elementen bevatten. De wachtrij is een first-in-first-out datastructuur. Er zijn situaties in de informatica waarin gegevens binnenkomen in de vorm van een wachtrij, waardoor first-in-first-out-gedrag nodig is. Een resource op een computer is een fysiek of virtueel onderdeel van beperkte beschikbaarheid. Ze omvatten de CPU, videokaart, harde schijf en geheugen. Het delen van een dergelijke bron heeft een wachtrij nodig. Computerrandapparatuur moet de computer van tijd tot tijd onderbreken. De interrupts moeten op dezelfde manier worden afgehandeld als dat ze zijn aangekomen. Dit heeft een wachtrij nodig. De wachtrij kan bijvoorbeeld worden gebruikt om toepassingsbestanden voor een taak te beheren, als de bestanden op de computer zijn opgeslagen. Een wachtrij is een lijstgegevensstructuur, die ofwel een enkelvoudig gekoppelde lijst of een dubbelgekoppelde lijst is. In de regel is het eerste element dat in de lijst komt, het eerste dat eruit komt. C++ biedt een wachtrijgegevensstructuur in zijn standaardbibliotheek. De categorieën van lidfuncties en operators die beschikbaar zijn voor deze structuur zijn wachtrijconstructie, toegang tot wachtrij-elementen, wachtrijcapaciteit, wachtrijmodificatoren en overbelaste wachtrijen. Elke wachtrijgegevensstructuur moet ten minste de lidfuncties push() en pop() bieden. push() betekent, het verzenden van een nieuw element achter in de wachtrij; en pop() betekent het verwijderen van het element dat vooraan in de wachtrij staat. Helaas retourneren deze functies in C ++ niet de waarde die is gepusht of gepoft. Dus, om het laatste element te kennen voordat je drukt, moet de extra back()-functie worden gebruikt; en om het eerste element te kennen voordat het wordt gepopt, moet de extra functie front() worden gebruikt. Een waarde is voor een gegevenstype, zoals een geïnstantieerd object voor een klasse is. Een bepaalde klasse kan dus worden gebruikt als een gegevenstype voor de instantie van de wachtrijsjabloon. Verschillende objecten voor de klasse worden als verschillende waarden voor de klasse. De wachtrij heeft toepassingen op de computer. Het kan bijvoorbeeld worden gebruikt om toepassingsbestanden voor een taak te beheren, als de bestanden op de computer zijn opgeslagen. Chrys
rij<const char*>dat2({'slecht'});
intop een=dat1>dat2;
kosten<<op een<< 'N';
rij<const char*>dat2({'slecht'});
intop een=dat1<=dat2;
kosten<<op een<< 'N';
rij<const char*>dat2({'slecht'});
intop een=dat1> =dat2;
kosten<<op een<< 'N'; Klasse en zijn geïnstantieerde objecten
#erbij betrekken
namespace std; gebruiken;
klasse TheCla
{
openbaar:
intop een;
statisch charch;
leegtefunctie(charNee, const char *P)
{
kosten<< 'Er zijn ' <<op een<< 'boeken waard' <<Nee<<P<< ' in de winkel.' << 'N';
}
statisch leegteplezier(charch)
{
indien (ch== 'tot')
kosten<< 'Officiële statische ledenfunctie' << 'N';
}
};
inthoofd()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
rij<De Cla>Dat;
Dat.duw(obj1);Dat.duw(obj2);Dat.duw(obj3);Dat.duw(obj4);Dat.duw(obj5);
kosten<<Dat.maat() << 'N';
opbrengst 0;
} Gelinkte lijst
Toepassingen van de wachtrij
Computerbronnen delen
Onderbrekingen afhandelen
Beheer informatie.
Conclusie