DOUG LLOYD: Beraz baduzu pila bideoa ikusi ditut,
hau da, ziurrenik, sentitzen joan deja vu pixka bat bezala.
Honez oso antzeko kontzeptu bat joan, nahikoa da bertan bira txiki bat eginez.
Orain ilarak buruz hitz egin behar izan dugu.
Beraz, ilara batean, pila bat antzekoa, Datuen egitura mota bat da
horri eutsi ezin dugu erabili modu antolatuan datuak.
Pila bat antzekoa, ezarri ahal izango da
array bat edo lotuta zerrenda bat bezala.
Pila bat bezala, arauak erabiltzen dugun zehazteko
denean gauzak gehitu eta kendu egiten urratsak ilararentzat pixka bat desberdinak dira.
>> Pila bat, ez bezala, zein LIFO egitura bat da,
iraungo, lehena inprimatu, ilara bat FIFO da egitura, FIFO, lehenengo, lehena inprimatu.
Orain ilarak, seguruenik ilarak analogia bat dute.
Duzun inoiz lerro izan bada at jolas-parke bat edo banku batean,
han zuzentasuna moduko egitura gauzatzeko.
Lehen lerroan pertsona at bankura lehen pertsona da
nork lortzen den kontalaria hitz egiten.
>> Lasterketa moduko lizateke hondoan modu bakarra bada
to at kontalaria esateko lortu duzu banku zen ildotik azken pertsona izango da.
Denek litzateke beti nahi azken pertsona izan nahi ildotik,
eta pertsona nor ez zegoen lehen nor izan zain pixka bat,
Han izan daiteke orduz, eta orduz, eta ordu
dute aukera bat benetan aurretik erretiratuko dirurik bankuan.
Eta beraz, ilarak moduko daude zuzentasuna egitura gauzatzeko.
Baina horrek ez du esan nahi pilak hori txarra dira, besterik
ilarak dela egiteko beste modu bat.
Beraz, berriro ere ilara bat da, lehen aldiz, eta lehen out, iraun ere pila bat versus,
lehen egindako.
Pila bat antzekoa, Bi operazio daukagu
ilarak izan dezakegun hori gauzatzeko.
Izen hauek enqueue dira, hau da, gehitu Ilaran amaierara arte elementu berri bat,
eta adierazten du, hau da, zaharrena kentzeko
Ilaran aurrean ere elementu.
Beraz, elementu gehitzen joan Ilaran bukaera aldera,
eta horretan ari gara elementuak kendu egingo da Ilaran aurrean ere.
Berriz ere, pila batekin, gehituz ari ginen pilaren goialdean elementu
eta elementu kendu pila goitik.
Beraz enqueue batera, egoten da gehituz Amaieran, aurrean kentzean.
Beraz, ez da gauza zaharrena Hurrengo gauza da beti
atera saiatzen bagara eta, zerbait adierazten.
>> Beraz, berriro ere, ilarak batera, ahal dugun array oinarritutako inplementazio
eta lotutako zerrenda oinarritutako inplementazio.
Hasiko gara berriro ekin array oinarritutako inplementazio.
Egitura hori definitzea nahiko antzekoa dela.
Array bat daukagu Datu mota balioaren han,
hain arbitrarioa datu motak eutsi ahal izango da.
Berriro ari gara erabili joan Adibide honetan zenbaki osoko.
>> Eta besterik ez bezala, gure array oinarritutako pila ezartzeko,
bat erabiltzen ari garelako array, nahitaez dugu
mugarik izan duten C motako of us on behartzean, hau da, ez dugu
ez duen dinamismoa dute gure hazten eta txikitu array gaitasuna.
Hasieran erabaki behar dugu zer gehienez gauzak kopurua da
hau sartu garela jarri ahal ilaran, eta kasu honetan,
ahalmena kiloko batzuk izango litzateke gure kodea konstante definitu.
Eta honetan, hitz egiteko video, ahalmena da 10 izango da.
>> Segimendua egiteko behar dugu Ilaran aurrealdean
beraz, badakigu zein elementu to Adierazten nahi dugu,
eta, era berean, segimendua egiteko behar dugu Zerbait elementu kopurua Bestela
Gure ilarako dugula.
Ohartu ez gara jarraipena Ilaran amaieraren, besterik
Ilaran tamaina.
Eta horren arrazoia, eta espero dugu Pixka bat une batean argiagoa.
Amaitu eta gero mota honen definizioa,
datu-mota berri bat daukagu bertan, orain ezin dugu ilaran deitzen,
Datu mota horretako aldagai deklaratzen.
Eta zertxobait nahastu, erabaki dut ilaran q honetan, gutun deitzeko
ordez, datu-mota q la q.
>> Hortaz, hona hemen gure ilara da.
Egitura bat da.
Hiru kide edo hiru biltzen ditu eremuak, tamaina EDUKIERA array bat.
Kasu honetan, edukiera 10 da.
Eta array hau da Osoko zenbaki eutsi behar.
Berdez gure ilara aurrean da, hurrengo elementua kendu egin behar da, eta gorriz
Ilaran tamaina izango da, zenbat elementuak dira gaur egun
Ilaran daudenik.
Q.front berdinen esan, beraz badugu 0 eta q.size tamaina berdinen 0--
0 s ari gara arlo horietan.
Eta puntu honetan, nahiko askoz gaude prest gure ilara batekin lanean hasteko.
>> Beraz, lehen operazioa ahal dugun burutu da zerbait ilaran,
Elementu berri bat gehitzeko Ilaran amaieran.
Beno, zer egin behar dugu kasu orokorra egin?
Beno, funtzio hau ilaran beharrak gure ilara erakuslea onartzeko.
Berriz ere, ez dugu bada deklaratu zuen Gure ilaran orokorrean,
ez genuke behar hori egin ahal izateko nahitaez, baina, oro har, ez dugu
erakusleak onartu behar datu egiturak
Hau atsegin, bestela delako, balioa ez gara ari gara pasatzen
Ilaran kopiak pasatzen, eta ez gara benetan aldatuz orain
Ilaran hori aldatu nahi dugu.
>> Egin behar da, beste gauza da onartu Datu motaren elementu bat.
Berriz ere, kasu honetan, ez da osokoa izan da joan,
baina arbitrarioki ezin duzu Datu motaren balio gisa deklaratzeko
eta hau erabiltzeko, oro har.
Hori ilaran nahi dugun elementua da, gehitu ilaran amaieran nahi dugu.
Ondoren dugu benetan nahi place datu horiek ilaran.
Kasu honetan, jarriz batean gure array kokapen egokia,
eta, ondoren, tamaina aldatu nahi dugu ilaran, zenbat elementu dugu
Une dute.
>> Beraz, hasi gaitezen.
Hemen da, berriz ere, oro har, hori Formulario funtzioa adierazpena
nolakoak liteke enqueue begiratzen da.
Eta hemen dugu joan.
Dezagun ilaran kopuruaren 28 ilaran sartu.
Beraz, zer egin behar dugu joan?
Beno, gure ilara aurrean da 0, eta gure ilara tamaina hartu du
0 da, eta beraz, seguraski jarri nahi dugu array elementu kopurua ere 28 zenbakira
0 da, ezta?
Beraz, orain dugu ez direla jartzen.
Beraz, gaur egun, zer aldatu behar dugu?
Guk ez dugu aldatu nahi Ilaran aurrealdean,
zer elementu jakin nahi dugulako Beranduago Adierazten behar dugu.
Beraz, arrazoia aurrean ez Zer da adierazle bat sort da
array gauzarik zaharrena.
Beno array gauzarik zaharrena ere Izan ere, array gauza bakarra eskuineko
da gaur egun, 28 da, hau da, array kokapena 0.
Beraz, ez dugu nahi zenbakia berde hori aldatu,
duten elementu zaharrena delako.
Baizik eta, tamaina aldatu nahi dugu.
Beraz, kasu honetan, dugu Kontatzailea tamaina 1era.
>> Orain bertan, ideia moduko orokor bat hurrengo elementua da ilara batean joango gara
bi zenbaki horiek gehitzeko elkarrekin, aurreko eta tamaina,
eta hori esango dizu non hurrengoan ilaran elementu da joango gara.
Beraz, gaur egun dezagun ilaran zenbaki batera.
Dezagun ilaran 33.
Beraz, 33 da sartzen joan array kokapena 0 plus 1.
Beraz, kasu honetan, joan da array kokapena 1 doaz;
eta orain gure ilara tamainaren 2 da.
>> Berriz ere, ez gara aldatzen Gure ilaran aurrealdean,
28 da oraindik delako elementu zaharrena, eta guk
Nahi zaie, azkenean lortu dugu , dequeuing elementu kendu
ilaran honetatik, jakin nahi dugu non elementu zaharrena da.
Eta beraz, beti behar dugu, mantentzeko Bertan dela adierazle batzuk.
Beraz, hori da 0 da han.
Hori aurrean zer dago egiteko.
>> Let enqueue ere aren elementu bat gehiago, 19.
Ziur asmatzen dezakezu naiz Bertan 19 da joango gara.
Honez sartzen joan array kokapena kopurua 2.
Hori da, 0 eta 2.
Eta orain, gure ilara tamainaren 3 da.
3 da elementu daukagu.
Beraz bagenu, eta ez goaz oraintxe, beste elementu bat ilaran,
array kokapena litzateke joan 3. zenbakian, eta gure ilaran tamainaren
4 litzateke.
Beraz, hainbat elementu enqueued dugu gaur egun.
Orain dezagun hasteko ezabatzea.
Dezagun Adierazten ilaran.
>> Beraz, antzeko, Pop, eta ordenatu honen analogikoa pilak egiteko,
Adierazten bat onartu behar du Ilara erakuslea berriro,
Honez globalean deklaratu ezean.
Orain kokalekua aldatu nahi dugu Ilaran aurrean.
Hau da, non sort dator jokoan sartzen, aurrean aldagai hori,
behin kendu dugulako elementu bat, nahi dugun
mugitu hurrengo elementu zaharrena da.
>> Ondoren murriztu nahi dugu Ilaran tamaina,
eta, ondoren, balio du itzuli nahi dugu Hori ilaran kendu zen.
Berriz ere, ez dugu nahi, besterik gabe baztertu da.
Zentzuzkoa erauzten ari gara Ilara gara bertatik
egiten dequeuing horri buruz zaintzen dugulako.
Beraz itzultzeko funtzio hau nahi dugu Datu mota balio elementu bat.
Berriz ere, kasu honetan, balio osokoa da.
>> Beraz, gaur egun dezagun Adierazten zerbait.
Dezagun kendu elementu bat ilaran.
Esan badugu int x berdinen & q, ampersand q-- Berriro hori q datu hau erakuslea da
structure-- zer elementu da dequeued behar da?
Kasu honetan, lehen bat delako , lehenengo datuen egitura, FIFO out,
Lehenengo gauza jarri hau sartu dugu ilaran 28 izan zen, eta, beraz, kasu honetan,
28 libratu goaz Ilaran, ez 19, hau da, zer
egin nahiko genuke hau pila bat bazegoen.
28 hartu ilaran daudelarik goaz.
>> Zer egin dugun antzekoa pila bat, ez gara benetan
28 ezabatzen joan Ilaran bertatik,
besterik ez gara nolako joan ren asmoa ez da han.
Beraz, bertan geratuko joan oroimenean, baina besterik ez gara
mota baztertu mugituz joan Gure q datuak beste bi zelaietan
egitura.
Aurrean aldatzeko goaz.
Q.front da orain joan izan 1, hau da, orain delako
du elementu zaharrena ere izan dugu gure ilaran, dugu dagoeneko kendu 28 delako,
bertan, antzinako elementu zaharrena zen.
>> Eta orain, aldatu nahi dugu Ilaran tamainaren
Hiru bi elementu ordez.
Orain gogoratzen Esan dudan dugunean elementu gehitzeko ilaran nahi,
jarri array kokapena batean bertan aurreko eta tamaina batura da.
Beraz, kasu honetan, oraindik ari gara da, ilaran hurrengo elementua,
array kokapena 3, eta sartu hori ikusiko dugu bigarren bat ere.
>> Beraz, orain dequeued dugu gure ilaratik lehen elementua.
Berriro egin dezagun.
Dezagun kendu beste ilaratik elementu.
Dagokienez, indarrean dagoen zaharrena elementu array kokapena 1 da.
Hori zer q.front kontatzen digu.
Koadro berde hori kontatzen digu duten elementu zaharrena da.
Eta beraz, x 33 izango da.
Besterik motatako ahaztu dugu duten 33 existitzen array,
eta orduan, esan dugu hori ilaran elementu zaharrena berria
array kokapena 2, eta tamainaren dago ilaran, elementu kopurua
dugun ilaran, da 1.
Orain dezagun ilaran zerbait, eta I Sort eman honen kanpoan duela bigarren,
baina 40 jarri du sartu nahi badugu ilaran, non nik 40 joango gara?
Beno dugu sido jarriz Nik q.front plus ilaran tamaina,
eta beraz, zentzuzkoa da Egia esan, 40 jarri behar da hemen.
Orain konturatu dela uneren, goazen
to amaieran iritsi q barrutik gure array,
baina hori desagertu dira 28 eta 33-- benetan ari dira, teknikoki
espazio libreak, ezta?
Eta beraz, eventually-- genezake gehituz araua argi
bi horiek, elkarrekin azkenean gaitezen mod behar ahalmena tamainaren arabera
beraz inguruan biltzea izango dugu.
>> Beraz, gero elementu dugu kopurua 10 bagaude
Horretarako, ordeztu 10 zenbakia elementu ere, genuen benetan ipini array kokapena 0 da.
Eta ari ginen joan bada array kokapen Barkatu,
horiek gehitu dugu bada elkarrekin, eta lortu dugu kopuruak
11 non jarri behar genuke izango litzateke da, eta horrek ez du array honek existitzen
egiten joatea litzateke egindako mugetatik.
Litezke 10 by mod dugu, eta jarri array kokapena 1 da.
Beraz, hori da ilarak nola lan egiten.
Beti ari dira Ezkerretik joango eskubidea eta seguru inguruan biltzeko.
Eta badakizu ari dira tamaina bada osoa, koadro gorri horretan,
ahalmen berdina bihurtzen.
Eta gehitu hain ondoren dugu 40 arte ilaran, bai, zer egin behar dugu?
Beno, elementu zaharrena Ilaran 19 da oraindik,
beraz, ez dugu aldatu nahi Ilaran aurrealdean,
baina orain bi ditugu ilaran elementuak,
eta, beraz, handitu nahi dugu Gure 1etik 2ra tamaina.
>> Hori nahiko askoz berarekin array oinarritutako ilarak lanean,
eta pilatu antzeko, ez da ere modu bat
ilararentzat lotutako zerrenda bat martxan jarri ahal izateko.
Orain datu-egitura mota hau bada Itxura duzu ezagutzen, hau da.
Ez da banaka lotuta zerrenda bat da, Bi aldiz lotuta zerrenda bat da.
Eta orain, bat alde batera utzita, ez da benetan posible den ezartzeko
ilararentzat banaka lotuta zerrenda bat bezala, baina Uste bisualizazio terminoetan I,
benetan den ikusteko lagundu dezake Bi aldiz lotuta zerrenda gisa honetan.
Baina, zalantzarik gabe, posible al da Horretarako banaka lotuta zerrenda bat bezala.
>> Hargatik begirada bat zer hori itxura.
To enquue-- nahi badugu beraz, orain, berriz ere gaude
lotutako zerrenda bat aldatu Eredu hemen.
To ilaran nahi badugu, nahi dugun Elementu berri bat gehitzeko, bai
zer egin behar dugu?
Beno, lehenik eta behin, zeren amaieran ari gara gehituz
eta kentzean hasita, ziurrenik dugu
bi erakusleak mantendu nahi Burua eta lotuta zerrendaren buztana?
Buztana epe bat izateaz lotuta zerrendaren amaieran,
lotuta zerrendan azken elementua.
Eta horiek ziurrenik, berriro, izan guretzat onuragarria
aldagai global badira.
Baina orain, bada berri bat gehitu nahi dugu elementu, zer egin behar dugu?
Zer besterik ez dugu [? Malak?] edo dinamikoki gure nodo berria esleitu geure buruari.
Eta gero, besterik ez denean edozein gehitzen badiogu Bi aldiz lotuta zerrenda dugu bat elementu,
besterik of-- ordenatzeko dute horiek azken hiru urrats hemen
besterik ez dira guztiak mugituz buruz modu egokian erakusleak
beraz elementua lortzen gehitu kate hautsi gabe kateko
edo akats nolabaiteko egiteko edo istripu nolabaiteko beharrik
gertatuko zeinaren dugu ustekabean gure ilaran elementu batzuk umezurtz.
Hona hemen zer hori itxura.
Elementua gehitu nahi dugu 10 ilaran honen amaierara arte.
Du elementu zaharrena hemen So burua ordezkatuta.
Hori da lehenengo gauza jarri genuen erantzuna hipotetiko ilaran hau hemen sartu.
Eta buztana, 13, da gehien Azkenaldian gehitutako elementu.
Eta beraz, 10 ilaran sartu nahi badugu ilara hau, jarri nahi 13 ondoren nahi dugu.
Eta horrela goaz dinamikoki esleitu espazioa nodo berri bat
eta nulua ziur egiteko dagoen egiaztatu ez dugu memoria porrot bat izan.
Ondoren goaz place 10 nodo horretan sartu,
eta orain kontu handiz ibili behar dugu erakusleak nola antolatzen ditugun buruz
beraz, ez dugu katea hausteko.
>> 10 aurreko eremu ezarri ahal izango ditugu, Atzera seinalatu zaharra buztana,
eta '10 geroztik izango da uneren buztana berria
garai horietan guztietan arabera kateak konektatuta daude,
ezer ez da etorriko joan 10 ondoren oraintxe.
Eta beraz, 10 hurrengo erakuslea null seinalatu egingo,
eta, ondoren, hau egin dugu ondoren, behar dugu eta ondoren 10 atzeraka konektatutako katean,
zaharra burua, edo, aitzakia hartu ahal izango dugu Niri, ilaran buztana zaharrean.
Ilara amaieran zaharrean, 13 eta 10 puntu ditu.
Eta orain, puntu honetan, ez dugu 10 zenbakia enqueued ilaran honetan sartu.
Orain egin behar dugun besterik ez da mugitu buztana 10 13 ordez seinalatu.
>> Dequeuing da benetan Popping oso antzekoak
Hori da pila bat lotutako zerrenda moduan eginda
pilak bideoa ikusi dut bada.
Egin behar duguna da zenbait hasteko hasita, bigarren elementua aurkitzeko,
lehen elementua askatzeko, eta gero, burua mugitu
den bigarren elementu seinalatu.
Seguruenik hobeto ikusmenarekin besterik estra dela argi izan.
Beraz, hemen da berriro gure ilaran.
12 elementurik zaharrena da Gure ilaran, buruan.
10 elementu berriena da Gure ilaran, gure buztana ere.
>> Eta beraz, nahi dugu elementu bat, adierazten du,
elementu zaharrena kendu nahi dugu.
Beraz, zer egiten dugu?
Beno zeharkako erakuslea ezarri dugu Hori buruan hasten da,
eta mugitu dugu, beraz, bigarren elementu puntu
honen Ilara zerbait trav esanez berdinen hurrengo gezi trav, adibidez,
trav mugituko litzateke ez den seinalatuko 15, eta bertan, adierazten dugu 12 ondoren,
edo kentzen dugu ondoren 12, izango elementu orduan zaharrena bihurtu.
>> Orain lortu dugu sotoan bat lehenean elementu erakuslea buruan bidez
eta bigarren elementu erakuslea trav bidez.
Eta, ondoren, ezin dugu burua orain askatu ahal izango dugu, esan ezer 15a baino lehen orduan jada.
Beraz aldatzeko aukera izango dugu 15 aurreko erakuslea null seinalatu,
eta burua mugitzen gara pasatxo.
Eta ez dugu joan.
Orain arrakastaz daukagu dequeued 12, eta orain dugu
4 elementuak ilaran beste bat izan.
Hori nahiko askoz guztiak ez ilarak da,
bi array-oinarritutako eta lotutako zerrenda oinarrituta.
Naiz Doug Lloyd.
Hau CS 50 da.