DOUG Lloyd: Pra, nëse ju keni shikuar video në rafte,
kjo është ndoshta do të ndihen si një pak e deja vu.
Është duke shkuar në një koncept shumë të ngjashme, vetëm me një kthesë të vogël në të.
Ne do të flasim tani për rradhë.
Pra, një radhë, të ngjashme me një pirg, është një tjetër lloj i strukturës së të dhënave
që ne mund të përdorim për të ruajtur të dhënat në mënyrë të organizuar.
Ngjashëm me një pirg, kjo mund të realizohet
si një grup ose një listë e lidhur.
Ndryshe nga një pirg, rregullat që ne përdorim për të përcaktuar
kur gjërat merrni shtuar dhe hequr nga një radhë janë pak të ndryshme.
>> Ndryshe nga një pirg, e cila është një strukturë LIFO,
zgjasë në, nga e para, një radhë është një FIFO Struktura, FIFO, së pari në, nga e para.
Tani rradhë, ju ndoshta kanë një analogji me rradhë.
Nëse ju keni qenë ndonjëherë në përputhje me një amusement park ose në një bankë,
nuk është lloj i një drejtësisë zbatimin e strukturës.
Personi i parë në përputhje me banka është personi i parë
i cili merr për të folur me tregimtar.
>> Ajo do të jetë lloj i një gare në fund, nëse e vetmja mënyrë
ju mori për të folur me tregimtar më së banka do të ishte personi i fundit në linjë.
Gjithkush do të duan gjithmonë të jetë personi i fundit në linjë:
dhe personi i cili ishte atje në fillim i cili ka qenë duke pritur për një kohë,
mund të jetë atje për orë të tëra, dhe orë dhe orë
para se ata kanë një shans për të vërtetë tërheqë ndonjë para në bankë.
Dhe kështu radhët e gjata janë lloj i ndershmërisë zbatimin e strukturës.
Por kjo nuk do të thotë se oxhaqet janë një gjë e keqe, vetëm
se radhët e gjata janë një mënyrë për të bërë atë.
Pra, përsëri një radhë është i pari në, së pari jashtë, kundrejt një pirg i cili zgjatë në,
për herë të parë jashtë.
Ngjashëm me një pirg, ne kemi dy operacione
që ne mund të kryejnë në radhët e gjata.
Emrat janë enqueue, e cila është për të shtuar një element i ri në fund të radhë,
dhe dequeue, i cili është për të hequr më i vjetër
element nga frontin e radhë.
Pra, ne jemi duke shkuar për të shtuar elemente të në fund të radhë,
dhe ne jemi duke shkuar për të hequr elementet nga frontin e radhë.
Përsëri, me rafte, ne ishim duke shtuar elemente majë të pirg
dhe elementët largimin nga maja e pirg.
Pra me enqueue, ajo është shtuar në në fund, duke hequr nga e para.
Pra, gjëja e vjetër në atje është gjithmonë gjë tjetër
për të dalë nëse ne përpiqemi dhe dequeue diçka.
>> Pra, përsëri, me rradhë, ne mund të Implementimi array-bazuar
dhe lidhur-lista Implementimi i bazuar.
Ne do të fillojë përsëri me array-bazuar Implementimi.
Struktura Përkufizimi duket goxha i ngjashëm.
Ne kemi një tjetër rrjet nuk e vlerës së të dhënave tipit,
kështu që ai mund të mbajë lloje të të dhënave arbitrare.
Ne jemi duke shkuar për të përdorur përsëri integers në këtë shembull.
>> Dhe ashtu si me tonë Zbatimi rafte array-bazë,
sepse ne jemi duke përdorur një grup, ne domosdo
kanë atë kufizim që lloji C i zbaton mbi ne, i cili është ne
nuk kanë ndonjë dinamizëm në tonë aftësia për të rritet dhe tkurret array.
Ne duhet të vendosin në fillim çfarë është numri maksimal i gjërave
që ne mund të vënë në këtë radhë, dhe në këtë rast,
Kapaciteti do të ketë disa kile përkufizuar konstante në kodin tonë.
Dhe për qëllime të këtij Video, kapaciteti do të jetë 10.
>> Ne duhet të mbajnë gjurmët e e përparme e radhë
kështu që ne e dimë që elementi ne duam të dequeue,
dhe ne gjithashtu duhet të mbajnë gjurmët e diçka else-- numrin e elementeve
që ne kemi në radhë tonë.
Vini re ne nuk jemi mbajtja në fund të radhë, vetëm
madhësia e radhë.
Dhe arsyeja për këtë do të shpresojmë se të bëhet një pak më të qartë në një moment.
Pasi ne kemi përfunduar ky përkufizim lloj,
ne kemi një lloj të ri të dhënave quajtur radhë, të cilat ne mund të tani
deklarojnë variablave të atij lloji të dhënave.
Dhe disi çudi, unë kam vendosur për të thirrur këtë q radhë, letra
q në vend të tipit të dhënave q.
>> Kështu që këtu është radhë ynë.
Kjo është një strukturë.
Ajo përmban tre anëtarë apo tre fusha, një grup prej madhësisë kapacitetit.
Në këtë rast, kapaciteti është 10.
Dhe kjo grup është do të mbajë integers.
Në gjelbër është front i radhë tonë, element tjetër për të hequr, dhe në të kuqe
do të jetë madhësia e radhë, Sa elemente janë aktualisht
ekzistuese në radhë.
Pra, nëse ne themi barabartë q.front 0, dhe madhësia q.size barabartë 0--
ne jemi duke 0s në këto fusha.
Dhe në këtë pikë, ne jemi shumë e shumë gati për të filluar punën me radhë tonë.
>> Pra, operacioni i parë që ne mund të kryejnë është të enqueue diçka,
për të shtuar një element të ri për fundi i radhë.
E pra çfarë kemi nevojë për të të bëjë në rastin e përgjithshme?
E pra ky funksion enqueue nevojat të pranojë një tregues për radhë tonë.
Përsëri, në qoftë se ne e kishte deklaruar radhë tona globalisht,
ne nuk do të ketë nevojë për të bërë këtë domosdoshmërisht, por në përgjithësi, ne
duhet të pranojnë pointers në strukturat e të dhënave
si kjo, sepse përndryshe, ne jemi duke kaluar nga value-- ne jemi
duke kaluar në kopje të radhë, dhe kështu ne nuk jemi të vërtetë ndryshuar
radhë që ne kemi ndërmend të ndryshojë.
>> Gjë tjetër që duhet të bëni është të pranojë një element të dhënat e llojit të përshtatshme.
Përsëri, në këtë rast, është do të jetë e integers,
por ju mund të në mënyrë arbitrare të deklarojë llojin e të dhënave si vlerë
dhe të përdorin këtë në përgjithësi.
Ky është elementi që ne duam të enqueue, ne duam për të shtuar në fund të rreshtit.
Pastaj ne të vërtetë duan të vendosni se të dhënat në radhë.
Në këtë rast, duke e vendosur atë në vendndodhja e saktë e array tonë,
dhe pastaj ne duam të ndryshojmë madhësinë e radhë, sa elemente ne
aktualisht kanë.
>> Pra, le të ketë filluar.
Këtu është, përsëri, se i përgjithshëm deklaratë funksion formë
për atë që enqueue mund të duket si.
Dhe këtu ne do të shkojmë.
Le të enqueue numrin 28 në radhë.
Pra, çfarë do të shkojmë të bëjmë?
E pra, para së radhës tonë është në 0, dhe madhësia e radhës tonë
është në 0, dhe kështu që ne ndoshta dëshironi të vënë numri 28 në array numër element
0, e drejtë?
Pra, ne kemi vendosur tani se në atje.
Kështu që tani ajo që nuk kemi nevojë për të ndryshuar?
Ne nuk duam të ndryshojmë e përparme e radhë,
sepse ne duam të dimë se çfarë element ne mund të kenë nevojë për të dequeue më vonë.
Pra, arsyeja që ne kemi front atje është lloj i një tregues i asaj që është
gjëja më i vjetër në rrjet.
E pra gjëja më i vjetër në array-- në fakt, e vetmja gjë në rrjet e drejtë
tani, është 28, i cili është në array vend të 0.
Pra, ne nuk duam të ndryshojë këtë numër të gjelbër,
sepse kjo është elementi më i vjetër.
Përkundrazi, ne duam të ndryshojmë madhësinë.
Pra, në këtë rast, ne do të ardhura madhësinë në 1.
>> Tani një lloj i përgjithshëm i idesë së, ku element tjetër do të shkojë në radhë
është për të shtuar këto dy numra së bashku, para dhe madhësia,
dhe që do të ju tregojnë se ku tjetër element në radhë do të shkojë.
Pra, tani le të enqueue një numër tjetër.
Le të enqueue 33.
Pra, 33 do të shkojë në array vendndodhjen 0 plus 1.
Pra, në këtë rast, ajo do për të shkuar në array lokacioni 1,
dhe tani madhësia e radhës tonë është 2.
>> Përsëri, ne nuk jemi duke ndryshuar pjesa e përparme e radhë sonë,
sepse 28 është ende element i vjetër, dhe ne
dua to-- kur ne përfundimisht të merrni të dequeuing, duke hequr elemente
nga kjo radhë, ne duam të dimë ku elementi më i vjetër është.
Dhe kështu që ne gjithmonë duhet të ruajë disa tregues se ku është.
Pra, kjo është ajo që është atje për 0.
Kjo është ajo që është atje për front.
>> Le në enqueue një element më shumë, 19.
Unë jam i sigurt që ju mund të me mend ku 19 do të shkojë.
Ajo do të shkojë në Grup lokacioni numër 2.
Kjo është 0 plus 2.
Dhe tani madhësia e radhës tonë është 3.
Ne kemi 3 elemente në të.
Pra, nëse ne do të, dhe ne nuk jemi duke shkuar për tani, enqueue një element tjetër,
ai do të shkojë në vend array numër 3, dhe madhësia e radhës tonë
do të jetë 4.
Pra, ne kemi enqueued disa elemente tani.
Tani le të fillojë për të hequr ato.
Le dequeue ato nga radhë.
>> Pra, të ngjashme me pop, e cila është lloj i analogut te ky për kollonat,
dequeue duhet të pranojë një tregues të queue-- përsëri,
përveç nëse është e deklaruar në nivel global.
Tani ne duam të ndryshojmë vendndodhjen i frontin e radhë.
Kjo është ku ai lloj i vjen në lojë, se ndryshueshme front,
sepse sapo kemi hequr një element, ne duam
për të lëvizur atë që elementi i vjetër tjeter.
>> Atëherë ne duam që të ulet madhësia e radhë,
dhe pastaj ne duam të kthehen vlerën që u hoq nga radhë.
Përsëri, ne nuk duam të vetëm hidhni atë.
Ne me sa duket jemi të nxjerrë ajo nga queue-- ne jemi
dequeuing atë, sepse ne kujdesemi për të.
Pra, ne duam që ky funksion të kthehen një element të dhëna me vlerë të tipit.
Përsëri, në këtë rast, vlera është numër i plotë.
>> Pra, tani le të dequeue diçka.
Le të hequr një element nga radhë.
Nëse themi int x është e barabartë dhe q, simbol q-- përsëri kjo është një tregues për këto të dhëna q
structure-- çfarë element do të jetë dequeued?
Në këtë rast, sepse kjo është një e parë në, së pari jashtë strukturën e të dhënave, FIFO,
gjëja e parë që ne kemi vënë në këtë radhë ishte 28, dhe kështu që në këtë rast,
ne jemi duke shkuar për të marrë 28 nga radhë, jo 19, e cila është ajo
ne do të kishte bërë nëse kjo ishte një pirg.
Ne jemi duke shkuar për të marrë 28 nga radhë.
>> Ngjashme me atë që ne e bëmë me një pirg, ne nuk jemi në fakt
do të fshini 28 nga radhë vetë,
ne jemi vetëm duke shkuar për të llojit të pretendojë se nuk është atje.
Kështu ajo do të qëndrojë atje në kujtesë, por ne jemi vetëm
duke shkuar për të lloj të injorojë atë duke lëvizur dy fusha të tjera të të dhënave tona q
Struktura.
Ne jemi duke shkuar për të ndryshuar para.
Q.front tani është duke shkuar për të jetë 1, sepse kjo është tani
elementi më i vjetër që kemi në tonë radhë, sepse ne kemi hequr tashmë 28,
e cila ishte elementi ish vjetër.
>> Dhe tani, ne duam të ndryshojmë madhësia e radhës
për dy elemente në vend të tre.
Tani mos harroni kam thënë më parë, kur ne doni të shtoni elemente në radhë,
ne kemi vënë atë në një vend array cila është shuma e para dhe të madhësisë.
Pra, në këtë rast, ne jemi ende duke vënë ajo, elementi tjetër në radhë,
në array vend 3, dhe ne do të shohim se në një të dytë.
>> Pra, ne kemi dequeued tani tonë Elementi i parë nga radhë.
Le ta bëjmë atë përsëri.
Le të largojë një tjetër element nga radhë.
Në rast, aktual vjetër element është array vend 1.
Kjo është ajo që q.front na tregon.
Kjo kuti e gjelbër na tregon se kjo është elementi më i vjetër.
Dhe kështu, x do të bëhet 33.
Ne vetëm do lloj i harrojmë se 33 ekziston në grup,
dhe ne do të themi se për tani, element i ri i vjetër në radhë
është në vend të vargut 2, dhe madhësinë e radhë, numri i elementeve
ne kemi në radhë, është 1.
Tani le të enqueue diçka, dhe unë lloj i dha kësaj larg një të dytë më parë,
por në qoftë se ne duam të vënë 40 në të radhë, ku është 40 do të shkojë?
E pra ne kemi qenë vënë atë në q.front plus radhë madhësi,
dhe kështu që ka kuptim për në fakt për të vënë 40 këtu.
Tani vini re se në disa pika, ne jemi duke shkuar
për të marrë në fund të array tonë brenda q,
por që venitur nga 28 dhe 33-- ata janë në fakt, teknikisht
hapësira të hapura, e drejtë?
Dhe kështu, ne mund të eventually-- se sundimi i shtuar
ata të dy together-- ne mund përfundimisht duhet të MM nga madhësia e kapaciteteve
kështu që ne mund të përfundojë rreth.
>> Pra, në qoftë se ne të merrni për elementin numër 10, në qoftë se ne jemi
zëvendësuar atë në element numër 10, ne do të në fakt e vënë atë në vend array 0.
Dhe në qoftë se ne ishim duke shkuar për të Grup location-- më falni,
nëse kemi shtuar ato së bashku, dhe kemi marrë në numrin
11 do të jetë aty ku ne do të duhet për të vënë kjo, e cila nuk ekziston ne kete array--
kjo do të shkojnë jashtë caqeve.
Ne mund të mod me 10 dhe vënë në array vend të 1.
Pra, kjo është se si punojnë rradhë.
Ata janë gjithmonë do të shkojnë nga e majta në të djathtë dhe ndoshta të përfundojë rreth.
Dhe ju e dini se ata janë të nëse me permasa të plota, se kuti të kuqe,
bëhet e barabartë me kapacitetin.
Dhe kështu pasi ne kemi shtuar 40 të radhë, dhe çfarë duhet të bëjmë?
E pra, elementi më i vjetër në radhë është ende 19,
kështu që ne nuk duam të ndryshojmë e përparme e radhë,
por tani ne kemi dy elementet në radhë,
dhe kështu ne duam të rritur madhësia tonë nga 1 deri në 2.
>> Kjo është shumë e shumë atë me duke punuar me rradhë array-bazë,
dhe të ngjashme me rafte, ka edhe një mënyrë
për të zbatuar një radhë si një listë e lidhur.
Tani në qoftë se ky lloj Struktura e të dhënave duket të njohura për ju, ajo është.
Kjo nuk është një listë e lidhur në formë individuale, kjo është një listë e lidhur dyfish.
Dhe tani, si një mënjanë, ajo është në fakt e mundur për të zbatuar
një radhë si një listë e lidhur në formë individuale, por Unë mendoj se në aspektin e vizualizimi,
ai në fakt mund të ndihmojë për të parë këtë si një listë e lidhur dyfish.
Por kjo është padyshim e mundur për e bëjnë këtë si një listë e lidhur në formë individuale.
>> Pra, le të kemi një vështrim në çfarë kjo mund të duket si.
Në qoftë se ne duam të enquue-- kështu që tani, përsëri ne jemi
kalimi te një i lidhur-listë model të bazuar këtu.
Në qoftë se ne duam të enqueue, ne duam për të shtuar një element të ri, dhe
çfarë duhet të bëjmë?
E pra, para së gjithash, për shkak se ne jemi duke shtuar në fund
dhe largimin nga fillimi, ne ndoshta
duan të ruajnë pointers për të dyja koka dhe bishti i listës të lidhura?
Bishti qenit një term tjetër për në fund të listës të lidhura,
elementi i fundit në lista e lidhur.
Dhe këto do të ndoshta, përsëri, të jetë e dobishme për ne
nëse ata janë variabla globale.
Por tani në qoftë se ne duam të shtoni një të ri element çfarë ne duhet të bëjmë?
Ajo që ne vetëm [? malak?] apo dinamike ndajë nyjen tonë të ri për veten.
Dhe pastaj, ashtu si kur ne të shtoni ndonjë element për një listë ne e lidhur dyfish,
vetëm duhet për të zgjidhur of-- këto tre hapa të fundit këtu
janë vetëm në lidhje me të gjithë duke lëvizur pointers në mënyrë korrekte
kështu që elementi merr shtuar në zinxhiri pa thyer zinxhirin
ose për të bërë një lloj të gabimit ose që kanë disa lloj aksidenti
ndodhë ku ne rastësisht jetim disa elemente të radhë sonë.
Ja se çfarë kjo mund të duket si.
Ne duam të shtoni elementin 10 deri në fund të këtij radhë.
Pra, elementi më i vjetër këtu përfaqësohet nga kokës.
Kjo është gjëja e parë që ne kemi vënë në këtë radhë hipotetik këtu.
Dhe bisht, 13, është më kohët e fundit shtuar element.
Dhe kështu që në qoftë se ne duam të enqueue 10 në këtë radhë, ne duam të vënë atë pas 13.
Dhe kështu që ne jemi duke shkuar për dinamike ndajë hapësirë ​​për një nyje të re
dhe kontrolloni për null që të sigurohemi ne nuk kemi një dështim kujtesës.
Pastaj ne jemi duke shkuar për vendin e 10 në atë nyje,
dhe tani ne duhet të jemi të kujdesshëm për mënyrën se si ne organizimin pointers
kështu që ne nuk e thyejnë zinxhirin.
>> Ne mund të vendosni fushë mëparshëm 10 s për pikë përsëri në bisht të vjetër,
dhe që nga viti '10 do të jetë bisht i ri në disa pika
me kohë të gjitha këto zinxhirët janë të lidhura,
asgjë nuk do të vijë pas 10 tani.
Dhe kështu tregues tjetër 10-së do të tregojnë për null,
dhe pastaj pasi e bëjmë këtë, pasi ne kemi 10 lidhur prapa me zinxhir,
ne mund të marrë kreun e vjetër, ose, justifikim mua, bishti i vjetër i radhë.
Fundi i vjetër i radhë, 13, dhe të bëjë atë pikë në 10.
Dhe tani, në këtë pikë, ne kemi enqueued numrin 10 në këtë radhë.
Të gjithë ne duhet të bëjmë tani është vetëm të lëvizur bisht për pikë në 10 në vend të 13.
>> Dequeuing është në fakt shumë e ngjashme me popping
nga nje pirg që është zbatohet si një listë të lidhura
në qoftë se ju keni parë videon oxhaqet.
Të gjithë ne duhet të bëni është të fillojë në nivel duke filluar, gjetur elementin e dytë,
pa elementin e parë, dhe pastaj të lëvizë kokën
për të vënë në elementin e dytë.
Ndoshta më mirë të kujtoj atë vetëm të jenë tepër të qarta në lidhje me të.
Kështu që këtu është radhë ynë përsëri.
12 është elementi më i vjetër në radhë tonë, kokë.
10 është elementi më i ri në radhë tonë, bisht tonë.
>> Dhe kështu kur ne duam një element të dequeue,
ne duam të hequr elementin më të vjetër.
Pra, çfarë bëjmë ne?
E pra ne kemi vendosur një akrep traversal që fillon në krye,
dhe ne e lëvizin atë në mënyrë që ajo vë në elementin e dytë
e kjo queue-- diçka duke thënë trav është e barabartë me Trav shigjetë tjetër, për shembull,
do të shkojë trav atje që të tregojnë për 15, e cila, pas ne dequeue 12,
ose pasi kemi hequr 12, do të të bëhet element i atëhershëm i vjetër.
>> Tani ne kemi marrë një të mbajë në ditën e parë Elementi nëpërmjet kokë akrep
dhe elementi i dytë nëpërmjet trav akrep.
Ne mund kokën tani të lirë, dhe pastaj ne mund të thonë se asgjë nuk vjen para 15 më.
Pra, ne mund të ndryshojmë 15 e mëparshme tregues të tregojnë për null,
dhe ne vetëm lëvizin kokën gjatë.
Dhe atje ne do të shkojmë.
Tani ne kemi sukses dequeued 12, dhe tani ne
kanë një radhë prej 4 elementeve.
Kjo është shumë e shumë të gjithë ka për radhët e gjata,
edhe array-bazuara dhe të lidhura-lista e bazuar.
Unë jam Doug Lloyd.
Kjo është CS 50.