Doug LLOYD: Tātad, ja jūs esat noskatījos video par steku, Tas ir iespējams, gatavojas justies tāpat mazliet deja vu. Tas būs ļoti līdzīgu koncepciju, tikai ar nelielu vērpjot par to. Mēs ejam tagad runāt par rindām. Tātad rinda, līdzīgs kaudze, ir cita veida datu struktūras ka mēs varam izmantot, lai saglabātu dati organizētā veidā. Līdzīgi kaudze, to var īstenot kā masīvu vai saistītajā sarakstā. Atšķirībā no skursteņiem, noteikumi ka mēs izmantojam, lai noteiktu kad lietas iegūt pievienot un izņemt no rinda ir mazliet atšķirīgs. Atšķirībā kaudze, kas ir LIFO struktūra, pēdējais iekšā, pirmais ārā, rinda ir FIFO struktūra, FIFO, pirmais iekšā, pirmais ārā. Tagad rindas, jūs, iespējams, ir analoģija ar rindām. Ja esat kādreiz bijuši rindā pie atrakciju parks vai bankā, tur ir sava veida taisnīguma īstenošanas struktūru. Pirmā persona rindā pie banka ir pirmā persona kas izpaužas runāt ar stāstītājs. 

Tas būtu sava veida sacīkstes uz leju, ja vienīgais veids jums runāt ar stāstītājs tajā banka bija pēdējais cilvēks rindā. Ikviens vienmēr vēlēties ir pēdējā persona līniju, un persona, kas bija tur pirmais kurš gaidīja brīdi, varētu būt tur stundām, un stundas, un stundas pirms tie ir iespēja reāli izņemt naudu bankā. Un tā rindas ir sava veida taisnīgums īstenošanas struktūru. Bet tas nebūt nenozīmē, ka skursteņi ir slikti, tikai ka rindas ir vēl viens veids, kā to darīt. Tātad atkal rinda ir pirmais iekšā, pirmais ārā, salīdzinot kaudze, kas pēdējo reizi, pirmais ārā. Līdzīgi kaudze, mums ir divas operācijas ka mēs varam veikt uz rindas. Šie vārdi ir Enqueue, kas ir pievienot jauns elements līdz beigām rindā, un dequeue, kas ir noņemt vecākā elements no priekšā rindā. Tātad mēs ejam, lai pievienotu elementus uz rindas beigās, un mēs ejam, lai novērstu elementu no priekšpuses rindā. Atkal, ar steku, mēs pievienojot elementi uz augšējās un likvidējot elementus no augšas kaudze. Tātad ar Enqueue, tā pievienojot beigām, noņemot no priekšpuses. Tātad vecākā lieta tur vienmēr nākamā lieta iznākt, ja mēs cenšamies un dequeue kaut ko. 

Tātad vēlreiz, ar rindām, mēs varam masīvs bāzes implementāciju un saistīta sarakstu balstītu implementāciju. Mēs sāksim no jauna ar masīvs bāzes implementāciju. Struktūra definīcija izskatās diezgan līdzīgi. Mums ir vēl viena masīva tur datu tipa vērtību, tāpēc tas var būt patvaļīgu datu tipu. Mēs atkal gatavojas izmantot skaitļu šajā piemērā. 

Un tāpat kā ar mūsu masīvs bāzes kaudze īstenošana, tāpēc, ka mēs esam, izmantojot masīvs, mēs vienmēr ir, ka ierobežojums, kas C veida no īsteno uz mums, kas esam mēs nav nekādu dinamiku mūsu spēju augt un sarauties masīvs. Mums ir jāizlemj sākumā kas ir maksimālais skaits, lietas ka mēs varam nodot šo rinda, un šajā gadījumā, jauda varētu būt daži mārciņa noteikts konstants mūsu kodu. Un no šī vajadzībām video, jauda būs 10. 

Mums ir nepieciešams, lai sekotu priekšējā rindā tāpēc mēs zinām, kurš no šiem elementiem mēs vēlamies dequeue, un mums ir arī nepieciešams, lai sekotu kaut else-- elementu skaitu ka mums ir mūsu rindā. Ievērojiet, mēs neesam sekotu no rindas beigās, tikko lielums rindā. Un iemesls, kas, cerams kļūt mazliet skaidrāka brīdi. Kad mēs esam pabeiguši šāda definīcija, mums ir jauns datu tipu sauc rinda, kurā mēs varam tagad deklarēt mainīgos šī datu tipu. Un nedaudz maldinoši, es esmu nolēmis lai izsauktu šo rindas q, vēstule q vietā Datu tipa q. 

Tātad, šeit ir mūsu rinda. Tā ir struktūra. Tā sastāv no trim locekļiem vai trīs lauki, masīvs lieluma jaudu. Šajā gadījumā, jauda ir 10. Un tas ir masīvs gatavojas rīkot veseli skaitļi. Zaļā krāsā ir priekšā mūsu rindā, tad blakus elements, kas izņemta, un sarkanā krāsā būs izmēru no rindas, cik elementi ir šobrīd esošo rindā. Tātad, ja mēs sakām q.front Vienāds 0, un q.size izmērs ir vienāds 0-- mēs esam liekot 0s šajās jomās. Un šajā brīdī, mēs esam diezgan daudz gatavs sākt strādāt ar mūsu rindā. 

Tātad pirmais operācija mēs varam veikt ir ierindod kaut, pievienot jaunu elementu beigām, rindā. Nu ko mums vajag, lai darīt vispārējā gadījumā? Nu šī funkcija ierindod vajadzībām pieņemt rādītāju uz mūsu rindā. Atkal, ja mēs būtu deklarēta Mūsu rinda pasaulē, mēs nebūtu tas jādara obligāti, bet vispār, mēs nepieciešams pieņemt norādes to datu struktūras kā šis, jo pretējā gadījumā, mēs esam garām value-- mēs esam iet uz kopijas rindā, un tāpēc mēs esam ne faktiski nemainot rinda, ka mēs plānojam mainīt. 

Otra lieta, tas ir jādara, ir pieņemt datu elements no attiecīgā tipa. Atkal, šajā gadījumā, tas ir būs veseli skaitļi, bet jūs varētu patvaļīgi atzīt datu tipu kā vērtību un izmantot to vispār. Tas ir elements, mēs vēlamies ierindod, mēs vēlamies pievienot rindas beigās. Tad mēs tiešām gribam izvietot ka dati rindā. Šajā gadījumā, ievietojot to pareizs izvietojums mūsu masīvs, un tad mēs gribam mainīt izmēru rindā, cik daudzi elementi Mums pašlaik ir. 

Tātad, pieņemsim sāktu. Te ir, atkal, ka vispārējā forma funkcija deklarācija par to, ko Enqueue varētu izskatīties. Un šeit mēs iet. Pieņemsim ierindod skaitu 28. rindā. Tātad, ko mēs gatavojamies darīt? Nu, priekšā mūsu rindā ir pie 0, un lielumu mūsu rindas ir 0, un tāpēc mēs, iespējams, vēlas likt skaits 28 masīva elementu skaits 0, labi? Tāpēc mēs esam tagad novietoti ka tur. Tāpēc tagad, ko mums vajag, lai mainītu? Mēs nevēlamies, lai mainītu priekšējā rindā, jo mēs vēlamies zināt, kāda elementa mums var būt nepieciešams dequeue vēlāk. Tātad iemesls mums ir priekšā tur ir sava veida indikators par to, kas ir vecākā lieta masīvā. Nu vecākā lieta array-- in Fakts, vienīgā lieta masīva tiesības now-- ir 28, kas ir pie masīva atrašanās vietā 0. Tāpēc mēs nevēlamies mainīt šo zaļo numuru, jo tas ir vecākā elements. Drīzāk, mēs gribam mainīt izmēru. Tātad šajā gadījumā, mēs pieauguma lielumu līdz 1. 

Tagad vispārēja veida ideju, kur Nākamais elements ir gatavojas iet rindā ir pievienot šos divus skaitļus kopā, priekšā un izmērs, un kas būs, ja pateiks, nākamais elements rindā gatavojas iet. Tāpēc tagad pieņemsim ierindod citu numuru. Pieņemsim ierindod 33. Tātad 33 gatavojas iedziļināties masīvs location 0 plus 1. Tātad šajā gadījumā, tas notiek iedziļināties masīva vietā 1, un tagad lielums mūsu rindā ir 2. 

Atgādināsim, ka mēs esam nemainot priekšējo mūsu rindā, jo 28 joprojām ir vecākais elements, un mēs gribu kuri paredzēti, kad mēs beidzot nokļūt līdz dequeuing, noņemot elementus no šīs rindas, mēs vēlamies zināt kur vecākā elements ir. Un tāpēc mums vienmēr ir nepieciešams saglabāt daži rādītājs, kur tas ir. Tātad, tas ir tas, ko 0 ir tur. Tas ir tas, ko priekšā ir tur. 

Let 's Enqueue vēl viens elements, 19. Es esmu pārliecināts, ka jūs varat uzminēt kur 19 gatavojas iet. Tas būs iedziļināties masīvs vietas numurs 2. Tas ir 0 plus 2. Un tagad lielums mūsu rindā ir 3. Mums ir 3 elementi tajā. Tātad, ja mēs, un mēs nebrauksim tieši tagad, ierindod citu elementu, tas varētu iedziļināties masīva vietā numurs 3, un lielumu mūsu rindā būtu 4. Tāpēc mēs esam enqueued vairāki elementi tagad. Tagad sāksim, lai tos novērstu. Pieņemsim dequeue tos no rindas. 

Tik līdzīgs pop, kas ir sava veida no analogās uz to, lai skursteņi, dequeue nepieciešams pieņemt rādītāju uz queue-- atkal, ja vien tas ir visā pasaulē pasludināts. Tagad mēs gribam mainīt atrašanās vietu no priekšpuses rindā. Tas ir, ja tā veida runa spēlē, ka priekšā mainīgs, jo, kad mēs noņemam elements, mēs gribam lai to pārvietotu uz nākamo vecāko elementa. 

Tad mēs gribam, lai samazinātu lielums rindā, un tad mēs gribam atgriezties vērtību kas tika izslēgta no rindas. Atgādināsim, ka mēs nevēlamies, lai tikai atbrīvoties. Mēs, iespējams, ir ieguves tas no queue-- mums esi dequeuing to, jo mēs rūpējamies par to. Tāpēc mēs vēlamies, lai šī funkcija, lai atgrieztos datu elements tipa vērtības. Atkal, šajā gadījumā, vērtība ir vesels skaitlis. 

Tāpēc tagad pieņemsim dequeue kaut ko. Pieņemsim izņemt elements no rindas. Ja mēs sakām, int x vienāds & q, Ampersand q-- atkal tas ir rādītājs, lai šo q datiem structure-- ko elements tiks dequeued? Šajā gadījumā, jo tas ir pirmais iekšā, pirmais ārā datu struktūra, FIFO, pirmā lieta, mēs nodots šis rinda bija 28, un tā šajā gadījumā, mēs spēsim pieņemt 28 no rinda, ne 19, kas ir tas, ko mēs būtu darījuši, ja tas bija kaudze. Mēs ejam, lai 28 no rindā. 

Līdzīgi tam, ko mēs darījām ar kaudze, mēs esam faktiski nav gatavojas dzēst 28 no rindas pati, mēs esam tikai gatavojas veida no izlikties tā tur nav. Tātad tas notiek tur palikt atmiņā, bet mēs esam tikai gatavojas veida ignorēt to, pārvietojot Pārējie divi lauki mūsu q datu struktūra. Mēs ejam, lai mainītu priekšā. Q.front tagad gatavojas ir 1, jo tas ir tagad vecākā elements mums ir mūsu rinda, jo mēs esam jau noņemts 28, kas bija bijušais vecākais elements. 

Un tagad, mēs gribam mainīt lielums rindā līdz trim diviem elementiem, nevis. Tagad atceros, agrāk es teicu, kad mēs vēlaties pievienot elementus rindā, mēs ieliekam to masīva vietā kas ir no priekšpuses un lielumu summa. Tātad šajā gadījumā, mēs joprojām liekot tā, nākamais elements rindā, uz masīvu vietā 3, un mēs redzam, ka sekundē. 

Tāpēc mēs esam tagad dequeued mūsu Pirmais elements no rindas. Darīsim to vēlreiz. Pieņemsim noņemt cits elements no rindas. Gadījumā, pašreizējā vecākā elements ir masīvs vieta 1. Tas ko q.front stāsta mums. Ka green box stāsta mums, ka tas ir vecākā elements. Un tā, x kļūs 33. Mēs tikko veida aizmirst ka 33 pastāv masīva, un mēs sakām, ka tagad, tad Jaunais vecākā elements rindā ir masīvs vietā 2, un lielumu no rindā, skaits elementu mums ir rindā, ir 1. Tagad pieņemsim ierindod kaut ko, un es kārtot sniedza šo prom otrs atpakaļ, bet, ja mēs gribam, lai 40 Into rinda, kur ir 40 gatavojas iet? Nu mēs esam liekot to in q.front plus rindas izmēru, un tāpēc tas ir jēga, lai faktiski likt 40 šeit. Tagad ievēroju, ka pie Kādā brīdī, mēs ejam nokļūt līdz beigām Mūsu masīvs iekšpusē q, bet izbalējis no 28. un 33-- viņi patiesībā, tehniski atklātas vietas, vai ne? Un tā, mēs varam eventually-- ka noteikums, pievienojot šie divi together-- mēs varam beidzot nepieciešams mod ar izmēru jaudu lai mēs varētu aptīt ap. 

Tātad, ja mēs uz elementu numuru 10, ja mēs esam aizstājot to elementu skaitu 10, mēs gribētu faktiski nodot to masīva atrašanās vietā 0. Un, ja mēs gatavojamies masīvs location-- atvainojiet, ja mēs pievienot tos kopā, un mēs saņēmām uz numuru 11 būtu, ja mums būtu likts tas, kas neeksistē šajā array-- tas būtu iet ārpus robežām. Mēs varētu mod ar 10 un nodot tas ir masīva vietā 1. Tātad tas, kā rindas strādāt. Viņi vienmēr gatavojas aiziet no kreisās uz labo pusi, un, iespējams, wrap ap. Un jūs zināt, ka viņi pilna ja izmēra, ka sarkanā lodziņa, kļūst vienāds ar jaudu. Un tā, kad mēs esam pievienojuši 40 uz rinda, arī to, kas mums jādara? Nu, vecākā elements rindā ir vēl 19, tāpēc mēs nevēlamies, lai mainītu priekšējā rindā, bet tagad mums ir divi elementi rindā, un tāpēc mēs vēlamies palielināt Mūsu izmērs no 1 līdz 2. 

Tas ir diezgan daudz to ar strādājot ar masīvu bāzes rindas, un līdzīgi kaudze, ir arī veids īstenot rindā kā saistīts sarakstā. Tagad, ja šī datu struktūra tips izskatās pazīstams ar jums, tā ir. Tas nav atsevišķi saistīts saraksts, tas ir divtik saistīts saraksts. Un tagad, kā malā, tas ir reāli iespējams īstenot rinda kā atsevišķi saistīta sarakstā, bet Es domāju, ka attiecībā uz vizualizāciju, tas tiešām var palīdzēt, lai skatītos tas kā divkārt saistīta sarakstā. Bet tas noteikti ir iespējams darīt kā atsevišķi saistīta sarakstā. 

Tātad, pieņemsim ir apskatīt ko tas varētu izskatīties. Ja mēs gribam, lai enquue-- Tāpēc tagad, atkal mēs esam pārejot uz saistītā sarakstā orientētu modeli šeit. Ja mēs vēlamies, lai ierindod, mēs gribam pievienot jaunu elementu, labi Ko mums darīt? Nu, pirmkārt, tāpēc, ka mēs pievienojot līdz beigām un noņemot no sākuma, mēs, iespējams, vēlas saglabāt norādes gan galva un aste saistītā saraksta? Aste ir cits apzīmējums beigām, kas saistīts saraksta, pēdējais elements saistīts sarakstā. Un šie būs iespējams, atkal būt izdevīga mums ja tie ir globālie mainīgie. Bet tagad, ja mēs gribam, lai pievienotu jaunu elements, ko mums ir jādara? Ko mēs vienkārši [? malak?] vai dinamiski piešķirt mūsu jauno mezglā sev. Un tad, tāpat kā tad, kad mēs pievienot kādu elements divkārt saistīta saraksta mēs, vienkārši ir, lai sakārtotu of-- šie pēdējie trīs soļi šeit ir tikai visu par pārvietojot norādes, kas pareizi tā, ka šis elements tiek pievienots ķēdi, nesalaužot ķēdi vai veikt kaut kādas kļūdas veida vai kam ir kāda negadījuma veida notikt kuru mēs nejauši bāreņu daži no mūsu rindā elementus. Lūk, ko tas varētu izskatīties. Mēs vēlamies, lai pievienotu šo elementu 10 līdz beigām šo rindā. Tātad vecākā elements šeit pārstāv galvu. Tas ir pirmais, ko mēs ieliekam šajā hipotētiskajā rindā šeit. Un astes, 13, ir visvairāk Nesen pievienotās elements. Un tāpēc, ja mēs gribam, lai ierindod 10 uz šī rinda, mēs vēlamies, lai tā pēc 13. Un tā mēs ejam, lai dinamiski piešķirt telpas uz jaunu mezglu un pārbaudīt null, lai pārliecinātos, mums nav atmiņas mazspēja. Tad mēs ejam izvietot 10 minētajā mezglā, un tagad mums ir jābūt uzmanīgiem par to, kā mēs organizējam norādes tāpēc mums nav pārtraukumu ķēdi. 

Mēs varam noteikt 10 līdzšinējo laukumā norādīt atpakaļ uz veco astes, un kopš '10 būs jauna aste kādā brīdī līdz brīdim, kad visi no šiem ķēdes ir savienotas, nekas gatavojas nākt pēc 10 jau tagad. Un tā 10 nākamais rādītājs norādīs uz null, un tad pēc mēs to darām, kad mēs esam savienots 10 atpakaļ, lai ķēdes, mēs varam veikt veco galvu, vai, atvainojiet mani, veco asti rindā. Vecais rindas beigās, 13, un padarīt to norāda uz 10. Un tagad, šajā brīdī, mēs esam enqueued numuru 10 šajā rindā. Viss, kas mums jādara, tagad ir tikai pārvietot asti norādīt līdz 10, nevis 13. 

Dequeuing faktiski ļoti līdzīgs popping no skursteņiem, kas ir īstenota kā saistīts saraksts ja esat redzējuši skursteņi video. Viss, kas mums jādara, ir sākt pie sākas, atrast otro elementu, atbrīvotu pirmo elementu, un pēc tam pārvietot galvu lai norādītu uz otrā elementa. Droši vien labāk vizualizēt tikai, lai būtu papildu skaidrs par to. Tātad, šeit ir mūsu rinda vēlreiz. 12 ir senākais elements mūsu rindā, galvas. 10 ir jaunākais elements mūsu rindā, mūsu asti. 

Un tad, kad mēs gribam lai dequeue elementu, mēs vēlamies, lai noņemtu vecākā elementu. Tātad, ko mēs darām? Nu mēs noteikti šķērsošana rādītāju kas sākas pie galvas, un mēs pārvietot tā, lai tā norāda uz otrā elementa Tas queue-- kaut ko pasakot trav vienāds Trav arrow blakus, piemēram, varētu pārcelties trav tur, lai norādītu uz 15, kas, pēc tam, kad mēs dequeue 12, vai pēc mēs noņemam 12, būs kļūt par tolaik vecākā elements. 

Tagad mēs esam ieguvuši turēt uz pirmo elements, izmantojot rādītāja galvas un otrais elements izmantojot rādītāja trav. Mēs tagad var bez galvas, un tad mēs varam teikt nekas nāk pirms 15 vairs. Tātad, mēs varam mainīt 15 iepriekšējo rādītāju norādīt uz null, un mēs vienkārši pārvietot galvu. Un tur mēs ejam. Tagad mums ir veiksmīgi dequeued 12, un tagad mēs ir cita rindā 4 elementiem. Tas ir diezgan daudz viss tur ir rindas, gan masīvs bāzes un saistītas sarakstu pamatā. Es esmu Doug Lloyd. Tas ir CS 50.