DOUG LLOYD: Felly, os ydych chi wedi gwylio'r fideo ar simnai, Mae'n debyg mae hyn yn mynd i deimlo'n fel ychydig o Deja vu. Mae'n mynd i gysyniad debyg iawn, dim ond gydag ychydig o thro arno. Rydym yn mynd i siarad yn awr am ciwiau. Felly ciw, yn debyg i stac, math arall o strwythur data y gallwn eu defnyddio i gynnal data mewn ffordd drefnus. Yn debyg i stac, gellir ei roi ar waith fel arae neu restr cysylltiedig. Yn wahanol i stac, mae'r rheolau a ddefnyddiwn i benderfynu pan fydd pethau'n cael eu hychwanegu a'u tynnu oddi ciw yn ychydig yn wahanol. Yn wahanol pentwr, a oedd yn yn strwythur LIFO, olaf i mewn, cyntaf allan, ciw yn FIFO strwythur, FIFO, yn gyntaf yn, allan gyntaf. Nawr ciwiau, mae'n debyg cael cyfatebiaeth i ciwiau. Os ydych wedi bod erioed yn unol ar parc adloniant neu mewn banc, mae fath o degwch gweithredu strwythur. Y person cyntaf yn unol ar mae'r banc yn y person cyntaf pwy sy'n cael siarad â'r teller. 

Byddai'n fath o ras i'r gwaelod os mai'r unig ffordd rhaid i chi siarad â'r teller yn y banc oedd i fod y person olaf yn unol. Byddai pawb bob amser am i fod y person olaf yn unol, a bod y person a oedd yno yn gyntaf sydd wedi bod yn aros am ychydig, Gallai fod yno am oriau, ac oriau, ac oriau cyn iddynt gael cyfle i mewn gwirionedd tynnu unrhyw arian yn y banc. Ac felly ciwiau yn fath o tegwch gweithredu strwythur. Ond nid yw hynny'n golygu o reidrwydd bod staciau yn beth drwg, dim ond bod ciwiau yn ffordd arall i wneud hynny. Felly, unwaith eto ciw yn gyntaf i mewn, cyntaf allan, yn erbyn bentwr sy'n para i mewn, cyntaf allan. Yn debyg i stac, mae gennym ddau gweithrediadau ein bod yn gallu perfformio ar ciwiau. Mae enwau yn enqueue, sef ychwanegu elfen newydd at ddiwedd y ciw, a dequeue, sef i gael gwared ar y hynaf elfen o du blaen y ciw. Felly rydym yn mynd i ychwanegu elfennau ar ddiwedd y ciw, ac rydym yn mynd i gael gwared ar elfennau o du blaen y ciw. Unwaith eto, gyda'r stac, roeddem yn ychwanegu elfen i ben y pentwr a chael gwared ar elfennau o ben y pentwr. Felly, gyda enqueue, mae'n ychwanegu at y diwedd, cael gwared o'r tu blaen. Felly, y peth hynaf i mewn 'na bob amser yn y peth nesaf i ddod allan os ydym yn ceisio ac yn dequeue rhywbeth. 

Felly unwaith eto, gyda chiwiau, y gallwn gweithrediadau sy'n seiliedig arae- ac yn gysylltiedig-rhestr implementations yn seiliedig. Byddwn yn dechrau eto gyda gweithrediadau sy'n seiliedig ar amrywiaeth. Mae'r diffiniad Strwythur edrych yn eithaf tebyg. Mae gennym amrywiaeth arall mae data gwerth fath, fel y gellir ei ddal mathau data mympwyol. Rydym yn unwaith eto yn mynd i ddefnyddio gyfanrifau yn yr enghraifft hon. 

Ac yn union fel gyda'n gweithredu stac seiliedig array-, oherwydd ein bod yn defnyddio array, rydym reidrwydd gael y cyfyngiad sy'n C math o yn gorfodi arnom ni, sef ein bod Nid oes rhaid i unrhyw bywiogrwydd yn ein gallu i dyfu ac yn crebachu y rhesi. Mae'n rhaid i ni benderfynu ar y dechrau beth yw'r nifer mwyaf o bethau y gallwn roi i mewn i hyn ciw, ac yn yr achos hwn, Byddai gallu cael rhyw bunt a ddiffinnir yn gyson yn ein cod. Ac at ddibenion y fideo, cynhwysedd yn mynd i fod yn 10. 

Mae angen i ni gadw golwg ar flaen y ciw felly rydym yn gwybod pa elfen rydym am dequeue, ac mae angen i ni hefyd gadw golwg ar rhywbeth else-- nifer yr elfennau sydd gennym yn ein ciw. Sylwch nid ydym yn cadw golwg i ddiwedd y ciw, dim ond maint y ciw. A'r rheswm am hynny a fydd, gobeithio, dod yn dipyn cliriach mewn munud. Unwaith y byddwn wedi cwblhau diffiniad math hwn, mae gennym fath ddata newydd Gelwir ciw, a allwn yn awr yn datgan newidynnau o'r math hwnnw data. A braidd yn ddryslyd, rwyf wedi penderfynu i alw ciw hwn q, y llythyr q yn hytrach na'r math data q. 

Felly dyma yw ein ciw. Mae'n strwythur. Mae'n cynnwys tri aelod neu dri caeau, amrywiaeth o faint GALLU. Yn yr achos hwn, GALLU yw 10. Ac mae amrywiaeth hwn mynd i ddal cyfanrifau. Yn wyrdd yw flaen ein ciw, y Elfen nesaf i'w dileu, ac mewn coch Bydd maint y ciw, faint o elfennau yw ar hyn o bryd sydd eisoes yn bodoli yn y ciw. Felly, os ydym yn dweud hafal q.front 0, a maint q.size hafal 0-- rydym yn rhoi 0au i gaeau hynny. Ac yn y fan hon, rydym yn 'n bert lawer barod i ddechrau gweithio gyda'n ciw. 

Felly y llawdriniaeth gyntaf y gallwn perfformio yw enqueue rhywbeth, i ychwanegu elfen newydd i diwedd y ciw. Wel beth sydd angen i ni'n ei wneud yn yr achos gyffredinol? Wel anghenion swyddogaeth hon enqueue i dderbyn pwyntydd at ein ciw. Unwaith eto, os ydym wedi datgan ein ciw yn fyd-eang, Ni fyddai angen i ni wneud hyn o reidrwydd, ond yn gyffredinol, rydym yn Mae angen i dderbyn awgrymiadau i strwythurau data fel hyn, oherwydd fel arall, rydym yn pasio trwy value-- rydym yn pasio mewn copïau o'r ciw, ac felly nid ydym yn newid mewn gwirionedd y ciw y bwriadwn eu newid. 

Y peth arall y mae angen ei wneud yw derbyn elfen data o'r math priodol. Eto, yn yr achos hwn, mae'n mynd i fod yn cyfanrifau, ond fe allech chi fympwyol ddatgan y math data fel gwerth a defnyddio hyn yn fwy cyffredinol. Dyna'r elfen yr ydym am ei enqueue, rydym eisiau ychwanegu at ddiwedd y ciw. Yna, rydym mewn gwirionedd eisiau rhoi data hwnnw yn y ciw. Yn yr achos hwn, ei roi yn y lleoliad cywir o'n array, ac yna rydym am newid maint y ciw, faint o elfennau yr ydym yn ar hyn o bryd. 

Felly gadewch i ni ddechrau arni. Dyma, unwaith eto, fod gyffredinol Datganiad Ffurflen swyddogaeth am yr hyn y gallai enqueue edrych. A dyma ni yn mynd. Gadewch i ni enqueue rhif 28 i mewn i'r ciw. Felly, beth ydym yn mynd i'w wneud? Wel, mae'r flaen ein ciw yw ar 0, a maint ein ciw yw ar 0, ac felly mae'n debyg ein bod eisiau rhoi rhif 28 yn array rhif elfen 0, dde? Felly rydym wedi gosod nawr bod i mewn 'na. Felly nawr beth sydd angen i ni newid? Nid ydym am newid flaen y ciw, am ein bod eisiau gwybod pa elfen Efallai y bydd angen i ni dequeue yn nes ymlaen. Felly, y rheswm sydd gennym flaen yno yn fath o ddangosydd o'r hyn sydd y peth hynaf yn y casgliad. Wel y peth hynaf yn y array-- yn wir, yr unig beth yn y casgliad cywir now-- yw 28, sy'n yn y lleoliad array 0. Felly nid ydym am i newid y rhif hwnnw gwyrdd, oherwydd dyna yr elfen hynaf. Yn hytrach, rydym am newid maint. Felly, yn yr achos hwn, rydym yn chi helpu cynyddiad maint i 1. 

Erbyn hyn, mae rhyw fath o syniad cyffredinol o gyflwr lle mae'r elfen nesaf yn mynd i fynd mewn ciw yw ychwanegu rhai ddau rif gyda'i gilydd, blaen a maint, a bydd hynny'n dweud wrthych ble mae'r nesaf elfen yn y ciw yn mynd i fynd. Felly nawr gadewch i ni enqueue rhif arall. Gadewch i ni enqueue 33. Felly 33 yn mynd i fynd i mewn i Lleoliad array 0 ac 1. Felly, yn yr achos hwn, mae'n mynd i fynd i mewn i amrywiaeth leoliad 1, ac yn awr maint ein ciw yw 2. 

Unwaith eto, nid ydym yn newid flaen ein ciw, oherwydd bod 28 yn dal i fod y elfen hynaf, ac yr ydym yn eisiau canlynol-- pan fyddwn yn y pen draw yn cael i dequeuing, cael gwared ar elfennau o'r ciw hwn, rydym am wybod lle yr elfen hynaf yw. Ac felly bob amser angen i ni gynnal rhyw arwydd o ble y mae. Felly dyna beth mae'r 0 yno ar gyfer. Dyna beth blaen yno ar gyfer. 

Gadewch i ni yn enqueue un fwy o elfennau, 19. Rwy'n siwr y gallwch chi ddyfalu lle mae 19 yn mynd i fynd. Mae'n mynd i fynd i mewn i amrywiaeth rhif Lleoliad 2. Dyna 0 a 2. Ac yn awr maint ein ciw yw 3. Mae gennym 3 elfen ynddo. Felly, pe baem yn, ac nid ydym yn mynd i ar hyn o bryd, enqueue elfen arall, byddai'n mynd i mewn i leoliad array rhif 3, a maint ein ciw fyddai 4. Felly rydym wedi enqueued sawl elfen yn awr. Nawr, gadewch i ni ddechrau i gael gwared arnynt. Gadewch i ni eu dequeue o'r ciw. 

Mor debyg i pop, sydd yn didoli o analog hyn ar gyfer staciau, Mae angen dequeue i dderbyn pwyntydd i'r queue-- eto, oni bai ei fod yn datgan yn fyd-eang. Nawr rydym am newid y lleoliad o flaen y ciw. Dyma lle mae'n fath o yn dod i chwarae, y newidyn blaen, oherwydd unwaith rydym yn cael gwared elfen, rydym am i'w symud i'r elfen hynaf nesaf. 

Yna, rydym am i ostwng maint y ciw, ac yna rydym eisiau dychwelyd y gwerth a gafodd ei dynnu oddi ar y ciw. Unwaith eto, nid ydym am i ddim ond taflu iddo. Rydym yn ôl pob tebyg yn tynnu oddi ar y queue-- rydym yn dequeuing oherwydd yr ydym yn gofalu am y peth. Felly rydym am swyddogaeth hon i ddychwelyd elfen data o werth fath. Eto, yn yr achos hwn, gwerth yn gyfanrif. 

Felly nawr gadewch i dequeue rhywbeth. Gadewch i ni gael gwared ar elfen o'r ciw. Os dywedwn int x yn hafal & q, ampersand q-- unwaith eto mae hynny'n pwyntydd i hyn q data structure-- pa elfen yn mynd i gael ei dequeued? Yn yr achos hwn, oherwydd ei fod yn gyntaf i mewn, cyntaf allan strwythur data, FIFO, y peth cyntaf rydym yn rhoi i mewn i hyn Roedd ciw 28, ac felly yn yr achos hwn, rydym yn mynd i gymryd 28 allan o y ciw, nid 19, sef yr hyn byddem wedi gwneud os oedd hyn pentwr. Rydym yn mynd i gymryd 28 allan o'r ciw. 

Yn debyg i'r hyn a wnaethom gyda pentwr, dydyn ni ddim mewn gwirionedd mynd i ddileu 28 oddi wrth y ciw ei hun, rydym yn jyst yn mynd i fath o esgus nad yw yno. Felly, mae'n mynd i aros yno mewn cof, ond rydym yn unig mynd i fath o hanwybyddu drwy symud y ddau gae arall o'n q data strwythur. Rydym yn mynd i newid y tu blaen. Q.front yn awr yn mynd i fod yn 1, gan mai dyna bellach yr elfen hynaf sydd gennym yn ein ciw, gan ein bod eisoes wedi tynnu 28, sef y cyn elfen hynaf. 

Ac yn awr, rydym am newid maint y ciw i ddwy elfen yn lle tri. Nawr cofiwch y dywedais yn gynharach pan fyddwn yn eisiau ychwanegu elfennau at y ciw, rydym yn ei roi mewn lleoliad arae sef y swm o flaen a maint. Felly, yn yr achos hwn, rydym yn dal i roi hynny, yr elfen nesaf yn y ciw, i mewn i amrywiaeth lleoliad 3, a byddwn yn gweld hynny mewn eiliad. 

Felly, rydym yn awr wedi dequeued ein elfen gyntaf o'r ciw. Gadewch i ni wneud hynny eto. Gadewch i ni gael gwared ar un arall elfen o'r ciw. Yn yr achos hwn, y presennol hynaf elfen yw amrywiaeth lleoliad 1. Dyna beth q.front dweud wrthym. Bod blwch gwyrdd yn dweud wrthym fod dyna yr elfen hynaf. Ac felly, bydd yn dod yn x 33. Byddwn yn unig fath o anghofio bod 33 yn bodoli yn y array, a byddwn yn dweud hynny yn awr, mae'r Elfen hynaf newydd yn y ciw mewn amrywiaeth lleoliad 2, a maint y ciw, mae nifer o elfennau gennym yn y ciw, yw 1. Nawr, gadewch i enqueue rhywbeth, ac yr wyf yn fath o roddodd hwn i ffwrdd eiliad yn ôl, ond os ydym am roi 40 i mewn i'r ciw, lle mae wedi 40 mynd i fynd? Wel rydym wedi bod yn ei roi yn q.front yn ogystal â ciw maint, ac felly mae'n gwneud synnwyr i mewn gwirionedd i roi 40 yma. Nawr yn sylwi bod o ryw adeg, rydym yn mynd i gyrraedd y diwedd ein amrywiaeth tu mewn q, ond y pylu allan 28 a 33-- eu bod mewn gwirionedd, yn dechnegol mannau agored, dde? Ac felly, efallai y byddwn eventually-- y rheol o ychwanegu dau y rhai together-- efallai y byddwn yn y pen draw Mae angen mod gan faint o gapasiti fel y gallwn cofleidiol. 

Felly, os ydym yn cael i elfen rhif 10, os ydym yn ddisodli yn yr elfen rhif 10, byddem mewn gwirionedd yn ei roi mewn lleoliad array 0. Ac os ydym yn mynd i location-- arae esgus i mi, os byddwn yn ychwanegu i fyny at ei gilydd, ac rydym yn cael i rif Byddai 11 yn lle y byddai'n rhaid i ni roi iddo, nad yw'n bodoli yn y array-- hwn byddai'n cael ei mynd allan waharddedig. Gallem mod erbyn 10 ac yn rhoi mewn amrywiaeth lleoliad 1. Felly dyna sut y ciwiau yn gweithio. Maen nhw'n wastad yn mynd i fynd o'r chwith i'r dde ac o bosibl cofleidiol. A ydych yn gwybod eu bod yn os maint llawn, y bocs coch, yn dod yn gyfartal i gynhwysedd. Ac felly ar ôl i ni wedi ychwanegu 40 at y ciw, yn dda yr hyn sydd angen i ni ei wneud? Wel, yr elfen hynaf yn y ciw yn dal i fod 19, felly nid ydym am newid flaen y ciw, ond erbyn hyn mae gennym ddau elfennau yn y ciw, ac felly rydym yn awyddus i gynyddu ein maint 1-2. 

Dyna 'n bert lawer' i ag gweithio gyda chiwiau seiliedig arae-, ac yn debyg i'r golwg, mae hefyd yn ffordd i weithredu ciw fel rhestr cysylltiedig. Nawr, os y math hwn o strwythur data yn edrych yn gyfarwydd i chi, y mae. Nid yw'n rhestr cysylltiedig yn unigol, mae'n rhestr gysylltiedig ddwbl. Ac yn awr, wrth fynd heibio, mae'n mewn gwirionedd yn bosibl i weithredu ciw fel rhestr cysylltiedig yn unigol, ond Yr wyf yn meddwl yn nhermau delweddu, mae mewn gwirionedd fod o gymorth i weld hyn fel rhestr cysylltiedig ddwbl. Ond mae'n bendant yn bosibl i yn gwneud hyn fel rhestr cysylltiedig yn unigol. 

Felly gadewch i ni gael golwg ar beth y gallai hyn edrych. Os ydym am enquue-- felly yn awr, unwaith eto rydym yn newid i gysylltu-restr model lleoli yma. Os ydym am enqueue, rydym am i ychwanegu elfen newydd, yn dda beth sydd angen i ni ei wneud? Wel, yn gyntaf oll, oherwydd rydym yn ychwanegu at ddiwedd ac yn tynnu oddi ar y dechrau, mae'n debyg ein bod am gynnal awgrymiadau at y pennaeth a'r gynffon y rhestr cysylltiedig? Cynffon yn dymor arall ar gyfer diwedd y rhestr cysylltiedig, yr elfen olaf yn y rhestr cysylltiedig. A bydd yn ôl pob tebyg y rhain, unwaith eto, fod o fudd i ni os ydynt yn newidynnau byd-eang. Ond yn awr os ydym am ychwanegu newydd Elfen beth sy'n rhaid i ni ei wneud? Yr hyn yr ydym yn unig [? Malak?] neu ddeinamig dyrannu ein nod newydd i ni ein hunain. Ac yna, yn union fel pan fyddwn yn ychwanegu unrhyw elfen i restr rydym cysylltiedig ddwywaith, dim ond rhaid i ddidoli o- y rhai tri cham diwethaf yma yn unig popeth am symud y arwyddion yn y ffordd gywir fel bod yr elfen yn cael ei ychwanegu at y gadwyn heb dorri'r gadwyn neu wneud rhyw fath o gamgymeriad neu gael rhyw fath o ddamwain digwydd lle yr ydym yn ddamweiniol amddifad rhai elfennau o'n ciw. Dyma beth y gallai hyn edrych. Rydym eisiau ychwanegu'r elfen 10 hyd at ddiwedd ciw yma. Felly yr elfen hynaf yma cael ei gynrychioli gan ben. Dyna'r peth cyntaf rydym yn rhoi i mewn i hyn ciw damcaniaethol yma. A chynffon, 13, yw'r mwyaf Elfen ychwanegwyd yn ddiweddar. Ac felly os ydym am enqueue 10 i mewn ciw hwn, rydym am roi ar ôl 13. Ac felly rydym yn mynd i ddeinamig neilltuo lle ar gyfer nod newydd a gwirio am null i wneud yn siŵr Nid oes gennym fethiant cof. Yna, rydym yn mynd i gosod 10 i mewn i'r nod, ac yn awr mae angen i ni fod yn ofalus am sut yr ydym yn trefnu awgrymiadau felly nid ydym yn torri'r gadwyn. 

Gallwn osod 10 o faes blaenorol i bwyntio yn ôl i'r hen gynffon, ac ers '10 fydd y cynffon newydd ar ryw bwynt erbyn yr amser pob un o'r rhain cadwyni yn cael eu cysylltu, dim byd yn mynd i ddod ar ôl 10 ar hyn o bryd. Ac felly 10 yn pwyntydd nesaf Bydd pwyntio at null, ac yna ar ôl i ni wneud hyn, ar ôl i ni cysylltu 10 yn ôl i'r gadwyn, gallwn gymryd yr hen ben, neu, esgus mi, yr hen gynffon y ciw. Mae'r hen ddiwedd y ciw, 13, ac yn ei gwneud yn pwyntio at 10. Ac yn awr, ar y pwynt hwn, rydym wedi enqueued y rhif 10 i mewn i ciw hwn. Y cyfan sydd angen i ni ei wneud yn awr yw dim ond symud y gynffon i bwyntio at 10 yn lle i 13. 

Dequeuing mewn gwirionedd debyg iawn i popping o bentwr sy'n rhoi ar waith fel rhestr cysylltiedig os ydych chi wedi gweld y fideo teisi. Y cyfan sydd angen ei wneud yw dechrau ar y dechrau, dod o hyd i'r ail elfen, rhad ac am ddim yr elfen gyntaf, ac yna symud y pen i dynnu sylw at yr ail elfen. Yn ôl pob tebyg yn well i ddychmygu iddo dim ond i fod yn hynod glir am y peth. Felly dyma ein ciw eto. 12 yw'r elfen hynaf yn ein ciw, y pennaeth. 10 yw'r elfen mwyaf newydd yn ein ciw, ein gynffon. 

Ac felly pan rydym am i dequeue elfen, rydym am gael gwared ar yr elfen hynaf. Felly beth ydym ni'n ei wneud? Wel rydym yn gosod pwyntydd llwybro sy'n dechrau ar ben, ac yr ydym yn symud fel ei fod yn cyfeirio at yr ail elfen o hyn queue-- rhywbeth trwy ddweud Trav hafal Trav saeth nesaf, er enghraifft, Byddai symud Trav yno i dynnu sylw at 15, sydd, ar ôl i ni dequeue 12, neu ar ôl i ni gael gwared ar 12, bydd yn dod yn elfen yna-hynaf. 

Nawr mae gennym gafael ar y cyntaf elfen drwy'r pen pwyntydd a'r ail elfen drwy'r Trav pwyntydd. Y gallwn pen yn awr rhad ac am ddim, ac yna o fewn ein gallu yn dweud dim byd yn dod cyn 15 anymore. Felly rydym yn gallu newid 15 oed blaenorol pwyntydd i bwyntio at null, ac rydym yn unig yn symud y pen drosodd. Ac dyna ni. Nawr rydym wedi llwyddo i dequeued 12, ac yn awr rydym cael ciw arall o 4 elfen. Dyna 'n bert lawer holl mae i ciwiau, y ddau yn seiliedig arae-ac yn gysylltiedig-rhestr sy'n seiliedig ar. Rwy'n Doug Lloyd. Mae hyn yn CS 50.