Introducció
Una cua és una col·lecció d’elements, on el primer element afegit a la llista ha de ser el primer que s’hagi d’eliminar a continuació. Així doncs, a mesura que s’afegeixen articles a la col·lecció, la seva mida creix, és a dir, creix en longitud. Sempre que s’ha d’eliminar qualsevol element, ha de ser el primer que s’afegeixi. Si els elements s’eliminen contínuament, el següent és el segon element; el tercer s’elimina després, etc.
Un cop eliminat el primer element de la llista original, el segon es converteix en el primer element. Després d’eliminar el segon element, el tercer es converteix en el primer element, etc.
Un bon exemple de la cua de la vida real és quan la gent fa fila per esperar el servei o bé. La primera persona se serveix abans que la darrera. Tot i això, la cua de què es parla en aquest tutorial és la cua de programari, tal com es dissenya a C ++.
FIFO
FIFO significa First-In, First-Out. És una altra manera d’apreciar la cua. Això vol dir que el primer element que entra a la llista és el primer que s’ha d’eliminar sempre que s’hagi d’eliminar. L’inici de la llista s’anomena capçalera o frontal; el final de la llista s’anomena darrera o cua.
Operacions essencials
Una cua de programari ha de tenir almenys les operacions següents:
empènyer
Aquesta operació afegeix un nou element a la part posterior de la cua. Aquesta operació es denomina oficialment encau.
torn
Aquesta operació elimina el primer element de la cua i el segon element es converteix en el primer element nou. Aquesta operació s’anomena oficialment cola. Es diu pop en C ++.
En aquest article s’explica com utilitzar l’estructura de dades de la cua C ++. Hauríeu de conèixer indicadors i referències C ++ per entendre la resta d’aquest article.
Classe i objectes
Una classe és un conjunt de variables i funcions que funcionen juntes, on les variables no tenen assignats valors. Quan s’assignen valors a les variables, la classe es converteix en un objecte. Els diferents valors donats a una mateixa classe donen lloc a objectes diferents; és a dir, diferents objectes són la mateixa classe amb valors diferents. Es diu que la creació d’un objecte a partir d’una classe és la instància de l’objecte.
El nom, cua, és una classe. Un objecte creat a partir de la classe de cua té un nom triat pel programador.
Es necessita una funció que pertany a una classe per crear un objecte de la classe. A C ++, aquesta funció té el mateix nom que el nom de la classe. Els objectes creats (creats a instàncies) a partir de la classe tenen diferents noms donats pel programador.
Crear un objecte a partir de la classe significa construir l’objecte; també vol dir instàncies.
Un programa C ++ que utilitza la classe de cua comença amb les línies següents a la part superior del fitxer:
#incloure#incloure
utilitzant l'espai de noms std;
La primera línia és per a l'entrada / sortida. La segona línia és permetre al programa utilitzar totes les funcions de la classe de cua. La tercera línia permet al programa utilitzar els noms a l’espai de noms estàndard.
Sobrecàrrega d'una funció
Quan dues o més signatures de funció diferents tenen el mateix nom, es diu que aquest nom està sobrecarregat. Quan es crida una funció, el nombre i el tipus d'arguments, determineu quina funció s'executa realment.
Construcció
cua<tipus>nom()La declaració següent crea una cua anomenada, que de tipus int.
cua<int>que;La cua està buida. La declaració comença amb la paraula reservada, cua seguida de claudàtors amb el tipus de dades. Després teniu el nom de programador de la cua.
Construint amb la llista d’inicialitzadors
La definició següent mostra com crear una cua amb la llista d'inicialitzadors:
cua<flotar>que({1.1, 2.2, 3.3, 4.4});Destruint una cua
Per destruir una cua, deixeu-la fora de l'abast.
Accés a l'element de cua
push (valor)
Una cua és una llista Primera entrada-primera sortida. Per tant, cada valor s’afegeix des de la part posterior. El següent segment de codi crea una cua buida, després de la qual s’afegeixen cinc valors flotants des de la part posterior:
cua<flotar>que;que.empènyer(1.1);
que.empènyer(2.2);
que.empènyer(3.3);
que.empènyer(4.4);
que.empènyer(5.5);
size () const
Això retorna el nombre d'elements a la cua. El següent codi il·lustra:
cua<flotar>que;que.empènyer(1.1);que.empènyer(2.2);que.empènyer(3.3);que.empènyer(4.4);que.empènyer(5.5);
cost<<que.mida() << ' n';
La sortida és 5.
front ()
Això retorna una referència al primer element de la cua, sense eliminar-lo. La sortida del següent codi és 1.1.
cua<flotar>que;que.empènyer(1.1);que.empènyer(2.2);que.empènyer(3.3);que.empènyer(4.4);que.empènyer(5.5);
cost<<que.frontal() << ' n';
L'element no s'elimina de la cua.
front () const
Quan la construcció de la cua va precedida de const, l'expressió front () const s'executa en lloc de front (). S'utilitza al codi següent, per exemple.
constcua<flotar>que({1.1, 2.2, 3.3, 4.4, 5.5});cost<<que.frontal() << ' n';
Es torna una referència constant. L'element no s'elimina del vector. No es poden canviar els elements de la cua.
esquena()
Això retorna una referència a l'últim element de la cua, sense eliminar-lo. La sortida del codi següent és 5.5.
cua<flotar>que;que.empènyer(1.1);que.empènyer(2.2);que.empènyer(3.3);que.empènyer(4.4);que.empènyer(5.5);
cost<<que.esquena() << ' n';
back () const
Quan la construcció de la cua va precedida de const, l'expressió back () const s'executa en lloc de back (). S'utilitza al codi següent, per exemple.
constcua<flotar>que({1.1, 2.2, 3.3, 4.4, 5.5});cost<<que.esquena() << ' n';
Es torna una referència constant. L'element no s'elimina de la cua. Amb la const anterior per a la construcció de la cua, els elements de la cua no es poden canviar.
Capacitat de cua
size () const
- Vegeu més amunt
empty () const
Això retorna 1 per cert si no hi ha elements a la cua, o 0 per fals si la cua està buida. El següent codi ho il·lustra:
cua<flotar>que1({1.1, 2.2, 3.3, 4.4, 5.5});cost<<que1.buit() << ' n';
cua<flotar>que2;
cost<<que2.buit() << ' n';
La sortida és:
01
Modificadors de cua
pop ()
Una cua és FIFO, de manera que qualsevol element que s’hagi d’eliminar s’ha d’eliminar de la part superior (cap) de la cua. Aquesta funció membre elimina el primer element sense retornar-lo. El següent codi ho il·lustra:
cua<flotar>que({1.1, 2.2, 3.3, 4.4, 5.5});cost<<que.frontal() << ' n';
que.pop();
cost<<que.mida() << ' n';
La sortida és:
1.14
a.swap (b)
Es poden intercanviar dues cues, tal com es mostra en aquest segment de codi:
cua<flotar>que1({1.1, 2.2, 3.3, 4.4, 5.5});cua<flotar>que2({10, 20});
que1.intercanviar(que2);
cost<< 'Primer element i mida de que1:
'<<que1.frontal() <<','<<que1.mida() << ' n';
cost<< 'Primer element i mida de que2'<<
que2.frontal() <<','<<que2.mida() << ' n';
La sortida és:
Primer element i mida de que1: 10, 2
Primer element i mida de que2: 1.1, 5
Tingueu en compte que la longitud d'una cua s'incrementa si cal. A més, els valors que no tenien substitucions se substitueixen per algun valor per defecte. Els tipus de dades han de ser del mateix tipus.
Igualtat i operadors relacionals per a cues
Per als caràcters ordinaris en C ++, en ordre ascendent, els números vénen abans que les majúscules, abans que les minúscules. El caràcter espacial és anterior a zero i tots ells.
Operadors d’igualtat
Retorna 1 per a cert i 0 per a fals.
L'operador ==
Retorna 1 si les dues cues tenen la mateixa mida i els elements corresponents són iguals; en cas contrari, retorna 0. Exemple:
cua<const char*>que1({'amable', 'alguna cosa més'});cua<const char*>que2({'malvat'});
inten un=que1==que2;
cost<<en un<< ' n';
La sortida és: 0.
L'operador! =
- oposat a l’anterior. Exemple:
cua<const char*>que1({'amable', 'alguna cosa més'});cua<const char*>que2({'malvat'});
inten un=que1! =que2;
cost<<en un<< ' n';
La sortida és: 1.
Operadors relacionals
Retorna 1 per a cert i 0 per a fals.
El
Retorna 1 si la primera cua és el subconjunt inicial de la segona cua, amb els elements de les dues porcions iguals en el mateix ordre. Si ambdues cues tenen la mateixa mida o mides diferents i es mouen d’esquerra a dreta, es troba un element a la primera cua que és inferior a l’element corresponent de la segona cua, encara es retornarà 1. En cas contrari, es retorna 0. Exemple:
cua<const char*>que1({'amable', 'alguna cosa més'});cua<const char*>que2({'malvat'});
inten un=que1<que2;
cost<<en un<< ' n';
La sortida és 1. El> Operador - oposat a l’anterior. Exemple: Sortida: 0 El<= Operator - el mateix que Sortida: 1 L'operador> = - oposat a l’anterior. Exemple: Sortida: 0 Un valor correspon a un tipus de dades, com un objecte instantani a una classe. La construcció de la cua també pot acceptar una classe com a tipus de dades. El programa següent ho il·lustra: La sortida és 5. La llista de cues s’anomena tècnicament llista enllaçada. Hi ha dos tipus de llistes enllaçades per a la cua: llista enllaçada individualment i llista doblement enllaçada. Un element de llista enllaçat individualment es pot implementar mitjançant una estructura de dos membres. Un membre té un punter a l’element següent i l’altre membre té la dada (singular per a dades). Un element de llista doblement enllaçat es pot implementar mitjançant una estructura de tres membres. El membre central manté la dada, mentre que el primer i el tercer membres tenen indicadors cap als seus elements adjacents. La cua és una estructura de dades de primer a primer que surt. Hi ha situacions en la informàtica quan les dades arriben en forma de cua, cosa que requereix un comportament de primer a entrada. Un recurs en un ordinador és qualsevol component físic o virtual de disponibilitat limitada. Inclouen la CPU, la targeta de vídeo, el disc dur i la memòria. Compartir aquest recurs necessita una cua. Els perifèrics d’ordinador han d’interrompre l’ordinador de tant en tant. Les interrupcions s'han de gestionar de la mateixa manera que van arribar. Això necessita una cua. La cua es pot utilitzar, per exemple, per gestionar fitxers d'aplicacions per a una tasca, si els fitxers s'emmagatzemen a l'ordinador. Una cua és una estructura de dades de llista, que és una llista enllaçada individualment o una llista doblement enllaçada. Com a regla general, el primer element que entra a la llista és el primer que surt. C ++ proporciona una estructura de dades de cua a la seva biblioteca estàndard. Les categories de funcions membres i operadors disponibles per a aquesta estructura són la construcció de cues, l’accés a elements de cua, la capacitat de la cua, els modificadors de cua i els operadors amb sobrecàrrega de cua. Qualsevol estructura de dades de cua ha de proporcionar com a mínim les funcions de membre push () i pop (). push () significa, enviar un element nou a la part posterior de la cua; i pop () significa, eliminant l'element que hi ha a la part davantera de la cua. Malauradament, a C ++, aquestes funcions no retornen el valor empès o aparegut. Per tant, per conèixer l’últim element abans d’empènyer, s’ha d’utilitzar la funció extra back (); i per conèixer el primer element abans d’aparèixer, s’ha d’utilitzar la funció frontal addicional (). Un valor correspon a un tipus de dades, com un objecte instantani a una classe. Per tant, es pot utilitzar una classe particular com a tipus de dades per a la instanciació de plantilla de cua. Diferents objectes per a la classe es converteixen en valors diferents per a la classe. La cua té aplicacions a l’ordinador. Es pot utilitzar, per exemple, per gestionar fitxers d'aplicacions per a una tasca, si els fitxers s'emmagatzemen a l'ordinador. Chrys
cua<const char*>que2({'malvat'});
inten un=que1>que2;
cost<<en un<< ' n';
cua<const char*>que2({'malvat'});
inten un=que1<=que2;
cost<<en un<< ' n';
cua<const char*>que2({'malvat'});
inten un=que1> =que2;
cost<<en un<< ' n'; Class i els seus objectes instantanis
#incloure
utilitzant l'espai de noms std;
classe TheCla
{
públic:
inten un;
estàtic charcap;
buitfunció(charno, const char *pàg)
{
cost<< 'Hi ha' <<en un<< 'val la pena els llibres' <<no<<pàg<< 'a la botiga'. << ' n';
}
estàtic buitdiversió(charcap)
{
si (cap== 'A')
cost<< 'Funció de membre estàtic oficial' << ' n';
}
};
intprincipal()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
cua<TheCla>que;
que.empènyer(obj1);que.empènyer(obj2);que.empènyer(obj3);que.empènyer(obj4);que.empènyer(obj5);
cost<<que.mida() << ' n';
tornar 0;
} Llista enllaçada
Aplicacions de la cua
Compartir recursos informàtics
Manipulació de les interrupcions
Gestionar la informació.
Conclusió