DOUG LLOYD: Deci, dacă ați vizionat video de pe stivă, Aceasta este, probabil va simti ca un pic de deja vu. Se va un concept foarte asemănătoare, doar cu o ușoară poftă de mâncare pe el. Vom vorbi acum despre cozile. Deci, o coadă, similar cu un stack, este un alt fel de structură de date pe care le putem folosi pentru a menține date într-un mod organizat. Similar cu o stivă, acesta poate fi pus în aplicare ca o matrice sau o listă de legat. Spre deosebire de o stivă, regulile pe care le folosim pentru a determina atunci când lucrurile se adaugă și se îndepărtează de la o coadă sunt un pic diferit. Spre deosebire de o stivă, care este o structură LIFO, ultimul intrat, primul ieșit, o coadă este un FIFO structura, FIFO, primul intrat, primul ieșit. Acum cozi, probabil au o analogie cu cozile. Dacă ați fost vreodată la coadă la un parc de distracții sau la o bancă, există un fel de echitate de punere în aplicare structura. Prima persoană la coadă la banca este prima persoana Șansă de a vorbi la povestitor. 

Ar fi un fel de cursă la partea de jos în cazul în care singura cale ai să vorbești cu casierul de la banca a fost de a fi ultima persoană în linie. Toata lumea ar dori întotdeauna pentru a fi ultima persoană în linie, și persoana care a fost acolo primul care a fost de așteptare pentru un timp, ar putea fi acolo pentru ore, și ore și ore înainte de a avea o șansă de a efectiv retrage bani de la bancă. Și astfel cozile sunt un fel de corectitudine de punere în aplicare structura. Dar asta nu înseamnă neapărat că stive sunt un lucru rău, doar că cozile sunt un alt mod de a face acest lucru. Deci, din nou, o coadă este primul intrat, primul out, comparativ cu o stivă care ultimul în, primul ieșit. Similar cu o stivă, avem două operațiuni pe care le poate efectua pe cozile. Numele sunt Puneți în coadă, care este de a adăuga un nou element la sfârșitul listei, și dequeue, care este pentru a elimina cele mai vechi Element din fata a cozii. Deci vom adăuga elemente pe capătul cozii, si vom elimina elemente din partea din față a cozii. Din nou, cu stiva, am fost adăugarea de elemente la vârful stivei și eliminarea elementelor din partea de sus a stivei. Deci, cu Puneți în coadă, este adăugarea la sfârșitul, eliminarea din față. Deci cel mai vechi lucru acolo este întotdeauna următorul lucru pentru a ieși dacă vom încerca și dequeue ceva. 

Deci, din nou, cu cozile, putem implementari bazate pe matrice și lista de legat pe bază de implementări. Vom începe din nou cu implementari bazate pe matrice. Definiția structurii pare destul de asemănătoare. Avem un alt array acolo de date valoare de tip, astfel încât să poată ține tipuri de date arbitrare. Vom din nou de gând să utilizeze numere întregi în acest exemplu. 

Și, la fel ca și cu nostru punerea în aplicare a stack-based matrice, pentru că suntem folosind un matrice, am neapărat au această limitare că C gen de impune pe noi, care ne este nu au nici dinamism în nostru capacitatea de a dezvolta și reduce matrice. Trebuie să decidă la începutul ceea ce este numărul maxim de lucruri pe care le putem pune în această coadă, și în acest caz, Capacitate ar fi unele de lire definit constant în codul nostru. Și în sensul prezentului video, capacitatea va fi de 10. 

Avem nevoie pentru a urmări partea din față a cozii așa că știm care element de vrem să dequeue, și avem nevoie, de asemenea, pentru a urmări ceva else-- numărul de elemente că avem în coadă nostru. Observați că nu te urmărirea de la sfârșitul cozii, doar dimensiunea cozii. Și motivul pentru care va sperăm deveni un pic mai clar într-o clipă. După am finalizat această definiție tip, avem un nou tip de date numit coada, care putem acum declara variabile de acest tip de date. Și oarecum confuz, m-am hotărât pentru a apela acest coadă q, litera q în loc de tip de date q. 

Deci, aici este coada noastră. Este o structură. Acesta conține trei membri sau trei domenii, o serie de dimensiuni capacitate. În acest caz, capacitatea este de 10. Și această matrice este va ține întregi. În verde este partea din față a coada noastre, Element de lângă fie eliminate, iar în roșu va fi de mărimea cozii, cât de multe elemente sunt în prezent existente în coada de așteptare. Deci, dacă spunem egali q.front 0, și dimensiunea q.size egal 0-- suntem punerea 0s în aceste domenii. Și în acest moment, noi suntem destul de mult gata pentru a începe lucrul cu coada noastră. 

Deci prima operație putem efectua este de a Puneți în coadă ceva, pentru a adăuga un element nou la capătul cozii. Ei bine, ceea ce avem nevoie pentru a face în cazul general? Ei bine, această funcție are nevoie Puneți în coadă să accepte un pointer la coadă nostru. Din nou, dacă am fi declarat coadă nostru la nivel global, nu am nevoie pentru a face acest lucru neapărat, dar, în general, ne trebuie să accepte indicii la structuri de date în acest fel, pentru că în caz contrar, suntem trece prin value-- suntem trecând în copii ale coadă, și așa nu suntem de fapt în schimbare coada care ne-am propus să se schimbe. 

Un alt lucru de care are nevoie să faceți este să accepte un element de date de tip corespunzătoare. Din nou, în acest caz, este O să fie numere întregi, Dar ai putea arbitrar declara tipul de date ca valoare și de a folosi acest lucru mai general. Asta e elementul vrem să Puneți în coadă, dorim să adăugăm la sfârșitul cozii de așteptare. Apoi ne-am dori de fapt să plasa că datele în coada de așteptare. În acest caz, se fi introduse în Locul de amplasare corectă a matrice noastre, și apoi ne-o dorim pentru a schimba dimensiunea de coada, cât de multe elemente noi, în prezent au. 

Deci, să începem. Iată, din nou, că generalul Declarația funcție formă pentru ceea ce ar putea arata ca Puneți în coadă. Și aici vom merge. Să Puneți în coadă numărul 28 în coada de așteptare. Deci, ce ne facem? Ei bine, partea din față a coada nostru este la 0, iar mărimea cozii noastre este la 0, și așa, probabil, ne-o dorim pentru a pune numărul 28 în matrice număr element de 0, nu? Așa că am pus acum că acolo. Deci, acum ce avem nevoie pentru a schimba? Noi nu vrem să se schimbe partea din față a cozii, pentru că vrem să știm ce elemente s-ar putea nevoie pentru a dequeue mai târziu. Deci, motivul pentru care avem față acolo este un fel de un indicator a ceea ce este cel mai vechi lucru din matrice. Ei bine, cel mai vechi lucru din array-- în De fapt, singurul lucru în matrice dreapta now-- este 28, care este la matrice locație 0. Deci nu vrem să schimba acest număr verde, pentru că asta e cea mai veche elementul. Mai degrabă, vrem sa schimbam dimensiunea. Deci, în acest caz, vom incrementa dimensiune la 1. 

Acum un fel generală a ideii de unde element de lângă este de gând să meargă într-o coadă este de a adăuga aceste două numere împreună, față și dimensiunea, și că voi spune unde următoarea element din coada este de gând să meargă. Deci, acum hai sa Puneți în coadă un alt număr. Să Puneți în coadă 33. Deci, 33 este de gând să meargă în matrice Localizare 0 plus 1. Deci, în acest caz, va pentru a merge în matrice locație 1, și acum dimensiunea coada nostru este de 2. 

Din nou, nu suntem schimbarea partea din față a coada noastre, pentru că 28 este încă cel mai vechi element și noi vreau sa-- când ajungem în cele din urmă la dequeuing, eliminarea elementelor din acest coada, vrem să știm în cazul în care cel mai vechi element este. Și așa am mereu nevoie pentru a menține un indicator de unde este. Deci, asta e ceea ce este acolo pentru 0. Asta e ceea ce fata este acolo pentru. 

Să în Puneți în coadă o mai multe elemente, 19. Sunt sigur că puteți ghici în cazul în care 19 este de gând să meargă. O să meargă în matrice locație numărul 2. Asta e 0 plus 2. Și acum dimensiunea coada nostru este de 3. Avem 3 elemente în ea. Deci, dacă ar fi să, și nu vom chiar acum, Puneți în coadă un alt element, ar intra în locație matrice numărul 3, iar mărimea cozii noastre ar fi 4. Deci ne-am enqueued mai multe elemente acum. Acum să începem pentru a le elimina. Să le dequeue din coadă. 

Atât de asemănătoare cu pop, care este un fel a analogului de acest lucru pentru stive, dequeue trebuie să accepte o pointer la queue-- din nou, excepția cazului în care este declarat la nivel global. Acum vrem pentru a schimba locația a cozii de așteptare. Acest lucru este în cazul în care un fel de vorba în joc, că variabila față, pentru că odată ce vom elimina un element, dorim să-l mute la următorul cel mai vechi element. 

Apoi ne-am dori să scadă mărimea cozii, și apoi ne-am dori să se întoarcă la valoarea care a fost scos din coada. Din nou, nu vrem să se debaraseze doar. Suntem probabil sunt extragerea l din queue-- suntem dequeuing pentru că ne pasă de ea. Deci, vrem să se întoarcă această funcție un element de date din valoarea de tip. Din nou, în acest caz, valoarea este întreg. 

Deci, acum hai să dequeue ceva. Să elimina un element din coadă. Dacă spunem int x este egal cu & q, ampersand q-- din nou că este un pointer la aceste date q structure-- ce element de va fi dequeued? În acest caz, pentru că este o prima în, primul ieșit structura de date, FIFO, primul lucru pe care am pus în această coadă a fost 28, și așa mai departe în acest caz, vom lua 28 din coada, nu 19, care este ceea ce ne-ar fi făcut dacă acest lucru a fost o stivă. Vom lua 28 din coada. 

Similar cu ceea ce am făcut cu o stivă, nu suntem de fapt O să ștergeți 28 din coada în sine, vom merge la fel doar de pretinde că nu este acolo. Deci o să rămână acolo în memorie, dar suntem doar O să-l ignore fel de prin mutarea celelalte două domenii de datele noastre q structura. Vom schimba în față. Q.front este acum de gând să fie 1, pentru că acum este cea mai veche elementul avem în nostru coada, pentru că ne-am îndepărtat deja 28, care a fost fostul mai vechi element. 

Și acum, vrem să schimbăm mărimea cozii a două elemente în loc de trei. Acum amintiți-vă mai devreme i-am spus atunci când am doriți să adăugați elemente la coadă, l-am pus într-o locație matrice care este suma față și dimensiuni. Deci, în acest caz, suntem încă punerea aceasta, următorul element în coada de așteptare, în matrice locație 3, și vom vedea că într-o secundă. 

Deci ne-am dequeued acum nostru prim element din coada. Să o facem din nou. Să sterge alt elementul din coada. În acest caz, curentul mai vechi element este matrice locație 1. Asta e ceea ce ne spune q.front. Cutia verde ne spune că asta e cea mai veche elementul. Și astfel, X va deveni 33. Vom doar un fel de uitat care 33 există în matrice, și vom spune că acest moment, nou cel mai vechi element din coada de așteptare este la matrice locație 2, și dimensiunea al cozii, numărul de elemente avem în coada de așteptare, este de 1. Acum, haideți să Puneți în coadă ceva, și eu un fel de a dat acest departe acum un al doilea, dar dacă vrem să 40 în coadă, în cazul în care se 40 va merge? Ei bine, am fost inscrie în plus q.front coadă dimensiune, și deci are sens să de fapt, pentru a pune 40 aici. Acum, observați că, la un moment dat, vom pentru a ajunge la sfârșitul anului gama noastră interiorul Q, dar că stins 28 și 33-- ele sunt de fapt, punct de vedere tehnic spații deschise, nu? Și astfel, am putea eventually-- această normă de a adăuga cei doi am putea în cele din urmă together-- Trebuie să mod de mărimea capacității astfel încât să putem încadra în jurul valorii. 

Deci, dacă ajungem la elementul numărul 10, dacă suntem înlocuindu-l în număr element de 10, ne-ar de fapt, a pus în matrice locație 0. Și dacă am fost de gând să matrice location-- mă scuzați, dacă le-am adaugat împreună, și am ajuns la numărul 11 ar fi în cazul în care ne-ar trebui să pună ea, care nu există în acest array-- ar fi merge în afara limitelor. Am putea Mod de 10 și a pus l în matrice locație 1. Deci, asta e modul în care funcționează cozile. Ei întotdeauna merge de la stânga la dreapta și, eventual, se infasoara in jurul. Și știi că sunt dacă full size, că casetă roșie, devine egal cu capacitatea. Și așa după ce am adăugat 40 la coadă, și ce trebuie să facem? Ei bine, cea mai veche elementul în coada de așteptare este încă 19, așa că nu doriți să modificați partea din față a cozii, dar acum avem două elemente în coada de așteptare, și așa ne-o dorim pentru a mări Dimensiunea nostru de la 1 pentru a doi. 

Asta e destul de mult cu de lucru cu cozi pe bază de matrice, și similar cu stiva, există, de asemenea un mod să pună în aplicare o coadă ca o listă legată. Acum, în cazul în care acest tip de structură de date pare familiar pentru tine, este. Nu este o listă individual legate, E o listă de două ori legată. Și acum, ca o parte, este de fapt posibil să se implementeze o coadă ca o listă individual legate, dar Cred că în termeni de vizualizare, este de fapt s-ar putea ajuta pentru a vizualiza acest lucru ca pe o listă de două ori legată. Dar este cu siguranta posibil să face acest lucru ca o listă individual legat. 

Deci, haideți să aruncăm o privire la ce acest lucru ar putea arăta. Dacă vrem să enquue-- Deci, acum, din nou suntem trecerea la o listă legată model bazat aici. Dacă vrem să Puneți în coadă, vrem pentru a adăuga un element nou, bine ce trebuie să facem? Ei bine, în primul rând, pentru că suntem adăugarea la sfârșitul și scoaterea din începând, probabil doresc să mențină indicii atât cap și coada listei legat? Coada fiind un alt termen pentru sfârșitul listei de legătura, ultimul element din lista de legat. Iar acestea vor probabil, din nou, să fie benefic pentru noi dacă acestea sunt variabile globale. Dar acum, dacă vrem să adăugați un nou Element ce avem de făcut? Ce ne-am [? Malak?] sau dinamic aloca noul nostru nod pentru noi înșine. Și apoi, la fel ca atunci când am adăuga orice element de la o listă de două ori ne-am legat, Trebuie doar pentru a sorta de-- aceste ultime trei etape aici sunt doar toate despre miscarea indicii în mod corect astfel încât elementul se adaugă la lanțul fără a rupe lanțul sau de a face un fel de greșeală sau având un fel de accident se întâmplă prin care accidental orfane unele elemente de coada noastre. Iată ce acest lucru ar putea arăta. Vrem să adăugați elementul 10 la sfârșitul acestui coadă. Deci cea mai veche elementul aici este reprezentat de cap. Asta e primul lucru pe care am pus în această coadă ipotetic aici. Și coada, 13, este cel mai adăugat recent de element. Și astfel, dacă vrem să Puneți în coadă 10 în acest coada, vrem să-l puneți după 13. Și așa vom dinamic aloca spațiu pentru un nou nod și verificați pentru a vă asigura nul nu avem o eroare de memorie. Apoi vom plasa 10 în acel nod, și acum trebuie să fim atenți despre modul în care vom organiza indicii așa că nu rupe lantul. 

Putem stabili de 10 de câmp precedent la punctul înapoi la coada vechi, iar din '10 va fi nou coada la un moment dat până la momentul toate aceste lanțuri sunt conectate, nimic nu va veni După 10 acum. Și astfel 10 de pe lângă indicatorul va indica nul, și apoi după ce am face acest lucru, după ce ne-am conectat 10 înapoi la lanțul, putem lua capul vechi, sau, scuza ma, coada vechi de coadă. Vechea sfârșitul cozii de așteptare, 13, și să-l arate la 10. Și acum, în acest moment, avem enqueued numărul 10 în acest coada. Tot ce trebuie să facem acum este doar deplasați coada pentru a indica 10 în loc de a 13. 

Dequeuing este de fapt foarte asemănător cu popping dintr-o stivă, care este implementat ca o listă legată dacă ați văzut videoclipul stive. Tot ce trebuie să faceți este să înceapă de la începând, găsiți al doilea element, elibera primul element, și apoi mutați capul pentru a indica al doilea element. Probabil, mai bine să-l vizualiza doar pentru a fi în plus clar cu privire la aceasta. Deci, aici e din nou coada noastră. 12 este cea mai veche elementul în coadă nostru, cap. 10 este cel mai nou elementul în coadă noastră, coada noastră. 

Și astfel, atunci când ne-o dorim să dequeue un element, dorim pentru a elimina cea mai veche elementul. Deci, ce facem? Ei bine, ne-am stabilit un pointer de traversare care începe de la cap, si l-am muta, astfel încât să indică al doilea element din acest queue-- ceva spunând trav este egal cu trav săgeata de lângă, de exemplu, s-ar muta acolo trav pentru a indica 15, care, după ce dequeue 12, sau după ce vom elimina 12, va devenit apoi cel mai vechi-element. 

Acum avem o așteptare pe primul elementul prin cap pointer și al doilea element prin trav pointer. Putem cap acum liber, iar apoi putem nu spun nimic mai vine înainte de 15. Deci, putem schimba 15 Înapoi pointer la punctul la nul, și ne-am muta doar capul peste. Și acolo mergem. Acum avem succes dequeued 12, iar acum ne-am o altă coadă de 4 elemente. Asta e destul de mult tot este de cozi, atât pe matrice și lista de legat pe bază de. Sunt Doug Lloyd. Aceasta este CS 50.