DOUG LLOYD: etdik Belə ki , yığını video seyr Bu yəqin ki, hiss edir Deja Vu bir az kimi. Bu, bir çox oxşar anlayış olacaq yalnız bir az twist ilə. Biz sıralarında indi danışmaq olacaq. Belə ki, bir yığın oxşar queue, məlumat strukturu bir növ biz qorumaq üçün istifadə edə bilərsiniz ki, mütəşəkkil şəkildə məlumat. Bir yığın kimi, Bu həyata keçirilə bilər bir sıra və ya bir bağlı siyahı kimi. Bir yığın fərqli olaraq, qaydaları biz müəyyən etmək üçün istifadə ki, şeylər əlavə və çıxarılır almaq zaman bir sıra bir az fərqlidir. Bir yığın fərqli olaraq hansı bir LIFO strukturdur ilk keçən, bir sıra bir FIFO deyil ilk strukturu, FIFO, ilk. İndi yəqin ki, sıralarında sıralarında bir analogiya var. Əgər line olmuşdur varsa bir oyuncaq park və ya bank, bir ədalət sort var strukturu həyata keçirir. istiqamətində ilk şəxs bank ilk şəxsdir olan teller danışmaq olur. 

Bu yarış sort olacaq yeganə yolu əgər aşağı Siz teller danışmaq lazımdır bank xətti keçən şəxs idi. Hər kəs həmişə istəyirəm line keçən şəxs üçün, və ilk şəxs orada olan olan, bir müddət gözləyir edilmişdir saat ola bilər, və saat və saat onlar həqiqətən etmək imkanı var əvvəl bankda pul geri. Və belə sıralarında sort var ədalət strukturu həyata keçirir. Amma mütləq demək deyil çıxarıcı borular yalnız pis bir şey var ki, sıralarında bunu başqa bir yolu var ki,. Belə ki, yenə bir sıra ilk ilk həyata davam bir yığını qarşı, ilk. Bir yığın kimi, biz iki əməliyyatları biz sıralarında çıxış edə bilər. adlar əlavə etmək üçün olan enqueue var növbə sonunda yeni bir element, və dequeue, qədim aradan qaldırılması üçün növbə önünə gələn element. Beləliklə, biz elementləri əlavə olacaq Növbədə sonunda üzərinə, və biz elementləri aradan qaldırılması olacaq növbə önünə gələn. Yenə yığını ilə, biz əlavə edildi yığını üst elementləri və elementləri aradan qaldırılması yığını üst. Enqueue ilə Belə ki, əlavə edir ön aradan qaldırılması sonu. Orada ən qədim şey belə hər zaman yanında şey biz cəhd çıxıb və bir şey dequeue. 

Belə ki, yenə sıralarında, biz edə bilərsiniz array-based tətbiq və bağlı siyahısı tətbiq əsaslanır. Biz yenidən başlamaq lazımdır array-based tətbiq. strukturu müəyyən olduqca oxşar görünür. Biz bir sıra var orada data type dəyər, belə ki, ixtiyari məlumat növləri aça bilər. Biz yenə istifadə etmək olacaq Bu misalda integers. 

Və yalnız ilə kimi bizim array-based yığını həyata keçirilməsi, Biz istifadə etdiyiniz çünki array, biz mütləq ki məhdudiyyət var ki, C cür bir biz olan bizə tətbiq hər hansı bir dinamizm yoxdur bizim inkişaf və array shrink imkanı. Biz əvvəlində qərar var şeyi maksimum sayı nə biz bu qoya bilər ki, queue, və bu halda, gücü bəzi funt olardı bizim kodu daimi müəyyən edilmişdir. Bu məqsədləri üçün video, gücü 10 olacaq. 

Biz takip lazımdır növbə ön belə ki, biz hansı element bilirik biz dequeue istəyirəm, və biz də takip lazımdır bir şey elementlərinin sayını else-- biz növbə var. Biz takip saxlanılması deyilik edək sıranın sonunda, yalnız növbə ölçüsü. Və səbəbi ümid olacaq bir anda bir az dəqiqləşəcək. Biz başa sonra bu cür müəyyən, biz yeni data növü , növbə adlanan biz indi bilərsiniz ki, data növü dəyişənlərin elan. Və bir qədər dolaşıq, mən qərar qəbul etdik Məktubda bu queue q zəng etmək üçün əvəzinə data type Q q. 

Belə ki, burada bizim queue edir. Bu strukturu. Bu üç üzvləri və ya üç ehtiva sahələri, ölçüsü gücü bir sıra. Bu halda, gücü 10 edir. Bu array var integers keçirəcəyik. Yaşıl bizim növbə ön edir növbəti element çıxarılır və qırmızı olunacaq növbə ölçüsü olacaq, neçə elementləri hazırda növbə mövcud. Biz q.front bərabərdir demək Belə ki, 0, və q.size ölçüsü bərabərdir 0- biz bu sahələrə 0s qoyulması edirik. Və bu nöqtədə, biz olduqca çox istəyirik Bizim növbə ilə iş başlamaq üçün hazır. 

Belə ki, ilk əməliyyat biz yerinə bir şey enqueue üçün, bir yenisini əlavə etmək növbə sonu. Yaxşı biz nə lazımdır ümumi halda nə? Yaxşı bu funksiya ehtiyaclarını enqueue Bizim növbə bir göstərici qəbul edəcək. Yenə elan olsaydı qlobal bizim queue, biz bunu lazım deyil mütləq, lakin, ümumiyyətlə, biz göstəricilərinə qəbul etmək lazımdır data strukturları bu kimi başqa, çünki, Biz istəyirik dəyər ilə keçən edirik növbə nüsxədə keçən, və biz, həqiqətən, dəyişən deyilik biz dəyişdirmək niyyətində queue. 

Bu nə etmək lazımdır başqa bir şey qəbul edir müvafiq tipli data element. Yenə bu halda, bu integers olacaq, ancaq özbaşına bilər dəyəri kimi data type elan və daha çox, ümumiyyətlə bu istifadə edin. Ki, biz enqueue istədiyiniz element var Biz queue sonuna əlavə etmək istəyirəm. Sonra biz, həqiqətən istəyirəm növbə data yer. Bu halda, yerləşdirilməsi bizim serialın düzgün yer, sonra biz ölçüsünü dəyişdirmək istəyirəm Növbədə, neçə elementləri biz Hal-hazırda var. 

Belə ki, başlamaq bildirin. Burada yenə, ümumi ki, forması funksiyası bəyannamə enqueue kimi baxmaq bilər nə üçün. Və burada biz gedin. Nömrəsi enqueue edək Növbə daxil 28. Belə ki, nə biz nə edəcəyik? Bəli, bizim növbə ön 0, və növbə ölçüsü 0 və biz yəqin ki, qoymaq istəyirik array element sayı sayı 28 0, sağ? Belə ki, indi orada ki, yerləşdirmişəm. Belə ki, indi biz dəyişdirmək lazımdır? Biz dəyişmək istəmirik növbə ön, biz nə element bilmək istəyirəm, çünki biz sonra dequeue lazımdır. Belə ki, səbəbi ön var nə göstəricisi sort array ən qədim şey. Yaxşı serialın ən qədim şey Əslində serialda tək şey doğru , indi olan 28 array yeri 0. Beləliklə, biz istəmirik ki, yaşıl sayı dəyişə çünki qədim element var. Əksinə, biz ölçüsünü dəyişdirmək istəyirik. Belə ki, bu halda, biz lazımdır 1 ölçüsü arttırmayı. 

Harada ideyasının indi ümumi sort növbəti element növbəyə getmək üçün gedir bu iki ədəd əlavə etmək birlikdə, ön və ölçüsü, ki, növbəti sizə deyim növbə element getmək üçün gedir. Belə ki, indi bir sıra enqueue imkan verir. 33 enqueue edək. Belə ki, 33 getmək üçün gedir array yeri 0 plus 1. Bu halda, belə ki, gedir array yeri 1 getmək üçün, və indi növbə ölçüsü 2 edir. 

Yenə dəyişən deyilik bizim növbə ön, 28 hələ, çünki qədim element və biz biz nəhayət almaq zaman, istədiyiniz to-- elementləri aradan qaldırılması, dequeuing üçün Bu növbə, bilmək istəyirəm burada qədim elementidir. Və belə ki, biz həmişə saxlamaq lazımdır ki, harada bir göstəricisidir. Belə ki, 0 var nə var. Bu ön var nə var. 

Enqueue nin daha bir element, 19 edək. Mən tahmin edə bilərsiniz eminim burada 19 getmək üçün gedir. Bu getmək olacaq array yeri sayı 2. Ki, 0 plus 2 var. İndi bizim növbə ölçüsü 3. Biz bu 3 elementləri var. Beləliklə, biz idi və biz fikrində deyilik əgər indi, başqa bir element enqueue Bu array yeri daxil getmək olardı 3 nömrəli və növbə size 4 olardı. Beləliklə, biz artıq bir neçə elementləri enqueued etdik. İndi onların aradan qaldırılması üçün başlamaq edək. Nin növbə onları dequeue edək. 

Sort olan pop belə oxşar çıxarıcı borular üçün bu analoq, dequeue bir qəbul etmək lazımdır daha Sıraya göstərici, halda qlobal elan edir. İndi biz yerinin dəyişməsini istəyir queue qarşısında. Bu cür gəlir yerdir dövrəyə ki, ön dəyişən, biz aradan qaldırılması bir dəfə, çünki bir element, biz istəyirik növbəti qədim element üçün hərəkət etmək. 

Sonra biz azaltmaq istəyirəm növbə ölçüsü, sonra biz dəyər qayıtmaq istəyirəm ki, növbə çıxarıldı. Yenə biz yalnız imtina etmək istəmirəm. Biz ehtimalla çıxarılması biz istəyirik Sıraya onu biz bu barədə qayğı, çünki onu dequeuing. Beləliklə, biz bu funksiya qayıtmaq istəyirəm növü dəyərinin data element. Yenə bu halda, dəyəri tam deyil. 

Belə ki, indi bir şey dequeue edək. Nin növbə bir element aradan qaldırılması edək. Biz demək olarsa int x bərabərdir & q, işareti Q yenidən bu q data bir göstərici var quruluşu nə element dequeued olacaq? Bu halda, bu bir ilk, çünki ilk data strukturu, FIFO həyata, Biz bu qoymaq ki, ilk şey queue 28 idi, və bu halda, biz həyata 28 etmək olacaq nədir queue deyil, 19, bu bir yığın, əgər biz edərdi. Biz növbə həyata 28 etmək olacaq. 

Biz nə bənzər bir yığın, biz, həqiqətən deyilik 28 silmək üçün gedir növbə özü, biz yalnız cür olacaq o yoxdur iddia. Belə ki, orada qalmaq olacaq yaddaş, lakin biz yalnız istəyirik cür hərəkət ignore gedir Bizim q məlumatların digər iki sahələri quruluşu. Biz ön dəyişiklik olacaq. Q.front indi gedir ki, indi, çünki 1 olmaq biz var qədim element bizim queue, biz artıq 28 xaric etdik, çünki, olan keçmiş qədim element idi. 

İndi biz dəyişdirmək istədiyiniz növbə size iki elementləri əvəzinə üç. İndi xatırlayıram əvvəllər dediyim zaman sıra elementləri əlavə etmək istəyirəm, biz bir sıra yeri qoyun olan ön və ölçüsü cəmidir. Bu halda, belə ki, biz hələ qoyulması edirik ki, növbə növbəti element, array yeri 3 və daxil biz ikinci görəcəksiniz. 

Beləliklə, biz indi dequeued etdik bizim Növbədə ilk element. Yenidən bunu edək. Başqa bir aradan qaldırılması imkan növbə element. Qədim halda, cari element array yeri 1. Ki q.front bizə deyir nə. Ki, yaşıl qutu bizə deyir ki, ki, qədim element var. Belə ki, x 33 olacaq. Biz yalnız cür unutmaq lazımdır 33 array var ki, və biz ki, demək lazımdır Növbədə olan yeni qədim element array yeri 2 və ölçüsü edir elementlərin növbə sayı biz növbə, 1 var. İndi bir şey enqueue imkan və mən sort, ikinci əvvəl bu üz verdi lakin biz daxil 40 qoymaq istəyirsinizsə queue harada 40 getmək olacaq? Yaxşı biz bunu qoyulması olduğunuz q.front plus queue ölçüsü, və buna anlamlı əslində burada 40 qoymaq. İndi fark bəzi point, gedirik sonuna almaq üçün q daxilində bizim array, lakin 28 və solğun 33-- onlar texniki, həqiqətən istəyirik açıq fəzalarında, sağ? Və belə ki, biz eventually-- bilər əlavə qayda Bu iki together-- biz nəhayət bilər tutumu ölçüsü mod lazımdır belə ki, biz ətrafında kesmek olar. 

Biz element almaq əgər belə Biz əgər 10 nömrə element sayı 10 əvəz biz istədiyiniz həqiqətən array yeri 0 qoyun. Və biz üçün gedir, əgər array pardon yerlerde, biz birlikdə onları əlavə əgər, və biz sayı var Biz qoymaq harada 11 olacaq Bu, hansı bu serialın mövcud deyil Bu həddi həyata gedən olardı. Biz 10 mod və qoymaq bilər Bu array yeri 1. Belə ki, sıralarında necə var. Onlar həmişə soldan getmək olacaq sağ və bəlkə ətrafında kesmek. Və onlar bilirik ki, tam əgər ölçüsü, qırmızı qutusu ki, tutumu bərabər olur. Və biz 40 əlavə etdik ki, sonra queue, yaxşı biz nə üçün lazımdır? Yaxşı, qədim element növbə hələ 19 belə ki, biz dəyişdirmək istədiyiniz yoxdur növbə ön, Amma indi biz iki növbəyə elementləri, və biz artırmaq istəyirik 1-dən 2 ölçüsü. 

Bu olduqca çox ilə var array-based sıralarında ilə iş, və dəstə oxşar, bir yol da var bir bağlı siyahı kimi bir sıra həyata keçirmək. İndi bu data structure növü sizə tanış görünür, bu. Bu, bir story bağlı siyahı deyil bir ikiqat bağlı siyahısı. İndi bir kənara kimi, o, həyata keçirilməsi üçün faktiki olaraq mümkün bir story bağlı siyahı kimi bir sıra, lakin Mən vizual baxımından hesab edirəm ki, Bu, həqiqətən keçirmək üçün kömək edə bilər bir ikiqat bağlı siyahısı kimi, bu. Amma bu mütləq mümkündür bir story bağlı siyahı kimi bunu. 

Belə ki, bir nəzər salaq nə bu kimi ola bilər. Biz enquue-- istəyirsinizsə belə ki, indi, daha istəyirik bir bağlı siyahısına keçid Burada model əsaslanır. Biz enqueue istəyirsinizsə, biz istəyirik yaxşı, yeni bir element əlavə etmək biz nə üçün lazımdır? Ilk növbədə, yaxşı, çünki sonuna əlavə edirik və aradan qaldırılması başlayan, biz yəqin ki, həm də göstəricilərinə saxlamaq istəyirik baş və bağlı siyahı quyruq? Tail üçün bir müddət olan bağlı siyahı sonunda, bağlı siyahısında son element. Və bu, yəqin ki, olacaq yenə bizə faydalı ola Onlar qlobal dəyişənlər əgər. Amma indi biz yeni bir əlavə etmək istəyirsinizsə element biz nə etmək lazımdır? Biz yalnız [? malak?] və ya dinamik özümüz üçün yeni node ayrılması. Biz hər hansı bir əlavə Və sonra, yalnız kimi bir ikiqat bağlı siyahısı biz element, yalnız of-- düzmək lazımdır burada bu son üç addımlar yalnız bütün hərəkət haqqında düzgün şəkildə göstəricilər ki, element əlavə edilir zənciri pozmadan zəncir və ya səhv bir növ edilməsi və ya qəza bir növ olan vasitəsi biz təsadüfən baş Bizim növbə bəzi elementləri yetim. Bu kimi baxmaq bilər nə. Biz element əlavə etmək istəyirəm Bu növbə sonuna 10. Burada qədim element So rəhbəri ilə təmsil olunur. Yəni biz qoymaq ilk şey Burada bu hipotetik növbə daxil. Və quyruq, 13, ən çox Bu yaxınlarda element əlavə edib. Və belə ki, biz 10 enqueue istəyirsinizsə Bu queue, biz 13 sonra onu qoymaq istəyirəm. Və belə ki, biz dinamik olacaq yeni node üçün yerin ayrılması və əmin null kontrol biz yaddaş uğursuzluq yoxdur. Sonra biz olacaq ki node daxil 10 yer, və indi biz ehtiyatlı olmaq lazımdır biz göstəricilərinə təşkil necə haqqında belə ki, biz zəncir qırmaq deyil. 

10 əvvəlki sahəyə bilərsiniz Köhnə quyruq geri qeyd etmək, və '10 ildən bəri olacaq bir nöqtədə yeni quyruq bütün bunlar vaxt zəncirlər bağlıdır, heç bir şey gəlib olacaq sonra 10 indi. Və belə 10-nin növbəti pointer null qeyd edəcək, biz sonra və sonra biz bunu sonra , zəncir 10 geri bağlı biz köhnə baş, və ya, bəhanə bilər Mənə növbə köhnə quyruq. Növbədə köhnə sonu, 13 və 10 qeyd etmək. İndi, bu nöqtədə, biz Bu sıraya daxil sayı 10 enqueued. Biz indi nə etmək lazımdır Bütün yalnız hərəkət edir quyruq 10 əvəzinə 13 qeyd etmək. 

Dequeuing əslində yaratma çox oxşar bir yığını bir bağlı siyahı həyata Siz çıxarıcı borular video gördüm əgər. Biz nə etmək lazımdır bütün başlamaq başlayan ikinci element tapmaq, ilk element pulsuz, və sonra baş hərəkət ikinci element qeyd etmək. Yəqin ki, daha yaxşı görüntüləmək üçün yalnız bu barədə əlavə aydın olmalıdır. Belə ki, burada bizim queue yenidən var. 12 qədim element Bizim növbə, baş. 10 yeni elementidir Bizim növbə, bizim quyruq. 

Və belə ki, biz istədiyiniz zaman bir element dequeue, biz qədim element çıxarmaq istəyirik. Beləliklə, biz nə etməliyəm? Yaxşı bir traversal göstərici müəyyən ki, baş başlayır və biz belə hərəkət ki, İkinci element göstərir Bu Trav deyərək bir şey Sıraya Trav növbəti arrow bərabərdir, məsələn, qeyd var Trav hərəkət olardı Biz 12 dequeue sonra, 15, Biz 12 aradan qaldırılması sonra və ya, olacaq sonra qədim element olur. 

İndi biz ilk bir gözləməyə var pointer baş vasitəsilə element və ikinci element pointer trav vasitəsilə. Biz indi pulsuz rəhbərlik edə bilər, və sonra biz heç bir şey artıq 15 əvvəl gəlir deyirlər. Beləliklə, biz 15 əvvəlki dəyişə bilərsiniz pointer null qeyd etmək, və biz yalnız baş üzərində hərəkət. Və biz getmək. İndi biz uğurla var 12 dequeued və indi biz 4 elementləri bir sıra var. Olduqca çox bütün var , sıralarında var həm array-based və bağlı siyahısı əsaslanır. Mən Doug Lloyd edirəm. Bu CS 50.