DOUG LLOYD: Així que si vostè té vist el vídeo a la pila, això és, probablement, va sentir com una mica de deixa vu. Es va a un concepte molt similar, només amb un petit gir en ell. Anem a parlar ara sobre les cues. Així que una cua, similar a una pila, és un altre tipus d'estructura de dades que podem utilitzar per mantenir dades en una manera organitzada. Igual que en una pila, pot ser implementat com una matriu o una llista enllaçada. A diferència d'una pila, les regles que utilitzem per determinar quan s'afegeixen i s'eliminen de les coses una cua són una mica diferents. A diferència d'una pila, que és una estructura LIFO, últim en entrar, primer en sortir, una cua és un FIFO estructura, FIFO, primer a entrar, primer en sortir. Ara cues, és probable que tenen una analogia amb les cues. Si alguna vegada has estat a la cua un parc d'atraccions o en un banc, hi ha una mena de justícia la implementació de l'estructura. La primera persona a la fila el banc és la primera persona qui va a parlar amb el caixer. 

Seria una mena de carrera a la part inferior si l'única manera has de parlar amb el caixer en el banc anava a ser l'última persona a la fila. Tothom estaria sempre volen ser l'última persona de la fila, i la persona que hi era primer qui ha estat esperant per un temps, podria ser-hi durant hores, i hores i hores abans que tinguin l'oportunitat de realitat retirar diners al banc. I així, les cues són una mena de equitat implementació d'estructura. Però això no vol dir necessàriament que les piles són una cosa dolenta, simplement que les cues són una altra manera de fer-ho. Així que de nou una cua és primer a entrar, primer fora, davant d'una pila que dura a, primer a sortir. Igual que en una pila, tenim dues operacions que podem dur a terme a les cues. Els noms són enqueue, que consisteix a afegir un nou element fins al final de la cua, i treure de la cua, que és per eliminar els més antics element des de la part frontal de la cua. Així que anem a afegir elements a l'extrem de la cua, i anem a eliminar elements des de la part frontal de la cua. Una vegada més, amb la pila, vam anar agregant elements a la part superior de la pila i eliminació d'elements des de la part superior de la pila. Així que amb enqueue, està afegint a Al final, l'eliminació de la part davantera. Així que el més antic d'allà sempre és el proper a sortir si tractem i treure de la cua alguna cosa. 

Així que de nou, amb les cues, podem implementacions basades en matrius i llista enllaçada implementacions basades. Anem a començar de nou amb implementacions basades en matrius. La definició de l'estructura es veu molt similar. Tenim una altra matriu no del valor de tipus de dades, pel que pot contenir tipus de dades arbitraris. Estem novament utilitzarà nombres enters en aquest exemple. 

I igual que amb el nostre aplicació pila basada en matrius, perquè estem usant un array, que necessàriament tenir aquesta limitació que C tipus de fa complir en nosaltres, que som nosaltres no tenen cap dinamisme en la nostra capacitat per créixer i reduir la mida de la matriu. Hem de decidir al començament Quin és el nombre màxim de coses que podem posar en aquest cua, i en aquest cas, capacitat seria algun lliures definida constant en el nostre codi. I per als fins d'aquesta de vídeo, la capacitat serà 10. 

Necessitem fer un seguiment de la part davantera de la cua de així que sabem quin element volem treure de la cua, i també necessitem fer un seguiment de alguna cosa else-- el nombre d'elements que tenim a la nostra cua. Cal notar que no estem fer el seguiment del final de la cua, just la mida de la cua. I la raó que s'espera convertit en una mica més clara en un moment. Un cop hem completat aquesta definició de tipus, tenim un nou tipus de dades anomenada cua, que ara podem declarar variables d'aquest tipus de dades. I una mica confusament, he decidit anomenar aquesta cua q, la carta q en lloc del tipus de dades q. 

Així que aquí està la nostra cua. Es tracta d'una estructura. Conté tres membres o de tres camps, una matriu de mida CAPACITAT. En aquest cas, la capacitat és de 10. I aquesta matriu és va a celebrar sencers. En el verd és el front de la nostra cua, el següent element a ser eliminat, i en vermell serà la mida de la cua, quants elements Actualment existent a la cua. Així que si diem iguals q.front 0, i la mida és igual q.size 0-- estem posant 0s en aquests camps. I en aquest punt, estem més o menys a punt per començar a treballar amb la nostra cua. 

Així que la primera operació que puguem realitzar és posar en cua alguna cosa, afegir un nou element a al final de la cua. Bé, què és el que necessitem fer en el cas general? Bé aquesta funció encolar necessitats per acceptar un punter a la nostra cua. Un cop més, si haguéssim declarat la nostra cua a nivell mundial, no necessitaríem fer això necessàriament, però en general, d'acceptar punters a les estructures de dades d'aquesta manera, perquè en cas contrari, estem passant per value-- estem passant còpies de la cua, i així no canviarem realment la cua que tenim la intenció de canviar. 

L'altra cosa que ha de fer és acceptar un element de dades del tipus apropiat. Un cop més, en aquest cas, és serà sencers, però vostè podria arbitràriament declarar el tipus de dades com a valor i utilitzar això de manera més general. Aquest és l'element que volem posar en cua, volem afegir al final de la cua. Llavors realment volem col·locar les dades a la cua. En aquest cas, la col·locació en el correcta ubicació de la nostra matriu, i després volem canviar la mida de la cua, quants elements de nosaltres Actualment tenir. 

Així que anem a començar. Aquest és, de nou, que en general declaració de la funció forma per a la qual enqueue podria ser similar. I aquí anem. Anem a posar en cua el nombre 28 a la cua. Llavors, què farem? Bé, la part davantera de la nostra cua és a 0, i la mida de la nostra cua està a 0, de manera que probablement volem posar el número 28 en la sèrie nombre d'element 0, oi? Així que ara hem ja que en aquest país. Així que ara, què hem de canviar? No volem canviar la part davantera de la cua, perquè volem saber quin element que podríem necessitar per treure de la cua més tard. Així que la raó per la qual tenim davant no és una espècie d'un indicador del que és el més antic de la matriu. Bé, la cosa més vella del array-- en De fet, l'única cosa en la matriu de la dreta ara-- és 28, que és en la ubicació array 0. Així que no volem canviar aquest número verd, perquè aquest és l'element més antic. Més aviat, volem canviar la mida. Així que en aquest cas, anem a increment de mida a 1. 

Ara una espècie general d'idea d'on el següent element es va a anar en una cua és afegir aquests dos nombres junts, front i grandària, i que et diré on ve element a la cua se n'anirà. Així que ara anem a posar en cua un altre número. Anem a posar en cua 33. Així que 33 va entrar en ubicació matriu 0 + 1. Així que en aquest cas, es va per anar a la ubicació matriu 1, i ara la mida de la nostra cua és 2. 

Un cop més, no estem canviant el front de la nostra cua, 28 perquè segueix sent el element més antic, i vull A-- quan finalment arribem a desencua, eliminació d'elements d'aquesta cua, volem saber on l'element més antic és. I pel que sempre cal mantenir algun indicador d'on està. Així que això és el que el 0 és allà. Això és el que hi és per davant. 

Anem a enqueue un element més, 19. Estic segur que es pot endevinar on 19 es va a anar. Va a entrar en ubicació matriu número 2. Això és 0, més 2. I ara la mida de la nostra cua es 3. Tenim 3 elements en els mateixos. Així que si haguéssim de, i no anem que en aquest moment, posar en cua un element més, que entraria en lloc array número 3, i la mida de la nostra cua seria 4. Així que hem en col diversos elements ara. Ara anem a començar a eliminar-los. Anem a treure de la cua de la cua. 

Així similar al pop, que és una espècie l'anàleg d'això per a piles, dequeue necessita acceptar una punter a la queue-- de nou, llevat que sigui declarat globalment. Ara volem canviar la ubicació de la part frontal de la cua. Aquí és on ve una mena de en joc, aquesta variable front, perquè una vegada que eliminem un element, volem per moure al següent element més antic. 

Llavors volem disminuir la mida de la cua, i després volem tornar el valor que va ser eliminat de la cua. Un cop més, no volem simplement descartar-ho. Hem de suposar extraient des del queue-- estem desencua perquè ens preocupem per ell. Així que volem aquesta funció per tornar un element de dades de valor de tipus. Un cop més, en aquest cas, el valor és sencer. 

Així que ara anem a treure de la cua alguna cosa. Anem a treure un element de la cua. Si diem int x és igual a i q, signe q-- una vegada més que és un punter a aquestes dades q structure-- quin element serà tret de la cua? En aquest cas, ja que és una primera in, first out estructura de dades, FIFO, la primera cosa que posem en aquest cua era de 28 anys, de manera que en aquest cas, tindrem 28 de la cua, no 19, que és el ens hagués fet si es tractava d'una pila. Tindrem 28 fora de la cua. 

De manera similar al que vam fer amb una pica, no estem realment va a eliminar 28 de la cua de si mateix, només anem a classe de pretendre que no hi és. Així que va a quedar-s'hi en la memòria, però només som anar a classe d'ignorar-movent els altres dos camps de les nostres dades q estructura. Canviarem la part davantera. Q.front ara va a ser 1, ja que és ara l'element més antic que tenim a la nostra cua, perquè ja hem eliminat 28, que va ser el primer element més antic. 

I ara, volem canviar la mida de la cua a dos elements en lloc de tres. Ara recordeu abans vaig dir quan ens voleu afegir elements a la cua, el posem en un lloc array que és la suma de la part davantera i grandària. Així que en aquest cas, encara estem posant ell, el següent element a la cua, en lloc d'arranjament 3, i veurem que en un segon. 

Així que ara que hem desencolen nostra primer element de la cua. Anem a fer-ho de nou. Anem a treure una altra element de la cua. En el cas, el corrent més antiga element és la ubicació matriu 1. Això és el que q.front ens diu. Aquesta caixa verda ens diu que aquest és l'element més antic. I així, es convertirà en x 33. Tindrem tipus d'oblidar 33 que hi ha a la matriu, i direm que ara, la nou element més antic de la cua és en la ubicació matriu 2, i la mida de la cua, el nombre d'elements tenim a la cua, és 1. Ara anem a posar en cua alguna cosa, i jo tipus de donar aquesta distància fa un segon, però si volem posar 40 al cua, on està 40 va anar? Bé hem estat posant que en q.front més cua de grandària, i així que té sentit realment posar 40 aquí. Ara noti que al algun moment, anem per arribar a la final de la nostra gamma interior de q, però això es va esvair 28 i 33-- en realitat són, tècnicament espais oberts, oi? I així, podem eventually-- aquesta regla d'addició aquests dos junts-- puguem finalment necessitarà mod per la grandària de la capacitat perquè puguem embolicar al voltant. 

Així que si arribem a l'element número 10, si som reemplaçant-ho en l'element número 10, estaríem en realitat el va posar en lloc array 0. I si ens anàvem a varietat ubicació: em excusa, si els afegim junts, i vam arribar al nombre 11 seria on hauríem de posar ella, que no existeix en aquest array-- seria anar fora de límits. Podríem mod 10 i posar en lloc array 1. Així és com funcionen les cues. Ells sempre van a anar d'esquerra a dreta i possiblement embolicar al voltant. I vostè sap que són si a la mida, aquesta caixa vermella, arriba a ser igual a la capacitat. I així, després hem afegit 40 a la cua, bé, ¿què hem de fer? Bé, l'element més antic a la cua segueix sent 19, pel que no volem canviar la part davantera de la cua, però ara tenim dos elements a la cua, i així volem augmentar nostre grandària des 1 a 2. 

Això és més o menys amb treballant amb les cues de la matriu, i similar a apilar, també hi ha una manera per aplicar una cua com una llista enllaçada. Ara bé, si aquest tipus d'estructura de dades sembla familiar per a vostè, ho és. No és una llista enllaçada, és una llista doblement enllaçada. I ara, com un a part, és en realitat possible implementar una cua com una llista enllaçada, però Crec que en termes de visualització, que en realitat podria ajudar a veure això com una llista doblement enllaçada. Però és definitivament possible fer això com una llista enllaçada. 

Així que anem a fer una ullada a el que això podria ser similar. Si volem enquue-- de manera que ara, un cop més estem el canvi a una llista enllaçada model basat aquí. Si volem posar en cua, volem afegir un nou element, així ¿Què és el que hem de fer? Bé, en primer lloc, perquè estem afegint al final i l'eliminació de la començant, probablement volen mantenir punters tant a la el cap i la cua de la llista enllaçada? Cua de ser un altre terme per al final de la llista enllaçada, l'últim element de la llista enllaçada. I aquests probablement, un cop més, ser beneficiós per a nosaltres si són variables globals. Però ara si volem afegir un nou element, ¿què hem de fer? El que acabem [? Malak?] O dinàmicament destinar el nostre nou node per a nosaltres mateixos. I llavors, igual que quan afegim cap element a una llista que doblement enllaçada, només cal ordenar de-- els últims tres passos aquí són només tracta de moure el punters en la forma correcta de manera que l'element s'agrega a la cadena sense trencar la cadena o fer algun tipus d'error o tenir algun tipus d'accident succeir en què puguem accidentalment orfes alguns elements de la nostra cua. Aquí està el que aquest podria ser similar. Volem afegir l'element 10 fins al final d'aquesta cua. Així que l'element més antic aquí està representat pel cap. Això és el primer que posem en aquesta cua hipotètica aquí. I la cua, 13, és el més Recentment afegit element. I pel que si volem posar en cua 10 a aquesta cua, volem posar-ho després del 13. I així anem a dinàmicament assignar espai per a un nou node i verifiqui que no nul·la per assegurar no tenim un error de memòria. Llavors anem a col·locar 10 en aquest node, i ara hem de tenir cura sobre com organitzem punters així que no trenquem la cadena. 

Podem establir camp anterior de 10 assenyalar de nou a l'edat de la cua, i des '10 serà el nova cua en algun moment de moment tots aquests cadenes estan connectats, res vindrà després del 10 d'ara. I així que la propera punter de 10 apuntarà a null, i després fem això, després que hem connectat 10 cap enrere a la cadena, podem prendre l'antic cap, o, excusa jo, el vell de la cua de la cua. El final antic de la cua, 13, i fer que apunti a 10. I ara, en aquest moment, tenim en cua el número 10 en aquesta cua. Tot el que necessitem fer ara és simplement moure el cua perquè apunti a 10 en lloc de 13. 

Desencua és en realitat molt similar a esclatar a partir d'una pila que és implementat com una llista enllaçada si has vist el vídeo piles. Tot el que necessitem fer és començar pel començant, trobar el segon element, alliberar el primer element, i després moure el cap perquè apunti al segon element. Probablement millor per visualitzar- només per ser molt clar al respecte. Així que aquí està la nostra cua de nou. 12 és l'element més antic en la nostra cua, el cap. 10 és l'element més nou en la nostra cua, la nostra cua. 

I així, quan volem treure de la cua d'un element, volem eliminar l'element més antic. Llavors, què fem? Bé establim un punter recorregut que comença al capdavant, i ens movem de manera que apunta al segon element d'aquesta queue-- alguna cosa dient trav és igual a trav fletxa al costat, per exemple, mouria trav allà per assenyalar 15, el qual, després que treure de la cua 12, o després traiem 12, voluntat convertit en l'element més antic llavors. 

Ara tenim un celler en el primer element a través del cap del punter i el segon element a través de la Trav punter. Podem cap ara lliure, i llavors podem dir res arriba abans del 15 de més. Així que podem canviar 15 de l'anterior punter per apuntar a null, i acabem de moure el cap sobre. I aquí anem. Ara tenim èxit tret de la cua 12, i ara nosaltres tenir una altra cua de 4 elements. Això és més o menys tot no a les cues, tots dos basats en matrius i llista enllaçada amb base. Sóc Doug Lloyd. Això és CS 50.