Doug Lloyd: Se konsa, si ou te ap gade videyo a sou chemine, sa a se pwobableman ale nan santi tankou yon ti kras nan deja VU. Li nan ale nan yon konsèp trè menm jan an, jis ak yon tòde ti tay sou li. Nou pwal pale kounye a sou ke moun kap kriye. Se konsa, yon keu, menm jan ak yon pil, se yon lòt kalite estrikti done ke nou kapab itilize yo kenbe done nan yon fason òganize. Menm jan ak yon pil, li kapab aplike kòm yon etalaj oswa yon lis lye. Kontrèman ak yon chemine, règ yo ke nou itilize detèmine lè bagay sa yo jwenn te ajoute ak retire nan yon keu se yon ti jan ti kras diferan. Kontrèman ak yon chemine, ki se yon estrikti LIFO, dire nan, premye soti, yon keu se yon FIFO estrikti, FIFO, premye nan, premye deyò. Koulye a, ke moun kap kriye, pwobableman ou gen yon analoji ke moun kap kriye. Si ou te janm te nan liy nan yon pak amizman oswa nan yon bank, gen nan sòt de yon jistis mete ann aplikasyon estrikti. Premye moun ki nan liy nan bank la se premye moun ki ki moun ki gen pou pale ak Teller an. 

Li ta sòt de yon ras jouk anba a si wout la sèlman ou te resevwa pou pale ak Teller an nan la bank te dwe moun ki sot pase a nan liy. Tout moun ta toujou vle yo dwe moun ki sot pase a nan liy, ak moun nan ki moun ki te gen premye ki moun ki te ap tann pou yon ti tan, ta ka gen pou èdtan, ak èdtan, ak èdtan anvan yo gen yon chans yo aktyèlman retire nenpòt ki lajan nan bank la. Se konsa, ke moun kap kriye yo se sòt de la etidye ekite Règleman mete ann aplikasyon estrikti. Men, sa pa nesesèman vle di ki pil yo se yon move bagay, jis ki ke moun kap kriye yo se yon lòt fason yo fè li. Se konsa, ankò yon keu se premye nan, premye soti, kont yon pil ki dire a, premye deyò. Menm jan ak yon pil, nou gen de operasyon ke nou ka fè sou ke moun kap kriye. Non yo se enqueue, ki se yo ajoute yon eleman nouvo nan fen a nan keu a, ak dequeue, ki se yo retire pi ansyen an eleman soti nan devan an nan keu la. Se konsa, nou ap ale nan ajoute eleman sou nan fen nat la, e nou pral yo retire eleman soti nan devan an nan keu la. Yon fwa ankò, ak chemine a, nou te ajoute eleman nan tèt la nan chemine a epi yo retire eleman soti nan tèt la nan chemine a. Se konsa, avèk enqueue, li nan ajoute nan fen a, retire soti nan devan an. Se konsa, bagay ki pi ansyen nan la se toujou bagay la pwochen vin soti si nou eseye ak dequeue yon bagay. 

Se konsa, ankò, ak ke moun kap kriye, nou ka en etalaj ki baze sou ak lye-lis ki baze en. Nou pral kòmanse ankò ak etalaj ki baze sou en. Definisyon an estrikti sanble trè menm jan an. Nou gen yon lòt etalaj gen nan done valè kalite, se konsa li ka kenbe kalite done abitrè. Nou ap ankò ale nan sèvi ak nonm antye relatif nan egzanp sa a. 

Epi jis tankou ak nou an etalaj ki baze sou aplikasyon chemine, paske nou ap sèvi ak yon etalaj, nou nesesèman gen sa limitasyon ki kalite C a aplike pou nou, ki se nou pa gen okenn dynamism nan nou an kapasite yo grandi ak retresi etalaj la. Nou gen deside nan kòmansman an ki sa ki la pou maksimòm kantite bagay ke nou ka mete nan sa a keu, ak nan ka sa a, kapasite ta gen kèk liv defini konstan nan kòd nou an. Se pou rezon yo nan sa a videyo, kapasite a pwal 10. 

Nou bezwen kenbe tras nan devan nan keu la se konsa nou konnen ki eleman nou vle dequeue, epi nou bezwen tou nan kenbe tras nan yon bagay else-- nimewo a nan eleman ke nou gen nan keu nou an. Avi nou pa ap kenbe tras nan fen a nan nat la, jis gwosè a nan keu la. Ak rezon an pou ki pral èspere ke vin yon ti jan pi klè nan yon moman. Yon fwa nou fin fè definisyon kalite sa a, nou gen yon nouvo kalite done rele keu, nou kapab kounye a deklare varyab la ki kalite done. Ak yon ti jan konfizyon, mwen te deside yo rele sa a q keu, lèt la q olye pou yo q nan kalite done. 

Se konsa, isit la se keu nou an. Li se yon estrikti. Li genyen ladan li twa manm oswa twa chan sa yo, yon etalaj de gwosè KAPASITE. Nan ka sa a, kapasite se 10. Apre sa, sa a se etalaj ale nan kenbe nonm antye relatif. Nan vèt se nan devan an nan keu nou an, eleman pwochen yo dwe retire, ak nan wouj yo pral gwosè a nan keu a, konbyen eleman se kounye a ki deja egziste nan keu la. Se konsa, si nou di egal q.front 0, ak gwosè q.size egal 0-- nou ap mete nan sa yo 0s jaden yo. Ak nan pwen sa a, nou ap bèl anpil pare yo kòmanse travay ak keu nou an. 

Se konsa, operasyon an premye nou kapab fè se yo enqueue yon bagay, ajoute yon eleman ki nouvo nan nan fen keu la. Oke ki sa nou bezwen fè nan ka a jeneral? Oke sa a fonksyon enqueue bezwen aksepte yon konsèy nan keu nou an. Yon fwa ankò, si nou te deklare keu nou an globalman, nou pa ta bezwen fè sa nesesèman, men an jeneral, nou bezwen aksepte endikasyon nan estrikti done tankou sa a, paske otreman, nou ap pase nan value-- nou ap pase nan kopi keu a, e konsa nou ap pa aktyèlman chanje keu a ke nou gen entansyon chanje. 

Bagay la lòt li bezwen fè se aksepte yon eleman done nan kalite la ki apwopriye yo. Yon fwa ankò, nan ka sa a, li nan pral fè nonm antye relatif, men ou te kapab abitrèman deklare kalite nan done kòm valè epi sèvi ak sa a plis jeneralman. Sa a eleman nan nou vle enqueue, nou vle ajoute nan fen a nan keu la. Lè sa a, nou aktyèlman vle mete ke done nan keu la. Nan ka sa a, mete l 'nan la kòrèk kote nan etalaj nou an, ak Lè sa a nou vle chanje gwosè a nan nat la, konbyen eleman nou genyen kounye a. 

Se konsa nou jwenn te kòmanse. Isit la se, ankò, ki jeneral deklarasyon fonksyon fòm pou sa ki ta ka enqueue sanble. Ak isit la nou ale. Se pou nou enqueue nimewo a 28 nan keu la. Se konsa, sa nou pral fè? Oke, devan nan keu nou an, se nan 0, ak gwosè a nan nat nou an se nan 0, e konsa nou pwobableman vle mete nimewo a 28 nan kantite eleman etalaj 0, dwa? Se konsa, nou te kounye a mete ki nan la. Se konsa, kounye sa nou bezwen chanje? Nou pa vle chanje devan nan keu a, paske nou vle konnen ki sa eleman nou ta ka bezwen dequeue pita. Se konsa, rezon ki fè yo nou gen devan gen se sòt de yon endikatè a sa ki nan bagay la pi ansyen nan etalaj la. Oke bagay la pi ansyen nan array-- a nan reyalite, bagay la sèlman nan etalaj nan dwa now-- se 28, ki se a etalaj kote 0. Se konsa, nou pa vle chanje nimewo sa vèt, paske se sa eleman ki pi ansyen. Olye de sa, nou vle chanje gwosè la. Se konsa, nan ka sa a, nou pral kantite gwosè a 1. 

Koulye a, yon sòt jeneral nan lide sou a ki kote eleman pwochen ki pral ale nan yon keu se yo ajoute de nonb moun ansanm, devan ak gwosè, e ke pral di w ki kote pwochen an eleman nan keu la ki pral ale. Se konsa, kounye a kite a enqueue yon lòt kantite. Se pou nou enqueue 33. Se konsa, 33 ki pral ale nan etalaj kote 0 plis 1. Se konsa, nan ka sa a, li pral ale nan etalaj kote 1, e kounye a, gwosè a nan keu nou an, se 2. 

Yon fwa ankò, nou pa ap chanje devan nan keu nou an, paske 28 se toujou nan pi ansyen eleman, epi nou vle to-- lè nou evantyèlman jwenn dequeuing, retire eleman soti nan keu sa a, nou vle konnen kote eleman ki pi ansyen se. Se konsa, nou toujou bezwen kenbe kèk endikatè a ki kote se sa ki. Se konsa, se sa ki 0 la ki gen la pou. Sa a ki sa devan ki gen la pou. 

Se pou nou an enqueue yon sèl plis eleman, 19. Mwen si ke ou ka devine kote 19 ki pral ale. Li nan ale nan ale nan Nimewo kote etalaj 2. Sa a 0 plis 2. Epi, koulye a gwosè a nan keu nou an, se 3. Nou gen 3 eleman nan li. Se konsa, si nou te, epi nou pa ap ale a dwat koulye a, enqueue yon lòt eleman, li ta ale nan kote etalaj Nimewo 3, ak gwosè a nan nat nou an ta dwe 4. Se konsa, nou te enqueued plizyè eleman kounye a. Koulye a, kite la kòmanse yo retire yo. Se pou nou dequeue yo soti nan keu la. 

Se konsa, menm jan ak pòp, ki se sòt a analòg la nan sa a pou pil, dequeue bezwen aksepte yon konsèy nan queue-- la ankò, sof si li nan globalman te deklare. Koulye a, nou vle chanje kote a a devan nan keu la. Sa a se kote li sòt de vini nan jwe, ki varyab devan, paske yon fwa nou retire yon eleman, nou vle pou avanse pou li nan pwochen eleman ki pi ansyen. 

Lè sa a, nou vle diminye gwosè a nan keu a, ak Lè sa a nou vle retounen valè a ki te retire nan keu la. Yon fwa ankò, nou pa vle jis jete li. Nou prezimableman yo èkstraksyon li nan men queue-- nan nou ap dequeuing li paske nou pran swen sou li. Se konsa, nou vle fonksyon sa a yo retounen yon eleman done ki gen valè kalite. Yon fwa ankò, nan ka sa a, valè nonb antye relatif. 

Se konsa, kounye a kite a dequeue yon bagay. Se pou nou retire yon eleman soti nan keu la. Si nou di Int x egal & q, comercial q ankò sa a, se yon konsèy nan done sa a q structure-- sa eleman yo pral dked? Nan ka sa a, paske li se yon premye nan, premye soti done estrikti, FIFO, premye bagay la nou mete nan sa a keu te 28, e konsa nan ka sa a, nou ap ale nan pran 28 soti nan keu a, pa 19, ki se sa ki nou ta te fè si sa a te yon pil. Nou ap pral pran 28 soti nan keu la. 

Menm jan ak sa nou te fè ak yon pil, nou pa ap aktyèlman ale nan efase 28 soti nan keu la tèt li, nou ap jis ale nan kalite a pretann li se pa la. Se konsa, li k ap pase yo rete la nan memwa, men nou ap jis ale nan kalite inyore li pa deplase de lòt jaden ki te andeyò done nou an q estrikti. Nou pwal chanje devan an. Q.front se kounye a ale nan dwe 1, paske ki se kounye a eleman nan pi ansyen nou gen nan nou an keu, paske nou te deja retire 28, ki te ansyen eleman ki pi ansyen. 

Epi, koulye a, nou vle chanje gwosè a nan keu la nan de eleman olye pou yo twa. Koulye a, sonje pi bonè m 'te di lè nou vle ajoute eleman nan keu a, nou mete l 'nan yon kote etalaj ki se sòm total la nan devan ak gwosè. Se konsa, nan ka sa a, nou ap toujou mete li, eleman nan pwochen nan keu a, nan etalaj kote 3, ak nou pral wè ke nan yon dezyèm fwa. 

Se konsa, nou te kounye a dked nou an premye eleman soti nan keu la. Se pou yo fè l 'ankò. Se pou nou retire yon lòt eleman soti nan keu la. Nan ka a, aktyèl ki pi ansyen eleman se etalaj kote 1. Sa a ki sa q.front di nou. Sa ti bwat vèt di nou ke sa a, se eleman ki pi ansyen. Se konsa, x ap vin 33. Nou pral jis kalite bliye ki egziste nan 33 etalaj la, epi n ap di ke kounye a nan, nouvo eleman pi ansyen nan keu la se nan etalaj kote 2, ak gwosè a nan nat la, ki kantite eleman nou gen nan keu a, se 1. Koulye a, kite a enqueue yon bagay, ak mwen sòt de te bay sa a lwen yon dezyèm de sa, men si nou vle mete 40 an nan keu, kote nan 40 ale nan ale? Oke nou ve yo te mete l ' nan q.front plis keu gwosè, Se konsa, li fè sans nan aktyèlman yo mete 40 isit la. Koulye a, remake ke nan kèk pwen, nou ap ale pou li ale nan nan fen etalaj nou an andedan nan q, men sa ta vle chanje koulè soti 28 ak 33-- yo ap aktyèlman, teknikman espas ki louvri, dwa? Se konsa, nou ka eventually-- ki règ la pandan l ajoute sa yo de together-- nou ka evantyèlman bezwen mod pa gwosè a nan kapasite pou nou ka vlope alantou. 

Se konsa, si nou jwenn yo eleman Nimewo 10, si nou ap ranplase l 'nan kantite eleman 10, nou ta aktyèlman mete l 'nan etalaj kote 0. Men, si nou te ale nan etalaj location-- eskize m ', si nou te ajoute yo moute ansanm, epi nou te rive nan nimewo 11 ta dwe kote nou ta gen yo mete li, ki pa egziste nan sa a array-- li ta dwe ale soti nan avèk limit. Nou te kapab Mod pa 10, li mete l 'nan etalaj kote 1. Se konsa, lè sa a jan ke moun kap kriye travay. Yo toujou ap ale nan ale nan bò gòch a dwat epi pètèt vlope alantou. E ou konnen ke yo ap plen si gwosè, ki bwat wouj, vin egal a kapasite. Se konsa, apre nou te ajoute 40 a nan keu, byen ki sa nou bezwen fè? Oke, eleman ki pi ansyen nan keu a se toujou 19, se konsa nou pa vle chanje devan nan keu a, men kounye a nou gen de eleman nan keu a, epi pou nou vle ogmante gwosè nou an nan 1 rive nan 2. 

Sa a bèl anpil l 'ak travay ak ke moun kap kriye etalaj ki baze sou, ak menm jan ak chemine, gen tou se yon fason aplike yon keu kòm yon lis lye. Koulye a, si sa a ki kalite estrikti done sanble abitye nou la a, li ye. Li pa yon lis separeman lye, li nan yon lis doubl lye. Epi, koulye a, kòm yon sou kote, li se aktyèlman posib aplike yon keu kòm yon lis separeman lye, men Mwen panse ke an tèm de vizyalizasyon, li aktyèlman ta ka ede yo wè sa a kòm yon lis doubl lye. Men, li se definitivman posib yo fè sa a kòm yon lis separeman lye. 

Se konsa, kite a gen yon gade nan ki sa sa a ta ka sanble. Si nou vle enquue-- se konsa kounye a, ankò nou ap oblije chanje nan yon-lis lye baze modèl isit la. Si nou vle enqueue, nou vle ajoute yon eleman nouvo, byen ki sa nou bezwen fè? Oke, premye nan tout, paske nou ap ajoute nan fen a epi yo retire soti nan la kòmansman, nou pwobableman vle kenbe endikasyon nan la tou de tèt ak ke a nan lis la lye? Keu yo te yon lòt tèm pou nan fen lis la lye, eleman ki sot pase a nan lis la lye. Ak sa yo pral pwobableman, ankò, dwe benefisye yo ban nou si yo varyab mondyal. Men koulye a, si nou vle ajoute yon nouvo eleman sa nou dwe fè? Ki sa nou jis [? Malak?] oswa dynamique asiyen nouvo ne nou an pou tèt nou. Lè sa a,, jis renmen lè nou ajoute nenpòt eleman nan yon lis doubl lye nou, jis gen nan sòt de- moun pase twa etap isit la yo se jis tout bagay sou k ap deplase nan endikasyon nan fason ki kòrèk la se konsa ke vin eleman nan ajoute nan chèn nan san yo pa kraze chèn lan oswa fè kèk sòt de erè oswa gen kèk sòt de aksidan rive kijan nou aksidantèlman on òfelen kèk eleman nan keu nou an. Isit la nan ki sa sa a ta ka sanble. Nou vle ajoute eleman nan 10 nan fen a nan keu sa a. Se konsa, eleman ki pi ansyen isit la se reprezante pa tèt yo. Sa a premye bagay la nou mete nan sa a keu ipotetik isit la. Apre sa, ke, 13, se pi plis nan dènyèman te ajoute eleman. Se konsa, si nou vle enqueue 10 an keu sa a, nou vle mete li apre 13. Se konsa, nou ap ale nan dynamique asiyen espas pou yon nouvo ne epi tcheke pou nil a asire w nou pa gen yon echèk memwa. Lè sa a, nou ap ale nan mete 10 nan ki ne, epi kounye a nou bezwen dwe fè atansyon sou fason nou òganize endikasyon se konsa nou pa kraze chèn lan. 

Nou ka mete 10 an anvan yo jaden A ak pwen tounen nan ke a fin vye granmoun, epi depi '10 Haitian Creole Edition yo pral nan nouvo ke nan kèk pwen pa tan an tout moun sa yo chenn yo ki konekte, pa gen anyen k ap pase yo vin apre 10 kounye a. Se konsa, 10 nan pwochen konsèy pral lonje dwèt sou nil, ak Lè sa a apre nou fin fè sa, apre yo fin nou te konekte 10 bak nan chèn lan, nou ka pran tèt la fin vye granmoun, oswa, eskiz m ', ke a fin vye granmoun nan keu la. Fen a fin vye granmoun nan keu a, 13,, epi fè li lonje dwèt sou 10. Epi, koulye a, nan pwen sa a, nou gen enqueued nimewo a 10 nan keu sa a. Tout sa nou bezwen fè kounye a se jis deplase nan ke nan pwen a 10 olye pou yo a 13. 

Dequeuing se aktyèlman trè menm jan ak eklate ki sòti nan yon chemine ki se aplike kòm yon lis lye si ou te wè videyo a pil. Tout sa nou bezwen fè se kòmanse nan la kòmanse, jwenn eleman, dezyèm lan, libere eleman nan premye, ak lè sa a deplase tèt la nan pwen nan eleman, dezyèm lan. Pwobableman pi bon yo visualized li jis yo dwe klè siplemantè sou li. Se konsa, isit la nan nat nou an ankò. 12 se eleman ki pi ansyen nan keu nou an, tèt la. 10 se eleman nan dernye nan keu nou an, ke nou yo. 

Se konsa, lè nou vle dequeue yon eleman, nou vle yo retire eleman ki pi ansyen. Se konsa, sa nou fè? Oke nou mete yon konsèy parcourt ki kòmanse nan plas tèt la, epi nou avanse pou li konsa ke li lonje dwèt nan eleman an dezyèm nan sa a yon bagay lè li di queue-- Trav egal Trav flèch kap vini an, pou egzanp, ta deplase Trav gen yo lonje dwèt sou 15, ki, apre nou dequeue 12, oswa apre nou retire 12, yo pral vin eleman nan Lè sa a, pi ansyen. 

Koulye a, nou te gen yon kenbe sou premye a eleman atravè tèt la konsèy ak eleman nan dezyèm via Trav nan konsèy. Nou kapab kounye a gratis tèt, ak Lè sa a nou kapab di pa gen anyen vini anvan 15 ankò. Se konsa, nou ka chanje 15 an anvan konsèy nan lonje dwèt sou nil, epi nou jis deplase tèt la sou. Apre sa, nou ale. Koulye a, nou gen avèk siksè dked 12, epi kounye a nou gen yon lòt keu nan 4 eleman. Sa a bèl anpil tout gen nan ke moun kap kriye, tou de etalaj ki baze sou ak lye-lis baze sou. Mwen se Doug Lloyd. Sa a se CS 50.