Phenquestions
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 naarmate er items aan de collectie worden toegevoegd, groeit deze in omvang, i.e. het groeit in lengte. Telkens wanneer een item moet worden verwijderd, moet het 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 originele 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:
Duwen
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. Het heet pop in C++.
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 van een klasse zou het object instantiëren.
De naam, wachtrij, is een klasse. Een object 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 zijn gemaakt (geïnstantieerd) uit de klasse 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:
#include#include
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 standaard naamruimte 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
wachtrijDe volgende declaratie start een wachtrij met de naam que van het type int.
wachtrijDe 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:
wachtrijEen wachtrij vernietigen
Als u een wachtrij wilt vernietigen, laat u deze 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:
wachtrijvraag.duwen(1.1);
vraag.duwen (2.2);
vraag.duwen (3.3);
vraag.duwen (4.4);
vraag.duwen (5.5);
maat() const
Dit geeft het aantal elementen in de wachtrij terug. De volgende code illustreert:
wachtrijvraag.duwen(1.1); vraag.duwen (2.2); vraag.duwen (3.3); vraag.duwen (4.4); vraag.duwen (5.5);
cout << que.size() << '\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.
wachtrijvraag.duwen(1.1); vraag.duwen (2.2); vraag.duwen (3.3); vraag.duwen (4.4); vraag.duwen (5.5);
cout << que.front() << '\n';
Het element wordt niet uit de wachtrij verwijderd.
front() const
Wanneer de wachtrijconstructie wordt voorafgegaan door const, wordt de uitdrukking "front() const" uitgevoerd in plaats van "front()". Het wordt bijvoorbeeld gebruikt in de volgende code:.
const wachtrijcout << que.front() << '\n';
Er wordt een constante referentie geretourneerd. Het element wordt niet uit de vector verwijderd. De wachtrij-elementen kunnen niet worden gewijzigd.
terug()
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.
wachtrijvraag.duwen(1.1); vraag.duwen (2.2); vraag.duwen (3.3); vraag.duwen (4.4); vraag.duwen (5.5);
cout << que.back() << '\n';
back() cons
Wanneer de wachtrijconstructie wordt voorafgegaan door const, wordt de uitdrukking "back() const" uitgevoerd in plaats van "back()". Het wordt bijvoorbeeld gebruikt in de volgende code:.
const wachtrijcout << que.back() << '\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:
wachtrijcout << que1.empty() << '\n';
wachtrij
cout << que2.empty() << '\n';
De uitvoer is:
01
Wachtrij modifiers
knal()
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:
wachtrijcout << que.front() << '\n';
vraag.knal();
cout << que.size() << '\n';
De uitvoer is:
1.14
een.ruil(b)
Twee wachtrijen kunnen worden verwisseld, zoals geïllustreerd in dit codesegment:
wachtrijwachtrij
que1.swap(que2);
cout << "First element and size of que1:
"<< que1.front() <<", "<< que1.size() << '\n';
cout << "First element and size of que2 "<<
que2.voorkant() <<", "<< que2.size() << '\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 vervanging 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:
wachtrijwachtrij
int num = vraag1 == vraag2;
cout << num << '\n';
De uitvoer is: 0.
De != Operator
- tegenovergestelde van het bovenstaande. Voorbeeld:
wachtrijwachtrij
int num = que1 != vraag2;
cout << num << '\n';
De uitvoer is: 1.
Relationele operators
Retourneert 1 voor waar en 0 voor onwaar.
De < Operator
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 dezelfde of verschillende groottes hebben en van links naar rechts bewegend, wordt een element in de eerste wachtrij aangetroffen dat kleiner is dan het overeenkomstige element in de tweede wachtrij, dan wordt er nog steeds 1 geretourneerd. Anders wordt 0 geretourneerd. Voorbeeld:
wachtrijwachtrij
int num = que1 < que2;
cout << num << '\n';
De uitvoer is 1. < does not include the case when the size and order are the same.
De > Operator
- tegenovergestelde van het bovenstaande. Voorbeeld:
wachtrijwachtrij
int num = que1 > que2;
cout << num << '\n';
Uitgang: 0
De <= Operator
- hetzelfde als < but includes the case when the size and order are the same. Example:
wachtrijwachtrij
int num = que1 <= que2;
cout << num << '\n';
Uitgang: 1
De >= Operator
- tegenovergestelde van het bovenstaande. Voorbeeld:
wachtrijwachtrij
int num = que1 >= que2;
cout << num << '\n';
Uitgang: 0
Klasse en zijn geïnstantieerde objecten
Een waarde is voor een gegevenstype, zoals een geïnstantieerd object voor een klasse is. De wachtrijconstructie kan ook een klasse als een gegevenstype accepteren. Het volgende programma illustreert dit:
#include#include
namespace std; gebruiken;
klasse TheCla
openbaar:
int. aantal;
statisch teken;
void func (char cha, const char *str)
cout << "There are " << num << " books worth " << cha << str << " in the store." << '\n';
statische leegte plezier (char ch)
als (ch == 'a')
cout << "Official static member function" << '\n';
;
int hoofd()
DeCla obj1; DeCla obj2; DeCla obj3; DeCla obj4; DeCla obj5;
wachtrij
vraag.duwen(obj1); vraag.duwen(obj2); vraag.duwen(obj3); vraag.duwen (obj4); vraag.duwen (obj5);
cout << que.size() << '\n';
retourneer 0;
De uitvoer is 5.
Gelinkte lijst
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 de wijzers naar hun aangrenzende elementen bevatten.
Toepassingen van de wachtrij
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.
Computerbronnen delen
Een bron 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.
Onderbrekingen afhandelen
Computerrandapparatuur moet de computer van tijd tot tijd onderbreken. De interrupts moeten op dezelfde manier worden afgehandeld als waarop ze zijn aangekomen. Dit heeft een wachtrij nodig.
Informatie beheren.
De wachtrij kan bijvoorbeeld worden gebruikt om toepassingsbestanden voor een taak te beheren, als de bestanden op de computer zijn opgeslagen.
Conclusie
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 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 functies push() en pop() bevatten. 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 geven deze functies in C++ niet de waarde terug die is gepusht of gepopt. 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 functie extra 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 applicaties op de computer. Het kan bijvoorbeeld worden gebruikt om toepassingsbestanden voor een taak te beheren, als de bestanden op de computer zijn opgeslagen.
Chrys
