DOUG LLOYD: Hivyo kama wewe wameweza watched video juu ya stack, hii pengine ni kwenda kujisikia kama kidogo ya Deja vu. Ni kwenda dhana sawa sana, tu na twist kidogo juu yake. Sisi ni kwenda kuzungumza sasa kuhusu foleni. Hivyo foleni, sawa na stack, aina nyingine ya mfumo wa data kwamba tunaweza kutumia ili kudumisha data katika njia kupangwa. Sawa na stack, inaweza kutekelezwa kama safu au orodha wanaohusishwa. Tofauti na stack, sheria kwamba sisi kutumia ili kuamua Wakati mambo kupata aliongeza na kuondolewa kutoka foleni ni tofauti kidogo. Tofauti na stack, ambayo ni muundo wa LIFO, mwisho katika, nje ya kwanza, foleni ni FIFO muundo, FIFO, kwanza katika, nje ya kwanza. Sasa foleni, pengine kuwa mfano kwa foleni. Kama wameweza milele wamekuwa katika mstari katika Hifadhi ya pumbao au katika benki, kuna aina ya haki utekelezaji wa muundo. Mtu wa kwanza katika mstari katika benki ni mtu wa kwanza ambaye anapata kuongea na teller. 

Itakuwa aina ya mbio mpaka chini kama njia pekee Je, unayo kuzungumza na teller katika benki ilikuwa kuwa mtu wa mwisho katika mstari. Kila mtu bila siku zote wanataka kuwa mtu wa mwisho katika mstari, na mtu ambaye alikuwepo kwanza ambaye amekuwa kusubiri kwa muda, inaweza kuwa pale kwa saa, na masaa, na masaa kabla ya kuwa na nafasi ya kweli kutoa pesa yoyote katika benki. Na hivyo foleni ni aina ya haki utekelezaji wa muundo. Lakini hiyo haimaanishi zilizofungwa ni jambo baya, tu kwamba foleni ni njia nyingine ya kufanya hivyo. Hivyo tena foleni ni ya kwanza katika, kwanza nje, dhidi ya stack ambayo itadumu katika, kwanza nje. Sawa na stack, tuna shughuli mbili tuweze kufanya juu ya foleni. Majina yao ni enqueue, ambayo ni kuongeza kipengele mpya hadi mwisho wa foleni, na dequeue, ambayo ni kuondoa kongwe kipengele kutoka mbele ya foleni. Hivyo sisi ni kwenda kwa kuongeza mambo kwenye mwisho wa foleni, na tunakwenda kuondoa vipengele kutoka mbele ya foleni. Tena, kwa stack, tulikuwa na kuongeza mambo ya juu ya stack na kuondoa vipengele kutoka juu ya stack. Hivyo, pamoja na enqueue, ni kuongeza kwa mwisho, kuondoa kutoka mbele. Kwa hiyo, jambo kongwe nchini huko Daima ni jambo la pili kuja nje kama sisi kujaribu na dequeue kitu. 

Hivyo tena, na foleni, tunaweza utekelezaji safu makao na wanaohusishwa-orodha utekelezaji msingi. Tutaweza kuanza tena kwa safu makao utekelezaji. Muundo wa ufafanuzi inaonekana pretty sawa. Tuna safu nyingine kuna aina ya data thamani, hivyo inaweza kushikilia aina holela data. Sisi ni tena kwenda kutumia integers katika mfano huu. 

Na kama kwa wetu safu yenye makao yake stack utekelezaji, kwa sababu sisi ni kutumia safu, sisi lazima na kwamba kiwango cha juu kwamba C aina ya utekelezaji juu yetu, ambayo ni sisi hawana mabadiliko yoyote katika yetu uwezo wa kukua na kuogopa safu. Tuna kuamua mwanzoni kile ni upeo wa idadi ya mambo tuweze kuweka katika hii foleni, na katika kesi hii, uwezo itakuwa baadhi chupa inavyoelezwa mara kwa mara katika kanuni zetu. Na kwa madhumuni ya hii video, uwezo ni kwenda kuwa 10. 

Tunahitaji kuweka wimbo wa mbele ya foleni hivyo tunajua ambayo kipengele tunataka dequeue, na sisi pia haja ya kuweka wimbo wa kitu else-- idadi ya vipengele kwamba sisi katika foleni yetu. Taarifa sisi siyo kuweka wimbo ya mwisho wa foleni, tu ukubwa wa foleni. Na sababu ya kuwa mapenzi hopefully kuwa kidogo wazi katika wakati huu. Mara tuna kukamilika huu ufafanuzi aina, tuna aina mpya data aitwaye foleni, ambayo tunaweza sasa kutangaza vigezo vya aina kwamba data. Na kwa kiasi fulani confusingly, nimekuwa aliamua kuwaita hii foleni q, barua q badala ya aina data q. 

Hivyo hapa ni foleni yetu. Ni muundo. Ina wajumbe watatu au tatu mashamba, safu ya ukubwa UWEZO. Katika kesi hiyo, UWEZO ni 10. Na safu hii ni kwenda kushikilia integers. Katika kijani ni mbele ya foleni yetu, kipengele karibu na kuondolewa, na katika nyekundu itakuwa ukubwa wa foleni, jinsi mambo mengi kwa sasa zilizopo katika foleni. Hivyo kama sisi kusema sawa q.front 0, ukubwa na q.size sawa na 0-- sisi ni kuweka sekunde 0 katika mashamba hayo. Na katika hatua hii, sisi ni pretty much tayari kwa kuanza kufanya kazi na foleni yetu. 

Hivyo operesheni ya kwanza tunaweza kufanya ni enqueue kitu, kuongeza kipengele mpya ya mwisho wa foleni. Vizuri tunahitaji nini ili kufanya katika kesi ujumla? Vizuri kazi hii enqueue mahitaji kukubali pointer foleni yetu. Tena, kama sisi alikuwa ametangaza foleni yetu kimataifa, sisi bila haja ya kufanya hivyo lazima, lakini kwa ujumla, sisi haja ya kukubali kuyatumia kwa miundo data kama hii, kwa sababu vinginevyo, sisi ni kupita na value-- tuko kupita katika nakala za foleni, na hivyo sisi siyo kweli kubadilisha foleni kwamba sisi nia ya kubadilika. 

Jambo jingine ni mahitaji ya kufanya ni kukubali data kipengele cha aina ya mwafaka. Tena, katika kesi hii, ni kwenda kuwa integers, lakini wewe hakuweza kiholela kutangaza data aina kama thamani na kutumia hii kwa ujumla zaidi. Hiyo ni kipengele tunataka enqueue, tunataka kuongeza hadi mwisho wa foleni. Kisha sisi kweli wanataka mahali takwimu ambazo katika foleni. Katika kesi hiyo, kuziweka katika eneo sahihi ya safu yetu, na kisha tunataka mabadiliko ya kawaida ya foleni, jinsi wengi vipengele sisi sasa kuwa. 

Basi hebu kuanza. Hapa ni, tena, kwamba kwa ujumla fomu ya tamko kazi kwa nini enqueue ili kuangalia kama. Na hapa sisi kwenda. Hebu enqueue idadi 28 katika foleni. Kwa hiyo kile ni sisi kwenda kufanya? Naam, mbele ya foleni yetu ni saa 0, na ukubwa wa foleni yetu ni 0, na hivyo sisi pengine wanataka kuweka idadi 28 katika safu kipengele idadi 0, sawa? Hivyo tumekuwa sasa kuwekwa kwamba katika huko. Hivyo sasa je, sisi haja ya kubadili? Hatutaki kubadilisha mbele ya foleni, kwa sababu tunataka kujua nini kipengele tupate haja ya dequeue baadaye. Hivyo sababu tuna mbele huko ni aina ya kiashiria cha nini Jambo kongwe katika safu. Vizuri jambo kongwe nchini array-- katika kweli, kitu pekee katika safu haki now-- ni 28, ambayo ni katika safu eneo 0. Kwa hiyo sisi hawataki mabadiliko hayo idadi ya kijani, kwa sababu hiyo ni kipengele kongwe. Badala yake, tunataka mabadiliko ya kawaida. Hivyo katika kesi hii, tutaweza increment kawaida kwa 1. 

Sasa aina ya jumla ya wazo la ambapo kipengele ijayo ni kwenda katika foleni ni kuongeza namba hizo mbili pamoja, mbele na ukubwa, na kwamba nitakuambia ambapo ijayo kipengele katika foleni ni kwenda. Hivyo sasa hebu enqueue namba nyingine. Hebu enqueue 33. Hivyo 33 ni kwenda katika safu eneo 0 pamoja na 1. Hivyo katika kesi hii, ni kwenda kwenda katika safu eneo 1, na sasa ukubwa wa foleni yetu ni 2. 

Tena, sisi siyo kubadilisha mbele ya foleni yetu, kwa sababu 28 bado ni kongwe kipengele, na sisi wanataka to-- wakati sisi hatimaye kupata kwa dequeuing, kuondoa vipengele kutoka foleni hii, tunataka kujua ambapo kipengele kongwe ni. Na hivyo sisi daima haja ya kudumisha baadhi kiashiria cha ambapo kwamba ni. Hivyo kwamba ni nini 0 ni pale kwa ajili. Hiyo ni nini mbele ni pale kwa. 

Hebu katika enqueue moja zaidi ya kipengele, 19. Mimi nina uhakika unaweza nadhani ambapo 19 ni kwenda. Ni kwenda kwenda katika safu eneo idadi 2. Hiyo ni pamoja na 0 2. Na sasa ukubwa wa foleni yetu ni 3. Tuna 3 mambo ndani yake. Hivyo kama tulikuwa na sisi siyo kwenda kwa sasa hivi, enqueue kipengele kingine, ingekuwa kwenda katika safu eneo namba 3, na ukubwa wa foleni yetu itakuwa 4. Hivyo tumekuwa enqueued mambo kadhaa sasa. Sasa hebu kuanza kuondoa yao. Hebu dequeue yao kutoka foleni. 

Hivyo sawa na pop, ambayo ni aina ya Analog ya hii kwa mwingi, dequeue inahitaji kukubali pointer queue-- tena, isipokuwa ni duniani alisema. Sasa tunataka mabadiliko ya eneo ya mbele ya foleni. Hii ni pale ambapo ni aina ya suala la katika kucheza, kwamba kutofautiana mbele, kwa sababu mara moja sisi kuondoa kipengele, tunataka hoja hiyo kwa ijayo kongwe kipengele. 

Kisha tunataka kupunguza ukubwa wa foleni, na kisha tunataka kurudi thamani kwamba ilikuwa kuondolewa kutoka foleni. Tena, sisi hawataki tu kuondokana na hilo. Sisi labda ni kuchimba ni kutoka queue-- tuko dequeuing ni kwa sababu sisi huduma kuhusu hilo. Hivyo tunataka kazi hii kurudi data kipengele cha aina thamani. Tena, katika kesi hii, thamani ya kitu integer. 

Hivyo sasa hebu dequeue kitu. Hebu kuondoa kipengele kutoka foleni. Tukisema int x sawa na q, ampersand q-- tena kwamba pointer kwa taarifa hii q structure-- nini kipengele ni kwenda kuwa dequeued? Katika kesi hiyo, kwa sababu ni kwanza katika, kwanza nje data muundo, FIFO, Jambo la kwanza sisi kuweka katika hii foleni ilikuwa 28, na hivyo katika kesi hii, sisi ni kwenda kuchukua 28 nje ya foleni, si 19, ambayo ni nini sisi ingekuwa amefanya kama hii ilikuwa stack. Sisi ni kwenda kuchukua 28 nje ya foleni. 

Sawa na kile sisi alivyofanya kwa stack, sisi siyo kweli kwenda kufuta 28 kutoka foleni yenyewe, tunakwenda tu aina ya kujifanya si huko. Hivyo ni kwenda kukaa huko katika kumbukumbu, lakini tuko tu kwenda aina ya kupuuza na kusonga maeneo mengine mawili ya q takwimu zetu muundo. Tunakwenda kubadili mbele. Q.front sasa ni kwenda kuwa 1, kwa sababu hiyo ni sasa kongwe kipengele tuna katika yetu foleni, kwa sababu tumekuwa tayari kuondolewa 28, ambayo ilikuwa zamani kipengele kongwe. 

Na sasa, tunataka mabadiliko ukubwa wa foleni kwa mambo mawili badala ya tatu. Sasa kumbuka mapema nilivyosema wakati sisi wanataka kuongeza mambo ya foleni, sisi kuiweka katika safu eneo ambayo ni jumla ya mbele na ukubwa. Hivyo katika kesi hii, bado tuko kuweka hivyo, kipengele ijayo katika foleni, ndani ya safu eneo 3, na tutaweza kuona kwamba katika pili. 

Hivyo tumekuwa sasa dequeued yetu kitu cha kwanza kutoka foleni. Hebu kufanya hivyo tena. Hebu kuondoa mwingine kipengele kutoka foleni. Katika kesi, sasa kongwe kipengele ni safu eneo 1. Hiyo ni nini q.front anatueleza. Hiyo sanduku ya kijani anatueleza kwamba hiyo ni kipengele kongwe. Na hivyo, x itakuwa 33. Tutaweza tu aina ya kusahau kuwa 33 ipo katika safu, na tutaweza kusema kwamba sasa, mpya kipengele kongwe katika foleni ni katika safu eneo 2, na ukubwa ya foleni, idadi ya vipengele tuna katika foleni, ni 1. Sasa hebu enqueue kitu, na mimi aina ya alitoa hii ya pili iliyopita mbali, lakini kama tunataka kuweka 40 katika foleni, ambapo ni 40 kwenda? Naam tumekuwa kuweka katika q.front pamoja na foleni ukubwa, na hivyo inafanya hisia kweli kuweka 40 hapa. Sasa taarifa kwamba katika fulani, tunakwenda kupata mwisho wa safu yetu ya ndani ya q, lakini kwamba Faded nje 28 na 33-- wao ni kweli, kitaalam maeneo ya wazi, sawa? Na hivyo, tunaweza eventually-- kuwa utawala wa kuongeza hizo mbili together-- tupate hatimaye haja ya Mod na ukubwa wa uwezo ili tuweze kufungia. 

Hivyo kama sisi kupata kipengele namba 10, kama sisi ni badala yake katika kipengele namba 10, tunatarajia kweli kuiweka katika safu eneo 0. Na kama sisi wanakwenda safu location-- udhuru kwangu, kama sisi aliongeza yao juu pamoja, na tulipata idadi Kuwa 11 itakuwa ambapo tunataka kuwa na kuweka yake, ambayo haipo katika array-- hii itakuwa kwenda nje ya mipaka. Tunaweza Mod na 10 na kuweka hivyo katika safu eneo 1. Hivyo hiyo ni jinsi foleni kazi. Wao ni daima kwenda kwenda kutoka kushoto na haki na uwezekano wa kufungia. Na unajua kwamba wao ni kamili kama kawaida, kwamba nyekundu sanduku, inakuwa sawa na uwezo. Na hivyo baada tumekuwa aliongeza 40 kwa foleni, vizuri tunahitaji nini cha kufanya? Naam, kipengele kongwe katika foleni bado ni 19, hivyo hatutaki kubadili mbele ya foleni, lakini sasa tuna mbili vipengele katika foleni, na hivyo tunataka kuongeza ukubwa yetu 1-2. 

Hiyo ni pretty kiasi kwa kufanya kazi na foleni safu yenye makao yake, na sawa na stack, pia kuna njia kutekeleza foleni kama orodha wanaohusishwa. Sasa kama aina hii ya muundo data inaonekana ukoo na wewe, ni. Siyo orodha moja moja wanaohusishwa, ni orodha doubly wanaohusishwa. Na sasa, kama kando, ni kweli inawezekana kutekeleza foleni kama orodha moja moja wanaohusishwa, lakini Nadhani katika suala la taswira, ni kweli inaweza kusaidia kutazama hii kama orodha doubly wanaohusishwa. Lakini ni dhahiri inawezekana kufanya hivyo kama orodha moja moja wanaohusishwa. 

Basi hebu kuwa na kuangalia nini hii ili kuangalia kama. Kama tunataka enquue-- hivyo kwa sasa, tena sisi ni byte wanaohusishwa-orodha msingi mfano hapa. Kama tunataka enqueue, tunataka kuongeza kipengele mpya, vizuri je, sisi haja ya kufanya? Naam, awali ya yote, kwa sababu sisi ni kuongeza hadi mwisho na kuondoa kutoka mwanzo, sisi pengine wanataka kudumisha kuyatumia kwa wote kichwa na mkia wa orodha wanaohusishwa? Mkia kuwa muda mwingine kwa mwisho wa orodha wanaohusishwa, kipengele mwisho katika orodha wanaohusishwa. Na hawa pengine, tena, kuwa na manufaa kwa sisi kama ni vigezo kimataifa. Lakini sasa kama tunataka kuongeza mpya kipengele je, tuna kufanya? Nini sisi tu [? malak?] au dynamically kutenga nodi wetu mpya kwa wenyewe. Na kisha, tu kama wakati sisi kuongeza yoyote kipengele kwa mara mbili wanaohusishwa orodha sisi, tu una aina of-- wale hatua tatu za mwisho hapa ni tu wote kuhusu kuhamia kuyatumia katika njia sahihi ili kipengele anapata aliongeza kwa mlolongo bila kuvunja mlolongo au kufanya aina fulani ya makosa au kuwa na aina fulani ya ajali kutokea ambapo sisi ajali yatima baadhi ya vipengele ya foleni yetu. Hapa ni nini hii ili kuangalia kama. Tunataka kuongeza kipengele 10 hadi mwisho wa foleni hii. Hivyo kongwe kipengele hapa ni kuwakilishwa na kichwa. Hiyo ni jambo la kwanza sisi kuweka ndani ya hii foleni kubuni hapa. Na mkia, 13, ni zaidi hivi karibuni aliongeza kipengele. Na hivyo kama tunataka enqueue 10 katika foleni hii, tunataka kuiweka baada ya 13. Na hivyo tunakwenda dynamically kutenga nafasi kwa nodi mpya na kuangalia for kuhakikisha hatuna kushindwa kumbukumbu. Kisha tunakwenda mahali 10 katika nodi kwamba, na sasa tunahitaji kuwa makini kuhusu jinsi sisi kuandaa kuyatumia hivyo hatuna kuvunja minyororo. 

Tunaweza kuweka 10 ya uwanja uliopita kwa kumweka nyuma miaka mkia, na tangu '10 itakuwa mkia mpya wakati fulani na wakati yote haya minyororo ni kushikamana, kitu kinaendelea kuja baada ya 10 hivi sasa. Na hivyo 10 ijayo pointer uhakika na null, na kisha baada ya sisi kufanya hivyo, baada tumekuwa kushikamana 10 nyuma ya mlolongo, tunaweza kuchukua kichwa zamani, au, kisingizio mimi, mwenye umri wa mkia wa foleni. Mwisho wa miaka ya foleni, 13, na kufanya hivyo uhakika na 10. Na sasa, katika hatua hii, tuna enqueued namba 10 katika foleni hii. Wote tunahitaji kufanya sasa ni kusonga tu mkia kwa uhakika badala ya kwa 10 hadi 13. 

Dequeuing ni kweli sawa na yanajitokeza kutoka mkusanyiko kwamba ni kutekelezwa kama orodha wanaohusishwa kama wameweza kuona mwingi video. Wote tunahitaji kufanya ni kuanza saa mwanzo, kupata kipengele cha pili, bure kipengele kwanza, na kisha kuondoka kichwa kwa uhakika na kipengele cha pili. Pengine ni bora kwa taswira yake tu kuwa na ziada ya wazi kuhusu suala hilo. Hivyo hapa ni foleni yetu tena. 12 ni sehemu ya zamani zaidi katika foleni yetu, mkuu. 10 ni sehemu ya newest katika foleni yetu, mkia yetu. 

Na hivyo wakati tunataka kwa dequeue kipengele, tunataka kuondoa kipengele kongwe. Hivyo tunafanya nini? Naam sisi kuweka pointer traversal kwamba kuanza saa kichwa, na sisi hoja hiyo ili anazungumzia kipengele cha pili ya hii queue-- kitu kwa kusema trav sawa trav mshale ijayo, kwa mfano, ingekuwa hoja trav huko kwa uhakika na 15, ambayo, baada ya sisi dequeue 12, au baada ya sisi kuondoa 12, mapenzi kuwa kipengele kisha-kongwe. 

Sasa sisi tumepewa uwezo juu ya kwanza kipengele kupitia pointer kichwa na kipengele cha pili kupitia pointer trav. Tunaweza sasa bure kichwa, na kisha tunaweza kusema kitu huja kabla 15 tena. Hivyo tunaweza kubadili 15 uliopita pointer kwa uhakika na null, na sisi tu hoja kichwa juu. Na kuna sisi kwenda. Sasa tuna mafanikio dequeued 12, na sasa sisi na foleni nyingine ya 4 vipengele. Hiyo ni pretty much wote hapo ni foleni, wote safu yenye makao yake na wanaohusishwa-orodha msingi. Mimi nina Doug Lloyd. Hii ni CS 50.