DOUG LLOYD: Do se vi havas spektis la videon sur pilo, Tio estas verŝajne iranta senti kiel iomete de deja vu. Ĝi tuj tre simila koncepto, nur kun eta tordaĵo sur ĝi. Ni tuj parolos nun pri atendovicoj. Do atendovico, simila al pilo, Estas alia speco de datumstrukturo ke ni povas uzi por subteni datumoj en organizita maniero. Similaj al pilo, ĝi povas esti realigita kiel tabelo aŭ ligillisto. Kontraste stako, la reguloj ke ni uzos por determini kiam aĵoj get aldonis kaj forigis de atendovico estas iomete malsamaj. Kontraste pilo, kiu Estas LIFO strukturo, daŭri en, unue eksteren, atendovico estas FIFO strukturo, FIFO, unua en, unua el. Nun vostoj, vi probable havas analogion al atendovicoj. Se vi iam estis en linio je amuzparko aŭ ĉe banko, ekzistas ia justeco efektivigado strukturo. La unua persono en linio je la banko estas la unua persono Kiu akiras paroli al la kasisto. 

Estus ia raso al la fundo, se la sola maniero vi devas paroli al la kasisto ĉe la banko estis esti la lasta persono en linio. Cxiuj estus ĉiam volas esti la lasta persono en linio, kaj la persono kiu estis tie unua kiu estis atendante por momento, povus esti tie por horoj, kaj horoj kaj horoj antaŭ ol ili havas ŝancon reale retiri monon en la banko. Kaj tiel vostoj estas ia la justeco efektivigado strukturo. Sed tio ne nepre signifas ke stakoj estas malbona afero, nur ke vostoj estas alia maniero por fari ĝin. Do denove atendovico estas unua en, unua eksteren, kontre pilo kiu daŭras en, unua el. Similaj al pilo, ni havos du operacioj ke ni povas realigi sur vostoj. La nomoj estas enqueue, kiu estas aldoni nova elemento al la fino de la vico, kaj dequeue, kiu estas forigi la malnova elemento de la fronto de la atendovico. Do ni tuj aldonu elementoj sur la fino de la vico, kaj ni tuj forigos elementoj de la fronto de la atendovico. Denove kun la pilo, ni estis aldono elementoj al la supro de la stako kaj forigado elementoj De la supro de la stako. Do kun enqueue, ĝi estas aldono al Fine apartigu el la fronto. Do la plej malnova afero tien estas ĉiam la sekva afero eliri se ni provas kaj dequeue ion. 

Do denove, kun vostoj, ni povas tabelo-bazita implementaciones kaj ligitaj listo bazita implementaciones. Ni komencu denove kun tabelo-bazita implementaciones. La strukturo difino aspektas sufiĉe simila. Ni havas alian tabelo tie de datumtipo valoro, do ĝi povas teni arbitra datumtipoj. Ni denove uzos entjeroj en tiu ekzemplo. 

Kaj ĝuste kiel kun niaj tabelo-bazita pilo efektivigo, ĉar ni uzas la tabelo, ni nepre havas tiun limigon ke C speco de efikigas sur nin, kio estas ni ne havas dinamismo en nia kapablo kreski kaj ŝrumpi la tabelo. Ni devas decidi komence kio estas la maksimuma nombro de aferoj ke ni povas meti en tiun atendovico, kaj en tiu kazo, kapablo estus iu funto difinita konstanto en nia kodo. Kaj por la celoj de ĉi tiu vídeo, kapablo tuj estos 10. 

Ni devas sekvigi la fronto de la atendovico tial ni scias ke elemento ni volas dequeue, kaj ni ankaŭ devas teni trako de io else-- la nombro de elementoj ke ni havas en nia vosto. Rimarku ni ne konservanta trako de la fino de la vosto, same la grandeco de la vosto. Kaj la kialo por ke espereble fariĝis iom pli klara en momento. Unufoje ni kompletigis tiu tipo difino, ni havas novan datumtipo nomata vosto, kiun ni povas nun deklari variablojn de tiu datumtipo. Kaj iom konfuze, mi decidis nomi tiun atendovico q, la letero q anstataŭ la datumtipo q. 

Do tie estas nia vico. Estas strukturo. Ĝi enhavas tri membroj aŭ tri kampoj, tabelo de grandeco kapablo. En tiu kazo, kapablo estas 10. Kaj ĉi tabelo estas tenos entjeroj. Verde estas la fronto de niaj vosto, la sekva elemento esti forigita, kaj en ruĝa estos la grandeco de la vosto, kiom da elementoj nuntempe ekzistantaj en la vico. Do se ni diras q.front egaluloj 0, kaj q.size grandeco egalas 0-- ni metante _0s_ en tiuj kampoj. Kaj je tiu punkto, ni estas preskaux pretas komenci laboranta kun niaj vosto. 

Do la unua operacio eblan elfari estas enqueue ion, aldoni novan elementon al la fino de la vico. Nu kion ni bezonas plenumi en la ĝenerala kazo? Nu tiu funkcio enqueue bezonoj akcepti puntero al nia vosto. Denove, se ni klariginte nia vico tutmonde, ni ne bezonas fari tion nepre, sed en ĝenerala, ni bezonas akcepti punteros al datumstrukturoj tiel, ĉar alie, ni preteriras value-- ni estas pasante en kopioj de la atendovico, kaj do ni ne efektive ŝanĝanta la vosto kiu ni intencas ŝanĝi. 

La alia afero bezonas fari estas akcepti datuma elemento de la konvena tipo. Denove, en tiu kazo, ĝi estas tuj estos entjeroj, sed vi povus arbitre deklari la datumtipo kiel valoro kaj uzi tiun pli ĝenerale. Tio estas la elemento ni volas enqueue, Ni volas aldoni al la fino de la vico. Tiam ni efektive volas meti ke datumoj en la vico. En tiu kazo, metante ĝin en la korekta loko de nia tabelo, kaj tiam ni volas ŝanĝi la grandecon de la atendovico, kiom da eroj ni aktuale havas. 

Do ni komencu. Jen, denove, ke ĝenerala formo funkcio deklaro por kio enqueue povus aspekti. Kaj tie ni iru. Ni enqueue la nombro 28 en la vico. Do kion ni faros? Nu, la fronto de niaj atendovico estas je 0, kaj la grandeco de nia atendovico estas je 0, kaj tial ni probable volas meti la numero 28 en tabelo elemento nombro 0, dekstra? Do ni nun metis tiun en tie. Do nun kion ni devas ŝanĝi? Ni ne volas ŝanĝi la fronto de la atendovico, ĉar ni deziras scii kion elemento Ni eble bezonas dequeue poste. Do la kialo ni havas antaux tie estas ia indikilo de kio estas la plej malnova aĵo en la tabelo. Nu la plej malnova aĵo en la tabelo en Fakte, la sola afero en la tabelo dekstra now-- estas 28, kiu estas ĉe tabelo ĉelo 0. Do ni ne volas ŝanĝi tiun verdan numeron, ĉar tio estas la plej malnova elemento. Prefere, ni volas ŝanĝi la grandecon. Do en ĉi tiu kazo, ni devos pliigo grandeco al 1. 

Nun ĝeneralan ian ideon de kie la sekva elemento tuj iros en atendovico estas aldoni tiujn du nombroj kune, fronto kaj grandeco, kaj tio diros al vi kie la sekva elemento en la vico tuj iros. Do nun ni enqueue alian numeron. Ni enqueue 33. Do 33 tuj iri en tabelo ĉelo 0 plus 1. Do en ĉi tiu kazo, ĝi tuj enirontajn en tabelo situon 1, kaj nun la grandecon de nia vosto estas 2. 

Denove, ni ne ŝanĝas la fronto de niaj vosto, ĉar 28 estas ankoraŭ la malnova elemento, kaj ni volas to-- kiam ni eventuale akiri al dequeuing, forigante elementojn de tiu vosto, ni volas scii kie la plej malnova elemento estas. Kaj do ni ĉiam devas subteni iu indikilo de kie tiu estas. Do jen kion la 0 estas tie por. Tion fronto estas tie por. 

Ni en enqueue pli elemento, 19. Mi certas ke vi povas diveni kie 19 estas iranta iri. Ĝi tuj iri en tabelo situon numero 2. Tio 0 plus 2. Kaj nun la grandecon de nia vosto estas 3. Ni havas 3 elementojn en ĝi. Do se ni estis, kaj ni ne tuj por nun, enqueue alia elemento, ĝi irus en tabelo location numero 3, kaj la grandeco de nia atendovico estus 4. Do ni enqueued pluraj elementoj nun. Nun ni komencu forigi ilin. Ni dequeue ilin de atendovico. 

Do simila al popmuziko, kiu estas speco de la analoga de tiu por stakoj, dequeue bezonas akcepti sagon al la queue-- denove, krom se ĝi estas tutmonde deklaris. Nun ni volas ŝanĝi la lokon de la fronto de la atendovico. Jen kie ia venas en ludon, tiu fronto ŝanĝiĝema, ĉar iam ni forigu ero, ni volas movi ĝin al la venonta plej malnova elemento. 

Tiam ni volas malpliigi la grandeco de la vosto, kaj tiam ni volas reveni al la valoro kiu estis forigita de la atendovico. Denove, ni ne volas simple forĵeti ĝin. Ni supozeble ankaŭ ĉerpas ĝin de la queue-- ni estas dequeuing ĝin ĉar ni zorgas pri ĝi. Do ni volas tiun funkcion reveni datuma elemento de tipo valoro. Denove, en tiu kazo, valoro estas entjero. 

Do nun ni dequeue ion. Ni forigu ero de la vico. Se ni diras int x egalas & q, ampersand q-- denove jen puntero al tiu q datumoj structure-- kion elemento tuj estos dequeued? En tiu kazo, ĉar ĝi estas unua en, unua el datumstrukturo, FIFO, ni unue metas en tiun atendovico estis 28, kaj tiel en tiu kazo, ni iras preni 28 el la vosto, ne 19, kion estas kio ni estus farinta se tiu estis stako. Ni iras preni 28 el la vico. 

Similaj al kion ni faris kun pilo, ni ne vere tuj forviŝi 28 el la vosto mem, ni nur tuj speco de ŝajnigi ke gxi mankas. Do ĝi estas tuj restos tie en memoro, sed ni estas nur tuj speco de ignori ĝin movante la aliaj du kampoj de nia q datumoj strukturo. Ni tuj ŝanĝos la fronton. Q.front nun tuj esti 1, pro tio estas nun la plej malnova elemento kiun ni havas en nia atendovico, ĉar ni jam forigis 28 kiu estis la iama plej malnova elemento. 

Kaj nun, ni volas ŝanĝi la grandeco de la vosto por du elementoj anstataŭ tri. Nun memoru frue mi diris, kiam ni volas aldoni elementojn al la atendovico, ni metu ĝin en tabelo location kiu estas la sumo de fronto kaj grandeco. Do en ĉi tiu kazo, ni ankoraŭ metante ĝi, la sekvanta elemento en la vico, en tabelo loko 3, kaj Ni vidos ke en dua. 

Do ni nun dequeued nia unua elemento de la vico. Ni faru tion denove. Ni forigu alian elemento de la vico. En la kazo, la nuna malnova elemento estas tabelo situon 1. Tion q.front diras ni. Ke verda skatolo nin diras ke tio estas la plej malnova elemento. Kaj do, x fariĝos 33. Ni nur ia forgesas ke 33 ekzistas en la tabelo, kaj ni diru, ke nun, la novajn plej malnova ero en la atendovico estas ĉe tabelo loko 2, kaj la grandeco de la atendovico, la nombro de elementoj ni havas en la vosto, estas 1. Nun ni enqueue io, kaj mi ia donis tiun for sekundo antaŭ, sed se ni volas meti 40 en la atendovico, kie estas 40 tuj iros? Nu ni estis metante gxin en q.front plus atendovico grandeco, kaj tiel ĝi havas sencon reale meti 40 tie. Nun rimarkas ke ĉe iu punkto, ni tuj akiri al la fino de nia tabelo interne de q, sed ke elsenkoloriĝis 28 kaj 33-- ili estas reale, teknike malferma spacoj, dekstra? Kaj tiel, ni eventually-- regulon de aldonado tiuj du together-- ni povas eventuale bezonas mod per la grandeco de kapacito tiel ni povas envolvi ĉirkaŭe. 

Do se ni atingos elemento numero 10, se ni estas anstataŭante ĝin elemento numero 10, ni preferus efektive metis ĝin en tabelo ĉelo 0. Kaj se ni iris al tabelo location-- pardonu, se ni aldonas ilin kune, kaj ni atingis numeron 11 estus kie ni devus meti ĝin, kiu ne ekzistas en tiu tabelo ĝi estus iranta el baroj. Ni povis mod per 10 kaj metis ĝi pafu situon 1. Do jen kiel vostoj labori. Ili estas ĉiam iranta iri de maldekstra dekstren kaj eble envolvi ĉirkaŭe. Kaj vi scias, ke ili estas plena se grandeco, ke ruĝa skatolo, iĝas egala al kapacito. Kaj do post ni aldonis 40 por la atendovico, bone kion ni devas fari? Nu, la plej malnova elemento en la atendovico estas ankoraŭ 19, tial ni ne volas ŝanĝi la fronto de la atendovico, sed nun ni havas du elementoj en la vosto, kaj tiel ni volas pliigi nia grando el 1 al 2. 

Tio estas sufiĉe multe ĝin kun laborante kun tabelo-bazita atendovicoj, kaj simila al pilo, ekzistas ankaŭ vojo implementar atendovico kiel ligillisto. Nun se tiu datumstrukturo tipo aspektas familiaraj al vi, ĝi estas. Ĝi ne estas unuope ligillisto, ĝi estas duoble ligitaj listo. Kaj nun, kiel flanken, estas fakte eblas apliki atendovico kiel unuope ligita listo, sed Mi pensas en terminoj de visualización, ĝi efektive povus helpi al vidi tion kiel duoble ligita listo. Sed estas sendube ebla faras tion kiel unuope ligita listo. 

Do ni havas rigardi kion tio povus aspekti. Se ni volas enquue-- tial nun, denove ni estas ŝaltanta al kunligita-listo bazita modelo tie. Se ni volas enqueue, ni volas aldoni novan elementon, bone kion ni devas fari? Nu, unue, ĉar ni aldonante al la fino forigo de la komencante, ni probable volas subteni punteros al ambaŭ la kapo kaj la vosto de la ligitaj listo? Vosto esti alia termino por la fino de la ligillisto, la lasta elemento en la ligitaj listo. Kaj tiuj verŝajne, denove, esti utila al ni se ili estas tutmonda variabloj. Sed nun se ni volas aldoni novan elemento kion ni devas fari? Kion ni ĵus [? Malak?] aŭ dinamike asigni nia nova nodo por ni mem. Kaj tiam, ĝuste kiel kiam ni aldonas neniun elemento al duoble ligillisto ni, nur devi ordigi of-- tiuj lastaj tri paŝojn tie estas nur ĉio pri movanta la punteros en la korekta maniero por ke la elemento gets aldonita al la ĉeno sen rompi la ĉenon aŭ farante ian eraro aŭ havantaj iun specon de akcidento okazi per kiu ni hazarde Orfino iuj elementoj de nia vico. Jen kion ĉi povus aspekti. Ni volas aldoni la elementon 10 al la fino de tiu vico. Do la plej malnova elemento tie estas reprezentita de kapo. Tio estas la unua afero ni metu en tiu hipotético atendovico tie. Kaj vosto, 13, estas la plej ĵus aldonita elemento. Kaj do se ni volas enqueue 10 en tiu vosto, ni volas meti ĝin post 13. Kaj do ni tuj dinamike destini spaco por nova nodo kaj kontroli por nula certigi ni ne havas memoron fiasko. Tiam ni tuj meti 10 en tiu nodo, kaj nun ni devas atenti pri kiel ni organizi punteros do ni ne rompi la ĉenon. 

Ni povas agordi 10 la antaŭa kampo atentigi reen al la malnova vosto, kaj ekde '10 estos la novajn vosto en iu punkto por kiam ĉiuj tiuj ĉenoj estas konektitaj, nenio tuj venu post 10 nun. Kaj do 10 la sekvanta puntero indikos al nula, kaj tiam post ni fari tion, ni ja konektita 10 malantaŭen al la ĉeno, ni povas preni la malnova kapo, aŭ, senkulpigo Mi, la malnova vosto de la vosto. La malnova fino de la vico, 13 kaj faru por ĝi indikas 10. Kaj nun, je ĉi tiu punkto, ni havas enqueued la numero 10 en tiu vico. Ĉiuj ni devas fari nun estas simple movi la voston por indiki al 10 anstataŭ 13. 

Dequeuing estas reale tre simila al krevanta el stako kiu estas implementados kiel ligillisto se vi vidos la stakoj vídeo. Ĉiuj ni devas fari estas komenci ĉe la komencante, trovi la dua elemento, liberigi la unua elemento, kaj tiam movi la kapon atentigi al la dua elemento. Probable pli bone bildigi ĝi Nur esti kroma klara pri tio. Do jen nia vosto denove. 12 estas la plej malnova elemento en nia vosto, la kapo. 10 estas la plej nova elemento en nia vosto, nia vosto. 

Kaj tial kiam ni volas al dequeue ero, ni deziras forigi la plej malnova elemento. Do kion ni faru? Nu ni aperigos trairado montrilon kiu komenciĝas ĉe la kapo, kaj ni movas ŝin por ke ĝi montras al la dua ero de tiu queue-- ion dirante trav egalas trav arrow sekva, ekzemple, movus trav tie atentigi al 15, kiuj, post ni dequeue 12 aŭ post ni forpreni 12, volo fariĝis la tiama plej malnova elemento. 

Nun ni havas tenon sur la unua elemento tra la montrilon kapo kaj la dua elemento tra la montrilon trav. Ni povas nun libera kapon, kaj tiam ni povas diru nenion venas antaŭ 15 anymore. Do ni povas ŝanĝi 15 la antaŭa puntero atentigi al nula, kaj ni simple movi la kapon super. Kaj tie ni iru. Nun ni havas sukcese dequeued 12, kaj nun ni havas alian atendovico de 4 elementoj. Tio estas sufiĉe multe ĉiuj oni devas atendovicoj, ambaŭ tabelo-bazita kaj ligitaj listo bazita. Mi Doug Lloyd. Jen CS 50.