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.