Introduktion
En kø er en samling af varer, hvor det første element, der føjes til listen, skal være det første element, der skal fjernes derefter. Så når genstande føjes til samlingen, vokser den i størrelse, dvs.e. den vokser i længde. Hver gang et element skal fjernes, skal det være det første, der tilføjes. Hvis genstande fjernes kontinuerligt, er den næste fjernet den anden genstand; den tredje fjernes bagefter og så videre.
Når det første element på den oprindelige liste er fjernet, bliver det andet det første element. Når det andet element er fjernet, bliver det tredje det første osv.
Et godt eksempel i køen i virkeligheden er, når folk står i kø for at vente på service eller godt. Den første person serveres først før den sidste. Imidlertid er køen, der er omtalt i denne vejledning, softwarekøen, som designet i C++.
FIFO
FIFO står for First-In, First-Out. Det er en anden måde at sætte pris på køen på. Dette betyder, at det første element, der kommer ind på listen, er det første element, der skal fjernes, når fjernelse skal finde sted. Begyndelsen på listen kaldes hoved eller front; slutningen af listen kaldes ryg eller hale.
Væsentlige operationer
En softwarekø skal mindst have følgende handlinger:
skubbe
Denne handling tilføjer et nyt element bag på køen. Denne operation kaldes officielt enqueue.
flytte
Denne handling fjerner det første element i køen, og det andet element bliver det nye første element. Denne operation kaldes officielt dequeue. Det kaldes pop i C++.
Denne artikel forklarer, hvordan du bruger C ++ kø-datastrukturen. Du bør kende C ++ - pointer og referencer for at forstå resten af denne artikel.
Klasse og objekter
En klasse er et sæt variabler og funktioner, der fungerer sammen, hvor variablerne ikke har værdier tildelt. Når værdier tildeles variablerne, bliver klassen et objekt. Forskellige værdier givet til samme klasse resulterer i forskellige objekter; det vil sige, at forskellige objekter er den samme klasse med forskellige værdier. Oprettelse af et objekt fra en klasse siges at instantere objektet.
Navnet, køen, er en klasse. Et objekt oprettet fra køen har et programmørvalgt navn.
En funktion, der hører til en klasse, er nødvendig for at instantiere et objekt fra klassen. I C ++ har denne funktion det samme navn som navnet på klassen. Objekter oprettet (instantieret) fra klassen har forskellige navne givet af programmøren.
At skabe et objekt fra klassen betyder at konstruere objektet; det betyder også instantiating.
Et C ++ - program, der bruger køklassen, starter med følgende linjer øverst i filen:
#omfatte#omfatte
ved hjælp af namespace std;
Den første linje er til input / output. Den anden linje er at lade programmet bruge alle funktionerne i køklassen. Den tredje linje giver programmet mulighed for at bruge navnene i standardnavneområdet.
Overbelastning af en funktion
Når to eller flere forskellige funktionssignaturer har samme navn, siges dette navn at være overbelastet. Når en funktion kaldes, bestemmer antallet og typen af argumenter, hvilken funktion der faktisk udføres.
Konstruktion
køDen følgende erklæring instantierer en kø med navnet, que af typen int.
køKøen er tom. Erklæringen begynder med det reserverede ord, kø efterfulgt af vinkelparenteser med datatypen. Så har du programmøren givet navn til køen.
Konstruktion med initialiseringsliste
Følgende definition viser, hvordan man opretter en kø med initialiseringslisten:
køØdelægger en kø
For at ødelægge en kø skal du bare lade den gå uden for rækkevidden.
Køelementadgang
skub (værdi)
En kø er en First-In-First-Out-liste. Så hver værdi tilføjes bagfra. Følgende kodesegment opretter en tom kø, hvorefter fem floatværdier tilføjes bagfra:
køque.skub (1.1);
que.skub (2.2);
que.skub (3.3);
que.skub (4.4);
que.skub (5.5);
størrelse () konst
Dette returnerer antallet af elementer i køen. Følgende kode illustrerer:
køque.skub (1.1); que.skub (2.2); que.skub (3.3); que.skub (4.4); que.skub (5.5);
cout << que.size() << '\n';
Outputtet er 5.
foran()
Dette returnerer en henvisning til det første element i køen uden at fjerne elementet. Outputtet fra følgende kode er 1.1.
køque.skub (1.1); que.skub (2.2); que.skub (3.3); que.skub (4.4); que.skub (5.5);
cout << que.front() << '\n';
Elementet fjernes ikke fra køen.
front () konst
Når køkonstruktionen er forud for const, udføres udtrykket "front () const" i stedet for "front ()". Det bruges f.eks. I følgende kode.
const køcout << que.front() << '\n';
En konstant reference returneres. Elementet fjernes ikke fra vektoren. Køelementerne kan ikke ændres.
tilbage()
Dette returnerer en henvisning til det sidste element i køen uden at fjerne elementet. Outputtet fra den følgende kode er 5.5.
køque.skub (1.1); que.skub (2.2); que.skub (3.3); que.skub (4.4); que.skub (5.5);
cout << que.back() << '\n';
tilbage () konst
Når køkonstruktionen er forud for const, udføres udtrykket "back () const" i stedet for "back ()". Det bruges f.eks. I følgende kode.
const køcout << que.back() << '\n';
En konstant reference returneres. Elementet fjernes ikke fra køen. Med den foregående konst for køkonstruktionen kan elementerne i køen ikke ændres.
Køkapacitet
størrelse () konst
- se ovenfor
tom () konst
Dette returnerer 1 for sand, hvis der ikke er nogen elementer i køen, eller 0 for falsk, hvis køen er tom. Følgende kode illustrerer dette:
køcout << que1.empty() << '\n';
kø
cout << que2.empty() << '\n';
Outputtet er:
01
Kømodifikatorer
pop ()
En kø er FIFO, så ethvert element, der skal fjernes, skal fjernes fra toppen (hovedet) af køen. Denne medlemsfunktion fjerner det første element uden at returnere det. Følgende kode illustrerer dette:
køcout << que.front() << '\n';
que.pop ();
cout << que.size() << '\n';
Outputtet er:
1.14
-en.bytte (b)
To køer kan byttes som vist i dette kodesegment:
køkø
que1.swap (que2);
cout << "First element and size of que1:
"<< que1.front() <<", "<< que1.size() << '\n';
cout << "First element and size of que2 "<<
que2.foran() <<", "<< que2.size() << '\n';
Outputtet er:
Første element og størrelse på que1: 10, 2
Første element og størrelse på que2: 1.1, 5
Bemærk, at længden af en kø øges, hvis det er nødvendigt. Værdier, der ikke havde erstatninger, erstattes også af en standardværdi. Datatyperne skal være af samme type.
Ligestillings- og relationsoperatører til køer
For almindelige tegn i C ++, i stigende rækkefølge, kommer tallene foran store bogstaver, som kommer før små bogstaver. Rumkarakteren kommer foran nul og dem alle.
Ligestillingsoperatører
Returnerer 1 for sand og 0 for falsk.
== Operatøren
Returnerer 1, hvis de to køer har samme størrelse, og de tilsvarende elementer er ens; Ellers returnerer den 0. Eksempel:
køkø
int num = que1 == que2;
cout << num << '\n';
Outputtet er: 0.
Det != Operatør
- modsat af ovenstående. Eksempel:
køkø
int num = que1 != que2;
cout << num << '\n';
Outputtet er: 1.
Relationelle operatører
Returnerer 1 for sand og 0 for falsk.
Det < Operator
Returnerer 1, hvis den første kø er den indledende delmængde af den anden kø, hvor elementerne i de to lige store dele er de samme og i samme rækkefølge. Hvis begge køer har samme størrelse eller forskellige størrelser og bevæger sig fra venstre til højre, opstår der et element i den første kø, der er mindre end det tilsvarende element i den anden kø, så returneres 1 stadig. Ellers returneres 0. Eksempel:
køkø
int num = que1 < que2;
cout << num << '\n';
Outputtet er 1. < does not include the case when the size and order are the same.
> Operatøren
- modsat af ovenstående. Eksempel:
køkø
int num = que1> que2;
cout << num << '\n';
Output: 0
Det <= Operator
- samme som < but includes the case when the size and order are the same. Example:
køkø
int num = que1 <= que2;
cout << num << '\n';
Output: 1
Operatøren> =
- modsat af ovenstående. Eksempel:
køkø
int num = que1> = que2;
cout << num << '\n';
Output: 0
Klassen og dens øjeblikkelige genstande
En værdi er til en datatype, som et instantieret objekt er for en klasse. Køkonstruktionen kan også acceptere en klasse som datatype. Følgende program illustrerer dette:
#omfatte#omfatte
ved hjælp af namespace std;
klasse TheCla
offentlig:
int num;
statisk char ch;
ugyldig funk (char cha, const char * str)
cout << "There are " << num << " books worth " << cha << str << " in the store." << '\n';
statisk tomrums sjov (char ch)
hvis (ch == 'a')
cout << "Official static member function" << '\n';
;
int main ()
TheCla mod1; TheCla obj2; TheCla obj3; TheCla obj4; TheCla obj5;
kø
que.skub (obj1); que.skub (obj2); que.skub (obj3); que.skub (obj4); que.skub (obj5);
cout << que.size() << '\n';
returnere 0;
Outputtet er 5.
Tilknyttet liste
Kølisten kaldes teknisk en sammenkædet liste. Der er to typer sammenkædede lister til køen: enkeltkædet liste og dobbeltkædet liste.
Et enkelt forbundet linkelement kan implementeres af en struktur af to medlemmer. Et medlem holder en markør til det næste element, og det andet medlem holder datoen (ental for data).
Et dobbeltkoblet listeelement kan implementeres af en struktur på tre medlemmer. Det midterste medlem holder henføringspunktet, mens det første og tredje medlem holder peger på deres tilstødende elementer.
Anvendelser af køen
Køen er en første-i-første-ud-datastruktur. Der er situationer i computing, når data ankommer i form af en kø, der kræver første ind-først ud ud adfærd.
Deling af computerressourcer
En ressource i en computer er enhver fysisk eller virtuel komponent med begrænset tilgængelighed. De inkluderer CPU, grafikkort, harddisk og hukommelse. Deling af en sådan ressource har brug for en kø.
Håndtering af afbrydelser
Computerudstyr skal af og til afbryde computeren. Afbrydelserne skal håndteres på samme måde, som de ankom. Dette har brug for en kø.
Administrer information.
Køen kan f.eks. Bruges til at administrere applikationsfiler til et job, hvis filerne er gemt på computeren.
Konklusion
En kø er en listedatastruktur, som enten er en enkeltkædet liste eller en dobbeltkædet liste. Som regel er det første element, der kommer ind på listen, det første element, der kommer ud. C ++ giver en kø-datastruktur i sit standardbibliotek. Kategorierne af medlemsfunktioner og operatører, der er tilgængelige for denne struktur, er køkonstruktion, køelementadgang, køkapacitet, kømodifikatorer og køoverbelastede operatører.
Enhver kødatastruktur skal mindst omfatte funktionerne push () og pop (). push () betyder, at sende et nyt element bag i køen; og pop () betyder at fjerne elementet, der er forrest i køen. Desværre returnerer disse funktioner i C ++ ikke værdien skubbet eller poppet. Så for at kende det sidste element, før du skubber, skal den ekstra tilbage () funktion bruges; og for at kende det første element inden popping, skal den ekstra front () funktion bruges.
En værdi er til en datatype, som et instantieret objekt er for en klasse. Så en bestemt klasse kan bruges som datatype til kø-skabelon-instantiering. Forskellige objekter for klassen bliver som forskellige værdier for klassen.
Køen har applikationer på computeren. Det kan f.eks. Bruges til at administrere applikationsfiler til et job, hvis filerne er gemt på computeren.
Chrys