Introduksjon
En kø er en samling av elementer, der det første elementet som er lagt til i listen, må være det første elementet som skal fjernes neste. Så når varer legges til i samlingen, vokser den i størrelse, det vil si at den vokser i lengde. Når et element skal fjernes, må det være det første som er lagt til. Hvis elementene fjernes kontinuerlig, er det neste som er fjernet, det andre elementet; den tredje fjernes etterpå, og så videre.
Etter at det første elementet i den opprinnelige listen er fjernet, blir det andre det første elementet. Etter at det andre elementet er fjernet, blir det tredje det første elementet, og så videre.
Et godt eksempel på en kø i virkeligheten er når folk står i kø for å vente på service eller god. Den første personen serveres først før den siste. Imidlertid er køen det snakkes om i denne opplæringen, programvarekøen, som designet i C ++.
FIFO
FIFO står for First-In, First-Out. Det er en annen måte å sette pris på køen. Dette betyr at det første elementet som kommer inn på listen, er det første elementet som skal fjernes når fjerning skal finne sted. Begynnelsen på listen kalles hode eller front; slutten av listen kalles ryggen eller halen.
Viktige operasjoner
En programvarekø må ha minst følgende operasjoner:
trykk
Denne operasjonen legger til et nytt element på baksiden av køen. Denne operasjonen kalles offisielt, enqueue.
skifte
Denne operasjonen fjerner det første elementet i køen, og det andre elementet blir det nye første elementet. Denne operasjonen kalles offisielt dequeue. Det kalles pop i C ++.
Denne artikkelen forklarer hvordan du bruker C ++ - køstrukturen. Du bør kjenne til C ++ - tips og referanser for å forstå resten av denne artikkelen.
Klasse og objekter
En klasse er et sett med variabler og funksjoner som fungerer sammen, der variablene ikke har verdier som er tilordnet. Når verdier er tilordnet variablene, blir klassen et objekt. Ulike verdier gitt til samme klasse resulterer i forskjellige objekter; det vil si at forskjellige objekter er samme klasse med forskjellige verdier. Det sies å lage et objekt fra en klasse for å instantere objektet.
Navnet, køen, er en klasse. Et objekt som er opprettet fra køklassen, har et valgt programmeringsnavn.
En funksjon som tilhører en klasse er nødvendig for å instantiere et objekt fra klassen. I C ++ har den funksjonen samme navn som navnet på klassen. Objekter som er opprettet (instantiert) fra klassen har forskjellige navn gitt dem av programmereren.
Å lage et objekt fra klassen betyr å konstruere objektet; det betyr også instantiating.
Et C ++ - program som bruker køklassen, starter med følgende linjer øverst i filen:
#inkludere#inkludere
ved hjelp av navneområde std;
Den første linjen er for input/output. Den andre linjen er å la programmet bruke alle funksjonene i køklassen. Den tredje linjen lar programmet bruke navnene i standardnavnområdet.
Overbelastning av en funksjon
Når to eller flere forskjellige funksjonssignaturer har samme navn, sies det at navnet er overbelastet. Når en funksjon kalles, bestemmer antallet og typen argumenter hvilken funksjon som faktisk utføres.
Konstruksjon
kø<type>Navn()Følgende deklarasjon instantierer en kø med navn, que av typen int.
kø<int>at;Køen er tom. Erklæringen begynner med det reserverte ordet, kø etterfulgt av vinkelparenteser med datatypen. Deretter har du programmeringsnavn for køen.
Konstruerer med initialiseringsliste
Følgende definisjon viser hvordan du oppretter en kø med initialiseringsliste:
kø<flyte>at({1.1, 2.2, 3.3, 4.4});Ødelegger en kø
For å ødelegge en kø, bare la den gå utenfor rekkevidden.
Tilgang til køelement
push (verdi)
En kø er en First-In-First-Out-liste. Så hver verdi legges til bakfra. Følgende kodesegment oppretter en tom kø, hvoretter fem flyteverdier legges til bakfra:
kø<flyte>at;at.trykk(1.1);
at.trykk(2.2);
at.trykk(3.3);
at.trykk(4.4);
at.trykk(5.5);
størrelse () konst
Dette returnerer antall elementer i køen. Følgende kode illustrerer:
kø<flyte>at;at.trykk(1.1);at.trykk(2.2);at.trykk(3.3);at.trykk(4.4);at.trykk(5.5);
koste<<at.størrelse() << ' n';
Utgangen er 5.
front()
Dette returnerer en referanse til det første elementet i køen, uten å fjerne elementet. Utdataene fra følgende kode er 1.1.
kø<flyte>at;at.trykk(1.1);at.trykk(2.2);at.trykk(3.3);at.trykk(4.4);at.trykk(5.5);
koste<<at.front() << ' n';
Elementet fjernes ikke fra køen.
foran () konst
Når køkonstruksjonen går foran const, utføres uttrykket front () const i stedet for front (). Den brukes for eksempel i følgende kode.
konstkø<flyte>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.front() << ' n';
En konstant referanse returneres. Elementet er ikke fjernet fra vektoren. Køelementene kan ikke endres.
tilbake()
Dette returnerer en referanse til det siste elementet i køen, uten å fjerne elementet. Utdataene fra følgende kode er 5.5.
kø<flyte>at;at.trykk(1.1);at.trykk(2.2);at.trykk(3.3);at.trykk(4.4);at.trykk(5.5);
koste<<at.tilbake() << ' n';
tilbake () konst
Når køkonstruksjonen går foran const, utføres uttrykket back () const i stedet for back (). Den brukes for eksempel i følgende kode.
konstkø<flyte>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.tilbake() << ' n';
En konstant referanse returneres. Elementet fjernes ikke fra køen. Med den foregående const for køkonstruksjonen kan ikke elementene i køen endres.
Køkapasitet
størrelse () konst
- se ovenfor
tom () konst
Dette returnerer 1 for true hvis det ikke er noen elementer i køen, eller 0 for false hvis køen er tom. Følgende kode illustrerer dette:
kø<flyte>at1({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at1.tømme() << ' n';
kø<flyte>at2;
koste<<at2.tømme() << ' n';
Utgangen er:
01
Kømodifikatorer
pop ()
En kø er FIFO, så alle elementer som må fjernes må fjernes fra toppen (hodet) av køen. Denne medlemsfunksjonen fjerner det første elementet uten å returnere det. Følgende kode illustrerer dette:
kø<flyte>at({1.1, 2.2, 3.3, 4.4, 5.5});koste<<at.front() << ' n';
at.pop();
koste<<at.størrelse() << ' n';
Utgangen er:
1.14
a. bytte (b)
To køer kan byttes, som vist i dette kodesegmentet:
kø<flyte>at1({1.1, 2.2, 3.3, 4.4, 5.5});kø<flyte>at2({10, tjue});
at1.bytte(at2);
koste<< 'Første element og størrelse på que1:
'<<at1.front() <<','<<at1.størrelse() << ' n';
koste<< 'Første element og størrelse på que2'<<
at2.front() <<','<<at2.størrelse() << ' n';
Utgangen er:
Første element og størrelse på que1: 10, 2
Første element og størrelse på que2: 1.1, 5
Vær oppmerksom på at lengden på en kø blir økt om nødvendig. Verdier som ikke hadde erstatninger, erstattes også av en standardverdi. Datatypene må være av samme type.
Likestillings- og relasjonsoperatører for køer
For vanlige tegn i C ++, i stigende rekkefølge, kommer tall før store bokstaver, som kommer før små bokstaver. Romtegnet kommer foran null og alle sammen.
Likestillingsoperatører
Returnerer 1 for true og 0 for false.
== Operatøren
Returnerer 1 hvis de to køene har samme størrelse og de tilsvarende elementene er like; ellers returnerer det 0. Eksempel:
kø<konst røye*>at1({'snill', 'noe annet'});kø<konst røye*>at2({'ond'});
intpå en=at1==at2;
koste<<på en<< ' n';
Utgangen er: 0.
! = Operatøren
- motsatt av det ovennevnte. Eksempel:
kø<konst røye*>at1({'snill', 'noe annet'});kø<konst røye*>at2({'ond'});
intpå en=at1! =at2;
koste<<på en<< ' n';
Utgangen er: 1.
Relasjonelle operatører
Returnerer 1 for true og 0 for false.
De
Returnerer 1 hvis den første køen er det første delsettet til den andre køen, med elementene i de to like delene som er like og i samme rekkefølge. Hvis begge køene er av samme størrelse eller forskjellige størrelser, og beveger seg fra venstre til høyre, vil et element oppstå i den første køen som er mindre enn det tilsvarende elementet i den andre køen, så vil 1 fortsatt bli returnert. Ellers returneres 0. Eksempel:
kø<konst røye*>at1({'snill', 'noe annet'});kø<konst røye*>at2({'ond'});
intpå en=at1<at2;
koste<<på en<< ' n';
Utgangen er 1. Operatøren - motsatt av det ovennevnte. Eksempel: Utgang: 0 De<= Operator - samme som Utgang: 1 Operatøren> = - motsatt av det ovennevnte. Eksempel: Utgang: 0 En verdi er til en datatype, slik et instantiert objekt er for en klasse. Køkonstruksjonen kan også godta en klasse som datatype. Følgende program illustrerer dette: Utgangen er 5. Kølisten kalles teknisk en koblet liste. Det er to typer koblede lister for køen: enkeltkoblet liste og dobbeltkoblet liste. Et enkelt koblet listeelement kan implementeres av en struktur på to medlemmer. Ett medlem holder en peker til det neste elementet, og det andre elementet holder nullpunktet (entall for data). Et dobbeltkoblet listeelement kan implementeres av en struktur på tre medlemmer. Det midterste elementet holder nullpunktet, mens det første og tredje elementet holder pekere til sine tilstøtende elementer. Køen er en først-inn-først-ut-datastruktur. Det er situasjoner i databehandling når data kommer i form av en kø, noe som nødvendiggjør først-inn-først-ut-oppførsel. En ressurs i en datamaskin er enhver fysisk eller virtuell komponent med begrenset tilgjengelighet. De inkluderer CPU, skjermkort, harddisk og minne. Å dele en slik ressurs trenger en kø. Datamaskinutstyr må av og til avbryte datamaskinen. Avbruddene må håndteres på samme måte som de kom. Dette trenger kø. Køen kan for eksempel brukes til å administrere applikasjonsfiler for en jobb, hvis filene er lagret på datamaskinen. En kø er en listedatastruktur, som enten er en enkeltkoblet liste eller en dobbeltkoblet liste. Som regel er det første elementet som kommer inn på listen det første elementet som kommer ut. C ++ gir en kødatastruktur i standardbiblioteket. Kategoriene av medlemsfunksjoner og operatører som er tilgjengelige for denne strukturen er køkonstruksjon, køelementtilgang, køkapasitet, kømodifikatorer og køoverbelastede operatører. Enhver datastruktur i kø må minst inneholde funksjonene push () og pop (). push () betyr å sende et nytt element bak i køen; og pop () betyr å fjerne elementet som er foran i køen. Dessverre, i C ++, returnerer disse funksjonene ikke verdien som er presset eller poppet. Så, for å kjenne det siste elementet før du skyver, må den ekstra tilbake () -funksjonen brukes; og for å kjenne det første elementet før du popper, må den ekstra fronten () -funksjonen brukes. En verdi er til en datatype, slik et instantiert objekt er for en klasse. Så en bestemt klasse kan brukes som datatype for kømalen. Ulike objekter for klassen blir som forskjellige verdier for klassen. Køen har applikasjoner på datamaskinen. Den kan for eksempel brukes til å administrere applikasjonsfiler for en jobb, hvis filene er lagret på datamaskinen. Chrys
kø<konst røye*>at2({'ond'});
intpå en=at1>at2;
koste<<på en<< ' n';
kø<konst røye*>at2({'ond'});
intpå en=at1<=at2;
koste<<på en<< ' n';
kø<konst røye*>at2({'ond'});
intpå en=at1> =at2;
koste<<på en<< ' n'; Klassen og dens Instantiated Objects
#inkludere
ved hjelp av navneområde std;
klasse TheCla
{
offentlig:
intpå en;
statisk røyekap;
tomromfunksjon(røyeNei, konst røye *s. s)
{
koste<< 'Det er ' <<på en<< 'bøker verdt' <<Nei<<s. s<< ' i butikken.' << ' n';
}
statisk tomrommoro(røyekap)
{
hvis (kap== 'til')
koste<< 'Offisiell statisk medlemsfunksjon' << ' n';
}
};
inthoved-()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
kø<TheCla>at;
at.trykk(obj1);at.trykk(obj2);at.trykk(obj3);at.trykk(obj4);at.trykk(obj5);
koste<<at.størrelse() << ' n';
komme tilbake 0;
} Tilknyttet liste
Søknader om køen
Deling av datamaskinressurser
Håndtering avbryter
Administrer informasjon.
Konklusjon