Doug LLOYD: Dakle, ako ste gledao video na stog, ovo je vjerojatno će se osjećati kao malo deja vu. To će vrlo sličan konceptu, samo uz blagi twist na njega. Idemo sada govoriti o redova. Pa red, slično kao stog, je druga vrsta strukture podataka da možemo koristiti za održavanje podataka u organizirani način. Slično stog, može se provoditi kao polje ili popis povezan. Za razliku od hrpe, pravila koje koristimo za određivanje kada stvari dobiti dodano i uklonjen iz red su malo drugačiji. Za razliku od hrpe koja je LIFO struktura, trajati u, prvi van, red je FIFO Struktura, FIFO, prvi u, prvi van. Sada redovima, vjerojatno ima analogiju u redu. Ako ste ikada bili u redu na zabavni park ili u banci, postoji neka vrsta pravednosti provedbenih struktura. Prva osoba u redu na banka je prva osoba tko će razgovarati s pripovjedač. 

Bilo bi vrsta utrci na dnu, ako je jedini način moraš razgovarati s pripovjedač Na banka je trebala biti posljednja osoba u redu. Svatko bi uvijek žele biti posljednja osoba u redu, a osoba koja je bila prije koji je čekao neko vrijeme, mogao biti tamo satima, i sati, a radno vrijeme prije nego što oni imaju priliku da se zapravo povući novac u banci. I tako redovi su vrsta od pravičnosti provedbu strukturu. No, to ne znači nužno da hrpe su loša stvar, samo da redovi su još jedan način da to učinite. Pa opet red je prvi, van, u odnosu na hrpu koja traje u, Prvo se. Slično stog, imamo dvije operacije da možemo izvesti na redu. Imena su u red, koji je dodati novi element na kraj reda, i dequeue, koji je ukloniti najstariji Element s prednje red. Tako ćemo dodati elemente na kraju reda, i mi ćemo ukloniti elemente s prednje red. Opet, s stog, bili smo dodavanjem Elementi na vrhu snopa i uklanjanje elemenata s vrha dimnjaka. Tako je s enqueue, to je dodao da kraj, uklanjanje s prednje strane. Dakle, najstarija stvar u tu Uvijek je sljedeća stvar izaći ako pokušamo i dequeue nešto. 

Pa opet, sa redovima, možemo implementacije array-based i povezao-lista temelji implementacije. Počet ćemo opet s implementacije array-based. Definicija struktura izgleda prilično slično. Imamo još niz Postoji tipa podataka vrijednosti, tako da može držati proizvoljne vrste podataka. Mi opet ćemo koristiti cijeli brojevi u ovom primjeru. 

I baš kao što je s našim Provedba snop niz bazi, jer smo rabeći polje, mi nužno imati taj ograničenje da je C vrsta od provodi na nas, što je i mi nemaju dinamizam u našem sposobnost da rastu i smanjiti niz. Moramo odlučiti na početku što je najveći broj stvari koje možemo staviti u ovaj red, au ovom slučaju, Kapacitet će biti neki funta definirani konstanta u našem kodu. A za potrebe ovog Video, kapacitet će biti 10. 

Moramo pratiti prednji dio red tako da znamo što je element želimo dequeue, i mi također treba pratiti nešto else-- broj elemenata da smo u našem redu. Obavijest nismo praćenje na kraju reda, samo veličina reda čekanja. A razlog za to će, nadamo se postalo malo jasnije u trenutku. Nakon što smo završili ovaj tip definicija, imamo novi tip podataka zove red, koji sada možemo proglasiti varijable te vrste podataka. I pomalo zbunjujuće, odlučio sam nazvati ovaj red q, pismo q umjesto tipa podataka q. 

Dakle, ovdje je naš red. To je struktura. Sadrži tri člana ili tri polja, niz veličina kapaciteta. U ovom slučaju, kapacitet je 10. A ovo polje je će održati prirodna broja. U zelenom je ispred naše red je Sljedeći element biti uklonjena, a crveno će biti veličine redu, koliko elementi su trenutno postoje u redu. Dakle, ako kažemo q.front jednaki 0, a veličina q.size jednak 0-- mi smo stavljajući 0s u tim područjima. I u ovom trenutku, mi smo prilično mnogo spremni za početak rada s našim red. 

Dakle, prva operacija možemo obavljaju je enqueue nešto, dodati novi element kraj reda. Pa ono što trebamo učiniti u općem slučaju? Pa ova funkcija enqueue potrebama prihvatiti pokazivač na naš red. Opet, ako je proglasio naš red na globalnoj razini, ne bi trebao to učiniti nužno, ali općenito, što moraju prihvatiti naputke strukturama podataka ovako, jer inače, mi smo u prolazu value-- smo prolazi u kopijama redu, pa nismo zapravo mijenja red koji namjeravamo mijenjati. 

Druga stvar što treba učiniti je prihvatiti element podataka odgovarajućeg tipa. Opet, u ovom slučaju, to je će biti cijeli brojevi, ali mogli proizvoljno proglasiti tip podataka kao vrijednost i koristiti to općenito. To je element koji želimo enqueue, želimo dodati na kraj reda. Tada smo zapravo žele staviti da su podaci u redu. U tom slučaju, stavljanje je u točno mjesto naše ponude, a onda želimo promijeniti veličinu u redu, koliko smo elemente trenutno imaju. 

Tako ćemo početi. Evo, opet, da je general Obrazac funkcija izjava za ono u red moglo izgledati. I ovdje mi ići. Idemo enqueue broj 28 u redu. Pa što ćemo učiniti? Pa, ispred naše red je na 0 ° C, te veličine našeg reda je na 0, i tako smo vjerojatno želite staviti broj 28 u broj polja elemenata 0, zar ne? Dakle, sada smo postavljeni da postoji. Pa sad što nam treba mijenjati? Mi ne želimo mijenjati prednji dio reda, jer želimo znati što elementa ćemo možda morati dequeue kasnije. Dakle, razlog zbog kojeg smo se ispred se je vrsta pokazatelj što je najstarija stvar u nizu. Pa najstarija stvar u array-- u Zapravo, jedina stvar u nizu u pravu now-- je 28, što je na polja lokaciji 0. Dakle, mi ne želimo promijeniti da zeleni broj, jer to je najstariji dio. Umjesto toga, želimo promijeniti veličinu. Dakle, u ovom slučaju, mi ćemo povećajte veličinu do 1. 

Sada opći vrsta ideju gdje Sljedeći element će ići u redu se dodati tih dva broja zajedno, prednji i veličina, i da ću ti reći gdje je sljedeći element u redu je ići. Dakle, sada ćemo enqueue drugi broj. Idemo u red 33. Dakle, 33 će ići u Niz položaj 0 i 1. Dakle, u ovom slučaju, to se događa ići u polja položaju 1, a sada je veličina našeg reda 2. 

Opet, mi ne mijenjamo prednji našeg reda, jer 28 je i dalje Najstariji je element, a mi Želite to-- kad smo na kraju dobiti da dequeuing, uklanjanjem elemenata iz ovog reda, želimo znati gdje je najstariji element. I tako smo uvijek treba održavati neki pokazatelj gdje je to. Dakle, to je ono što je tu za 0. To je ono ispred je tamo. 

Idemo u enqueue još jedan element, 19. Siguran sam da možete pogoditi gdje 19 će ići. To će ići u Niz položaj broj 2. To je 0 plus 2. I sada je veličina našeg reda je 3. Imamo 3 elemente u njoj. Dakle, ako smo, a nećemo upravo sada, u red još jedan element, to će ići u polja položaja broj 3, a veličina našeg reda će biti 4. Tako smo enqueued nekoliko elemenata sada. Sada ćemo početi da ih ukloniti. Idemo ih dequeue iz reda čekanja. 

Dakle, slično kao pop, koja je vrsta od analog to za dimnjaka, dequeue treba prihvatiti pokazivač na queue-- opet, osim ako je na globalnoj razini je proglašen. Sada želimo promijeniti položaj prednje reda. Ovo je mjesto gdje je vrsta u pitanju u igru, da je prednji varijabla, jer jednom uklonimo element, želimo ga premjestiti na sljedeću najstarijeg elementa. 

Zatim želimo smanjiti veličina reda, a onda želimo vratiti vrijednost koji je uklonjen iz reda. Opet, mi ne želimo samo ga odbaciti. Mi vjerojatno su vađenje to iz queue-- smo to dequeuing jer mi je stalo do nje. Dakle, želimo ova funkcija za povratak element podataka tipa vrijednosti. Opet, u ovom slučaju, vrijednost broj. 

Dakle, sada ćemo dequeue nešto. Idemo uklanjanje element iz reda čekanja. Ako kažemo int x jednak & q, znak za struju q-- opet to je pointer na ovom q podataka structure-- što je element će se dequeued? U ovom slučaju, jer je prvi u, prvi van strukture podataka, FIFO, prva stvar koju smo stavili u ovu red je 28, pa u ovom slučaju, ćemo uzeti 28 iz red, a ne 19, što je ono bismo učinili ako je to hrpa. Idemo uzeti 28 iz reda. 

Slično onome što smo učinili s stog, nismo zapravo će izbrisati 28 iz samog reda, samo ćemo se vrste od pretvarati da ne postoji. Dakle, to će ostati tamo u memoriji, ali mi smo samo ide vrsta ignorirati pomicanjem druga dva područja naše q podataka strukturu. Idemo mijenjati ispred. Q.front sada će biti 1, zato što je sada najstariji elemenat imamo u našem red, jer smo već uklonjena 28, koji je bio bivši najstariji elemenat. 

A sada, želimo promijeniti veličina reda dva elementa umjesto tri. Zapamti ranije sam rekao kad smo želite dodati elemente na red, smo ga stavili na lokaciji polja koja je zbroj prednje i veličine. Dakle, u ovom slučaju, mi smo još uvijek stavljajući to, sljedeći element u redu, u položaju 3 polja, i vidjet ćemo da je u sekundi. 

Dakle, sada smo dequeued naše Prvi element iz reda čekanja. Idemo to učiniti opet. Idemo uklanjanje drugi element iz reda. U tom slučaju, struja najstariji element je niz lokacija 1. To je ono što q.front nam govori. To zelena kutija nam govori da to je najstariji dio. I tako, x će postati 33. Mi ćemo samo vrsta zaboraviti da 33 postoji u nizu, a mi ćemo reći da danas, Novi najstariji element u redu je na položaju 2, polja i veličine u redu, broj elemenata imamo u redu, je 1. Sada enqueue nešto, a ja vrsta je dao to daleko prije sekundu, ali ako želimo staviti 40 u red, gdje je 40 će ići? Pa smo ga stavljajući u q.front plus red veličine, pa ima smisla zapravo staviti 40 ovdje. Sada primijetite da u nekom trenutku, idemo doći do kraja naš niz unutar q, ali to izblijedi iz 28 i 33-- oni su zapravo, tehnički otvoreni prostori, zar ne? I tako, možemo eventually-- to pravilo dodavanja ta dva together-- možda ćemo na kraju trebate mod po veličini kapaciteta tako da možemo omotati oko. 

Dakle, ako smo dobili na elementu broj 10, ako smo zamjenjuje ga u elementu brojem 10, što bi zapravo ga staviti u polja položaj 0. I ako su idući u Niz mjesto-- me ispričati, ako ih zbroje zajedno, i moramo broj 11 će biti u kojoj ćemo morati staviti on, koji ne postoji u ovom array-- to bi se događa izvan granica. Mogli bismo mod za 10 i staviti to u polja položaj 1. Dakle, to je kako redovi rade. Uvijek ići s lijeva na desno i eventualno zaokrenuti. A ti znaš da su oni pune veličine, ako, kako crvenoj kutiji, postaje jednak kapacitetu. I tako, nakon što smo je dodao 40 do red, i što trebamo učiniti? Pa, najstariji elemenat u redu je još uvijek 19, pa ne želimo mijenjati prednji dio reda, ali sada imamo dva elementi u redu, i tako želimo povećati Naša veličina od 1 do 2. 

To je uglavnom to s rad s redovima array-based, i slično stog, tu je i način provoditi red kao popis povezane. Sada, ako je ova vrsta struktura podataka izgleda upoznat s tobom, to je. To nije popis s pojedinačno povezani, to je popis s dvostruko povezani. I sada, kao na stranu, to je zapravo moguće provesti red kao popis za pojedinačno povezani, ali Mislim u smislu vizualizacije, to zapravo može pomoći kako bi vidjeli ovo kao popis dvostruko povezani. Ali, to je svakako moguće to što je popis za pojedinačno povezane. 

Tako ćemo imati pogled na što bi to moglo izgledati. Ako želimo enquue-- pa sad, opet smo prebacivanje na povezanom-liste temelji modela ovdje. Ako želimo u red, želimo dodati novi element, i ono što trebamo učiniti? Pa, prije svega, jer je mi smo dodajući da do kraja i uklanjanje iz početak, vjerojatno ćemo želite zadržati upućuje na obje glava i rep popisa povezane? Rep je drugi izraz za kraj popisa povezani, posljednji element u popisu povezane. A to će vjerojatno, opet, biti koristan za nas ako su globalne varijable. Ali sada, ako želimo dodati novi Element što moramo učiniti? Ono što smo upravo [? Malak?] ili dinamički izdvojiti naš novi čvor za sebe. A onda, baš kao i kada smo dodali bilo element dvostruko povezane liste mi, samo morati sortirati of-- one posljednje tri koraka ovdje samo su sve o pomicanjem upućuje na ispravan način tako da element dodaje na lanac bez razbijanje lanca ili stvaranje neke vrste pogreške ili imaju neku vrstu nesreće dogoditi pri čemu smo se slučajno siroče neke elemente našeg reda. Evo što bi to moglo izgledati. Želimo dodati element 10 do kraja ovog reda. Dakle, najstariji elemenat ovdje zastupa glavu. To je prva stvar smo stavili u tom hipotetskom red ovdje. I rep, 13, je najviše Nedavno dodano element. I tako, ako želimo u red 10 u ovaj red, želimo ga staviti nakon 13 godina. I tako ćemo dinamički izdvojiti prostor za novi čvor i provjerite null bi bili sigurni nemamo neuspjeh memorije. Onda ćemo staviti 10 u taj čvor, a sada moramo biti oprezni o tome kako organiziramo upućuje tako da ne razbiti lanac. 

Možemo postaviti 10 je prethodno polje ukazati natrag na stari rep, a od '10 će biti Novi rep u nekom trenutku u vrijeme svih tih lanci su povezani, ništa ne će doći Nakon 10 sada. I tako 10 je sljedeći pokazivač će ukazati na null, a onda nakon što smo to učinili, nakon što imamo povezano 10 unatrag lancu, možemo uzeti staru glavu, ili, oprostite ja, stari rep red. Stari kraj reda, 13, a čine ga istaknuti do 10. I sada, u ovom trenutku, imamo enqueued broj 10 u ovaj red. Sve što trebate učiniti sada je samo premjestiti Rep ukazati na 10, umjesto na 13 godina. 

Dequeuing je zapravo Vrlo slično iskakanje iz dimnjaka koji je provodi kao popis povezan Ako ste vidjeli hrpe videa. Sve što trebate učiniti je početi na početak, pronaći drugi element, oslobodi prvi element, a zatim pomaknite glavu ukazati na drugom elementu. Vjerojatno bolje da ga vizualizirati samo da bude extra jasno o tome. Dakle, ovdje je naš red opet. 12 je najstariji elemenat u našem redu, glave. 10 je najnoviji elementa u našem redu, naše rep. 

I tako, kada želimo za dequeue element, želimo ukloniti najstariji element. Dakle, što nam je činiti? Pa smo postavili obuhvaćanje pokazivač koja počinje u glavi, a mi ga premjestiti tako da ukazuje na drugi element to queue-- nešto rekavši Trav jednako Trav strelicu uz, primjerice, će preseliti Trav ima ukazati na 15, koji je, nakon što smo dequeue 12, ili nakon što smo uklonili 12, će se postati tada najstarija elementa. 

Sada imamo držite na prvi Element putem pokazivač glavu a drugi element putem pokazivač Trav. Mi sada mogu slobodno glavu, a onda možemo kažu ništa ne dolazi prije 15 više. Tako možemo promijeniti 15 prethodnih pokazivač ukazati na null, a mi samo premjestiti nad glavom. I tamo idemo. Sada smo uspješno dequeued 12, a sada smo još jedan red 4 elemenata. To je ljepušan velik dio sve tu je redovima, i niz bazi i povezani-lista temelji. Ja sam Doug Lloyd. To je CS 50.