[Powered by Google Translate] [Cola] [Chris Gerber, Harvard University] Això és CS50, CS50.TV] Una estructura de dades útil per emmagatzemar una col · lecció ordenada d'elements és una cua. S'usa quan els elements necessiten ser remoguts en el mateix ordre en què s'han afegit. Aquest concepte es coneix com FIFO, que és un acrònim de primer a entrar, primer en sortir. Per ajudar a visualitzar aquest, pot ser útil per a foto una fila per pagar en una botiga. Com la gent arriba, esperen al final de la línia. El caixer llavors fan torns per servir els clients al front, que surti de la línia al mateix temps. En informàtica, ens referim a la part davantera de la cua al cap i la part posterior com la cua. Un exemple de quan es pot utilitzar en una aplicació d'aquest és una llista d'espera per a inscripcions de classe. Quan es disposi de seients a la classe, la persona al capdavant de la llista d'espera s'ofereix l'oportunitat de inscriure a la classe. 

Una cua pot ser construïda usant qualsevol col · lecció que emmagatzema les dades en ordre, com ara una matriu o una llista enllaçada. Juntament amb la col · lecció per emmagatzemar els elements de la cua, també es necessita un mètode per afegir elements al final de la cua, que es diu enqueuing, i una altra per eliminar un element del cap de la cua, que es diu desencua. Sovint és útil incloure un altre mètode per tornar la longitud actual de la cua així com un mètode per comprovar si la cua és buida. Anem a veure com podem implementar una cua d'enters en C, utilitzant una matriu per a la col · lecció d'elements. En primer lloc, vam crear una estructura anomenada cua per contenir les nostres variables. Anem a utilitzar una matriu de mida fixa 0 índex d'enters per emmagatzemar els elements. També s'inclouen un cap variable anomenada que emmagatzema l'índex de l'element que es troba actualment al cap de la cua. Una tercera variable, anomenada longitud, s'utilitzarà per fer un seguiment del nombre d'elements en la matriu. Com a alternativa, es pot considerar l'ús d'una variable anomenada cua perquè apunti a l'element últim camp a la matriu. Abans d'escriure codi més, anem a provar el nostre disseny. Anem a començar amb una matriu buida de longitud 0, amb el cap a 0. Ara anem a enqueue 4 valors - 6, 2, 3, i 1. La longitud serà ara 4, i el cap es quedarà a 0. 

Què passa si treure de la cua un valor? Anem a reduir la longitud a 3, establir el cap a 1, i tornar el valor 6. Aquest codi es veuria així. Aquí tenim la funció de treure de la cua, que pren un punter a la cua - q - i un punter a l'element, que és un tipus int. En primer lloc, comprovar la longitud de la cua per assegurar-se que és més gran que 0, per assegurar que hi ha un element a ser llevades de la cua. Després ens fixem en la matriu d'elements, en la posició del cap, i escolliu el valor d'element a ser el valor en aquesta posició. Després canviem el cap per ser el següent índex % De la capacitat. A continuació, reduir la longitud de la cua per 1. Finalment, tornem true per indicar que el treure de la cua s'ha realitzat correctament. Si treure de la cua de nou, la longitud serà 2, el cap també es convertirà en dues, i el valor de retorn serà 2. 

Què passa si encolar altre valor, com un 7? Com ja es trobaven al final de la cua, haurem de embolicar i emmagatzemar el valor a 0 element de la matriu. Matemàticament, això es pot representar mitjançant l'addició de la longitud per l'índex del cap i la realització d'un mòdul utilitzant la capacitat de la cua. Aquí és a dir 2 +2, que és 4% 4, que és 0. Traduint aquesta idea de codificar tenim aquesta funció. Aquí veiem la funció de posada en cua, que pren un punter a la cua - q - i pren l'element a encolar, que és un nombre enter. A continuació comprovar per assegurar-se que la capacitat de la cua és encara més gran que la longitud actual de la cua. A continuació, es guarda l'element en la matriu d'elements en l'índex que es determina pel cap% + longitud de la capacitat de la cua. A continuació, augmentar la longitud de la cua per 1, i després tornar true per indicar que la funció de posada en cua s'ha realitzat correctament. 

A més de les dues funcions que hem esmentat, hi ha dues funcions addicionals. La primera és la funció IsEmpty, que pren un punter a la cua i verifica que la longitud és 0. La segona és la funció de longitud, que també té un punter a la cua i retorna la longitud actual de l'estructura. Aquesta breu ressenya ha demostrat una possible implementació d'una cua. Una de les limitacions a aquesta implementació és que la cua té una mida màxima fix. Si tractem d'afegir més elements que la cua pot contenir, és possible que hàgim d'ignorar la sol · licitud i deixar anar l'element, o potser prefereix tornar algun tipus d'error. Ús d'una llista vinculada en lloc d'una matriu faria més fàcil a mida dinàmicament la cua. No obstant això, ja que no tenen accés directe als elements d'una llista enllaçada, si no mantenim un registre de la cua, hauríem de escanejar tota la llista vinculada a arribar fins al final cada vegada. També podria considerar l'ús d'una gran varietat d'altres tipus de dades, com ara estructures, per crear cues de elements més complexos. Pensant de nou al nostre exemple d'una llista d'espera de classe, aquestes estructures podrien representar als estudiants individuals. 

El meu nom és Chris Gerber, i això és CS50. [CS50.TV] I volta - >> Una vegada més. I tornar true per indicar que - la cua s'ha realitzat correctament. -% De la capacitat de la cua - Serà divertit en edició. [Rialles]