Introduktion
En kø er en samling af varer, hvor det første element tilføjet til listen skal være det første element, der skal fjernes derefter. Så når varer tilføjes til samlingen, vokser den i størrelse, dvs. den vokser i længde. Når et element skal fjernes, skal det være det første, der tilføjes. Hvis genstande fjernes kontinuerligt, er det næste, der fjernes, det andet element; den tredje fjernes bagefter og så videre.
Efter at det første element på den originale liste er blevet fjernet, bliver det andet det første element. Efter at det andet element er blevet fjernet, bliver det tredje det første element osv.
Et godt virkeligt eksempel på en kø 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. Men den kø, der blev talt om i denne vejledning, er softwarekøen, som designet i C ++.
FIFO
FIFO står for First-In, First-Out. Det er en anden måde at værdsætte 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 hovedet eller fronten; slutningen af listen kaldes ryggen eller halen.
Væsentlige operationer
En softwarekø skal mindst have følgende operationer:
skubbe
Denne operation tilføjer et nyt element bagerst i 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øens datastruktur. Du bør kende C ++ - tips og referencer for at forstå resten af denne artikel.
Klasse og genstande
En klasse er et sæt variabler og funktioner, der fungerer sammen, hvor variablerne ikke har værdier tildelt. Når værdierne tildeles variablerne, bliver klassen et objekt. Forskellige værdier givet til den samme klasse resulterer i forskellige objekter; det vil sige, at forskellige objekter er den samme klasse med forskellige værdier. At oprette et objekt fra en klasse siges at være instantiating objektet.
Navnet, køen, er en klasse. Et objekt, der er oprettet fra køklassen, har et programmeret navn.
En funktion, der tilhører 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, der er oprettet (instantieret) fra klassen, har givet forskellige navne af programmereren.
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 navneområde std;
Den første linje er for input/output. Den anden linje er at give programmet mulighed for at bruge alle funktionerne i køklassen. Den tredje linje gør det muligt for programmet at bruge navnene i standardnavneområdet.
Overbelastning af en funktion
Når to eller flere forskellige funktionssignaturer har samme navn, siges det navn at være overbelastet. Når en funktion kaldes, bestemmer antallet og typen af argumenter, hvilken funktion der faktisk udføres.
Konstruktion
kø<type>navn()Den følgende erklæring instantiates en kø navngivet, que af typen int.
kø<int>at;Køen er tom. Erklæringen begynder med det reserverede ord, kø efterfulgt af vinkelparenteser med datatypen. Derefter har du programmørens fornavn til køen.
Konstruerer med initialiseringsliste
Følgende definition viser, hvordan du opretter en kø med initialiseringsliste:
kø<flyde>at({1.1, 2.2, 3.3, 4.4});Ødelægge en kø
Hvis du vil ødelægge en kø, skal du bare lade den gå uden for rækkevidde.
Adgang til køelement
push (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 float -værdier tilføjes bagfra:
kø<flyde>at;at.skubbe(1.1);
at.skubbe(2.2);
at.skubbe(3.3);
at.skubbe(4.4);
at.skubbe(5.5);
størrelse () konst
Dette returnerer antallet af elementer i køen. Følgende kode illustrerer:
kø<flyde>at;at.skubbe(1.1);at.skubbe(2.2);at.skubbe(3.3);at.skubbe(4.4);at.skubbe(5.5);
koste<<at.størrelse() << ' n';
Outputtet er 5.
foran()
Dette returnerer en reference til det første element i køen uden at fjerne elementet. Outputtet af følgende kode er 1.1.
kø<flyde>at;at.skubbe(1.1);at.skubbe(2.2);at.skubbe(3.3);at.skubbe(4.4);at.skubbe(5.5);
koste<<at.foran() << ' n';
Elementet fjernes ikke fra køen.
foran () konst
Når køkonstruktionen går forud for const, udføres udtrykket front () const i stedet for front (). Det bruges f.eks. I følgende kode.
konstkø<flyde>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.foran() << ' n';
En konstant reference returneres. Elementet fjernes ikke fra vektoren. Køelementerne kan ikke ændres.
tilbage()
Dette returnerer en reference til det sidste element i køen uden at fjerne elementet. Outputtet af følgende kode er 5.5.
kø<flyde>at;at.skubbe(1.1);at.skubbe(2.2);at.skubbe(3.3);at.skubbe(4.4);at.skubbe(5.5);
koste<<at.tilbage() << ' n';
tilbage () konst
Når køkonstruktionen går forud for const, udføres udtrykket back () const i stedet for back (). Det bruges f.eks. I følgende kode.
konstkø<flyde>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.tilbage() << ' n';
En konstant reference returneres. Elementet fjernes ikke fra køen. Med den foregående const for køens konstruktion kan elementerne i køen ikke ændres.
Køens kapacitet
størrelse () konst
- se ovenfor
tom () konst
Dette returnerer 1 for true, hvis der ikke er nogen elementer i køen, eller 0 for false, hvis køen er tom. Følgende kode illustrerer dette:
kø<flyde>at1({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at1.tom() << ' n';
kø<flyde>at2;
koste<<at2.tom() << ' 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ø<flyde>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.foran() << ' n';
at.pop();
koste<<at.størrelse() << ' n';
Outputtet er:
1.14
a. bytte (b)
To køer kan byttes, som illustreret i dette kodesegment:
kø<flyde>at1({1.1, 2.2, 3.3, 4.4, 5.5});kø<flyde>at2({10, tyve});
at1.bytte rundt(at2);
koste<< 'Første element og størrelse på que1:
'<<at1.foran() <<','<<at1.størrelse() << ' n';
koste<< 'Første element og størrelse på que2'<<
at2.foran() <<','<<at2.størrelse() << ' 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 udskiftninger, erstattes også af en standardværdi. Datatyperne skal være af samme type.
Lighed og relationelle operatører til køer
For almindelige tegn i C ++, i stigende rækkefølge, kommer tal før store bogstaver, som kommer før små bogstaver. Rumtegnet kommer før nul og dem alle.
Lighedsoperatører
Returnerer 1 for true og 0 for false.
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ø<konst forkælelse*>at1({'venlig', 'noget andet'});kø<konst forkælelse*>at2({'ond'});
intpå en=at1==at2;
koste<<på en<< ' n';
Outputtet er: 0.
! = Operatøren
- modsat af ovenstående. Eksempel:
kø<konst forkælelse*>at1({'venlig', 'noget andet'});kø<konst forkælelse*>at2({'ond'});
intpå en=at1! =at2;
koste<<på en<< ' n';
Outputtet er: 1.
Relationsoperatører
Returnerer 1 for true og 0 for false.
Det
Returnerer 1, hvis den første kø er den første delsæt i den anden kø, idet 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 mod højre, stødes der på 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ø<konst forkælelse*>at1({'venlig', 'noget andet'});kø<konst forkælelse*>at2({'ond'});
intpå en=at1<at2;
koste<<på en<< ' n';
Outputtet er 1. > Operatøren - modsat af ovenstående. Eksempel: Output: 0 Det<= Operator - samme som Output: 1 Operatøren> = - modsat af ovenstående. Eksempel: Output: 0 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: Outputtet er 5. Kølisten kaldes teknisk set en sammenkædet liste. Der er to typer sammenkædede lister for køen: enkeltstående liste og dobbeltkædet liste. Et enkeltstående linkelement kan implementeres af en struktur på to medlemmer. Et medlem holder en markør til det næste element, og det andet element holder datoen (ental for data). Et dobbeltkædet listeelement kan implementeres af en struktur på tre medlemmer. Det midterste element holder datoen, mens det første og tredje element holder pointer til deres tilstødende elementer. Køen er en først-i-først-ud-datastruktur. Der er situationer i computing, når data ankommer i form af en kø, hvilket nødvendiggør først-i-først-ud-adfærd. 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 kræver en kø. Computerudstyr skal af og til afbryde computeren. Afbrydelserne skal håndteres på samme måde, som de ankom. Dette kræver en kø. Køen kan f.eks. Bruges til at administrere applikationsfiler til et job, hvis filerne er gemt på computeren. En kø er en liste datastruktur, som enten er en enkeltstående liste eller en dobbelt-linket 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, adgang til køelementer, køkapacitet, kømodifikatorer og køoverbelastede operatører. Enhver kødatastruktur skal mindst levere push () og pop () medlemsfunktionerne. push () betyder, at sende et nyt element bagerst i køen; og pop () betyder at fjerne elementet, der er foran i køen. Desværre i C ++ returnerer disse funktioner ikke værdien skubbet eller poppet. Så for at kende det sidste element, før du skubber, skal den ekstra back () -funktion bruges; og for at kende det første element, inden du springer, 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øskabeloninstitutionen. Forskellige objekter for klassen bliver til 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
kø<konst forkælelse*>at2({'ond'});
intpå en=at1>at2;
koste<<på en<< ' n';
kø<konst forkælelse*>at2({'ond'});
intpå en=at1<=at2;
koste<<på en<< ' n';
kø<konst forkælelse*>at2({'ond'});
intpå en=at1> =at2;
koste<<på en<< ' n'; Klasse og dens Instantiated Objects
#omfatte
ved hjælp af navneområde std;
klasse TheCla
{
offentlig:
intpå en;
statisk forkælelsekap;
ugyldigfungere(forkælelseingen, konst forkælelse *s)
{
koste<< 'Der er ' <<på en<< 'bøger værd' <<ingen<<s<< ' i butikken.' << ' n';
}
statisk ugyldigsjovt(forkælelsekap)
{
hvis (kap== 'til')
koste<< 'Officiel statisk medlemsfunktion' << ' n';
}
};
intvigtigste()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
kø<TheCla>at;
at.skubbe(obj1);at.skubbe(obj2);at.skubbe(obj3);at.skubbe(obj4);at.skubbe(obj5);
koste<<at.størrelse() << ' n';
Vend tilbage 0;
} Linket liste
Anvendelser af køen
Deling af computerressourcer
Håndtering afbryder
Administrer oplysninger.
Konklusion