1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Tātad, ja jūs esat
noskatījos video par steku,

3
00:00:07,370 --> 00:00:09,870
Tas ir iespējams, gatavojas justies
tāpat mazliet deja vu.

4
00:00:09,870 --> 00:00:13,850
Tas būs ļoti līdzīgu koncepciju,
tikai ar nelielu vērpjot par to.

5
00:00:13,850 --> 00:00:15,530
Mēs ejam tagad runāt par rindām.

6
00:00:15,530 --> 00:00:19,350
Tātad rinda, līdzīgs kaudze,
ir cita veida datu struktūras

7
00:00:19,350 --> 00:00:22,412
ka mēs varam izmantot, lai saglabātu
dati organizētā veidā.

8
00:00:22,412 --> 00:00:24,120
Līdzīgi kaudze,
to var īstenot

9
00:00:24,120 --> 00:00:27,000
kā masīvu vai saistītajā sarakstā.

10
00:00:27,000 --> 00:00:30,320
Atšķirībā no skursteņiem, noteikumi
ka mēs izmantojam, lai noteiktu

11
00:00:30,320 --> 00:00:34,210
kad lietas iegūt pievienot un izņemt no
rinda ir mazliet atšķirīgs.

12
00:00:34,210 --> 00:00:36,590
>> Atšķirībā kaudze, kas
ir LIFO struktūra,

13
00:00:36,590 --> 00:00:45,610
pēdējais iekšā, pirmais ārā, rinda ir FIFO
struktūra, FIFO, pirmais iekšā, pirmais ārā.

14
00:00:45,610 --> 00:00:49,320
Tagad rindas, jūs, iespējams,
ir analoģija ar rindām.

15
00:00:49,320 --> 00:00:52,820
Ja esat kādreiz bijuši rindā pie
atrakciju parks vai bankā,

16
00:00:52,820 --> 00:00:56,430
tur ir sava veida taisnīguma
īstenošanas struktūru.

17
00:00:56,430 --> 00:00:59,160
Pirmā persona rindā pie
banka ir pirmā persona

18
00:00:59,160 --> 00:01:00,760
kas izpaužas runāt ar stāstītājs.

19
00:01:00,760 --> 00:01:03,522
>> Tas būtu sava veida sacīkstes
uz leju, ja vienīgais veids

20
00:01:03,522 --> 00:01:06,730
jums runāt ar stāstītājs tajā
banka bija pēdējais cilvēks rindā.

21
00:01:06,730 --> 00:01:09,146
Ikviens vienmēr vēlēties
ir pēdējā persona līniju,

22
00:01:09,146 --> 00:01:12,580
un persona, kas bija tur pirmais
kurš gaidīja brīdi,

23
00:01:12,580 --> 00:01:14,715
varētu būt tur stundām,
un stundas, un stundas

24
00:01:14,715 --> 00:01:17,590
pirms tie ir iespēja reāli
izņemt naudu bankā.

25
00:01:17,590 --> 00:01:22,510
Un tā rindas ir sava veida
taisnīgums īstenošanas struktūru.

26
00:01:22,510 --> 00:01:25,780
Bet tas nebūt nenozīmē,
ka skursteņi ir slikti, tikai

27
00:01:25,780 --> 00:01:28,160
ka rindas ir vēl viens veids, kā to darīt.

28
00:01:28,160 --> 00:01:32,420
Tātad atkal rinda ir pirmais iekšā, pirmais
ārā, salīdzinot kaudze, kas pēdējo reizi,

29
00:01:32,420 --> 00:01:34,440
pirmais ārā.

30
00:01:34,440 --> 00:01:36,190
Līdzīgi kaudze,
mums ir divas operācijas

31
00:01:36,190 --> 00:01:38,470
ka mēs varam veikt uz rindas.

32
00:01:38,470 --> 00:01:43,910
Šie vārdi ir Enqueue, kas ir pievienot
jauns elements līdz beigām rindā,

33
00:01:43,910 --> 00:01:47,330
un dequeue, kas ir
noņemt vecākā

34
00:01:47,330 --> 00:01:49,670
elements no priekšā rindā.

35
00:01:49,670 --> 00:01:53,600
Tātad mēs ejam, lai pievienotu elementus
uz rindas beigās,

36
00:01:53,600 --> 00:01:57,220
un mēs ejam, lai novērstu elementu
no priekšpuses rindā.

37
00:01:57,220 --> 00:02:00,790
Atkal, ar steku, mēs pievienojot
elementi uz augšējās

38
00:02:00,790 --> 00:02:03,380
un likvidējot elementus
no augšas kaudze.

39
00:02:03,380 --> 00:02:07,570
Tātad ar Enqueue, tā pievienojot
beigām, noņemot no priekšpuses.

40
00:02:07,570 --> 00:02:10,639
Tātad vecākā lieta tur
vienmēr nākamā lieta

41
00:02:10,639 --> 00:02:13,620
iznākt, ja mēs cenšamies
un dequeue kaut ko.

42
00:02:13,620 --> 00:02:18,330
>> Tātad vēlreiz, ar rindām, mēs varam
masīvs bāzes implementāciju

43
00:02:18,330 --> 00:02:20,110
un saistīta sarakstu balstītu implementāciju.

44
00:02:20,110 --> 00:02:24,620
Mēs sāksim no jauna ar
masīvs bāzes implementāciju.

45
00:02:24,620 --> 00:02:27,070
Struktūra definīcija
izskatās diezgan līdzīgi.

46
00:02:27,070 --> 00:02:30,720
Mums ir vēl viena masīva
tur datu tipa vērtību,

47
00:02:30,720 --> 00:02:32,690
tāpēc tas var būt patvaļīgu datu tipu.

48
00:02:32,690 --> 00:02:35,570
Mēs atkal gatavojas izmantot
skaitļu šajā piemērā.

49
00:02:35,570 --> 00:02:39,830
>> Un tāpat kā ar mūsu
masīvs bāzes kaudze īstenošana,

50
00:02:39,830 --> 00:02:42,340
tāpēc, ka mēs esam, izmantojot
masīvs, mēs vienmēr

51
00:02:42,340 --> 00:02:46,850
ir, ka ierobežojums, kas C veida
no īsteno uz mums, kas esam mēs

52
00:02:46,850 --> 00:02:51,670
nav nekādu dinamiku mūsu
spēju augt un sarauties masīvs.

53
00:02:51,670 --> 00:02:55,710
Mums ir jāizlemj sākumā
kas ir maksimālais skaits, lietas

54
00:02:55,710 --> 00:02:59,300
ka mēs varam nodot šo
rinda, un šajā gadījumā,

55
00:02:59,300 --> 00:03:02,070
jauda varētu būt daži mārciņa
noteikts konstants mūsu kodu.

56
00:03:02,070 --> 00:03:05,430
Un no šī vajadzībām
video, jauda būs 10.

57
00:03:05,430 --> 00:03:07,690
>> Mums ir nepieciešams, lai sekotu
priekšējā rindā

58
00:03:07,690 --> 00:03:11,160
tāpēc mēs zinām, kurš no šiem elementiem
mēs vēlamies dequeue,

59
00:03:11,160 --> 00:03:15,070
un mums ir arī nepieciešams, lai sekotu
kaut else-- elementu skaitu

60
00:03:15,070 --> 00:03:16,690
ka mums ir mūsu rindā.

61
00:03:16,690 --> 00:03:19,360
Ievērojiet, mēs neesam sekotu
no rindas beigās, tikko

62
00:03:19,360 --> 00:03:21,150
lielums rindā.

63
00:03:21,150 --> 00:03:24,310
Un iemesls, kas, cerams
kļūt mazliet skaidrāka brīdi.

64
00:03:24,310 --> 00:03:26,143
Kad mēs esam pabeiguši
šāda definīcija,

65
00:03:26,143 --> 00:03:29,080
mums ir jauns datu tipu
sauc rinda, kurā mēs varam tagad

66
00:03:29,080 --> 00:03:30,630
deklarēt mainīgos šī datu tipu.

67
00:03:30,630 --> 00:03:35,350
Un nedaudz maldinoši, es esmu nolēmis
lai izsauktu šo rindas q, vēstule

68
00:03:35,350 --> 00:03:38,090
q vietā Datu tipa q.

69
00:03:38,090 --> 00:03:39,600
>> Tātad, šeit ir mūsu rinda.

70
00:03:39,600 --> 00:03:40,700
Tā ir struktūra.

71
00:03:40,700 --> 00:03:45,730
Tā sastāv no trim locekļiem vai trīs
lauki, masīvs lieluma jaudu.

72
00:03:45,730 --> 00:03:47,340
Šajā gadījumā, jauda ir 10.

73
00:03:47,340 --> 00:03:49,580
Un tas ir masīvs
gatavojas rīkot veseli skaitļi.

74
00:03:49,580 --> 00:03:55,240
Zaļā krāsā ir priekšā mūsu rindā, tad
blakus elements, kas izņemta, un sarkanā krāsā

75
00:03:55,240 --> 00:03:58,610
būs izmēru no rindas,
cik elementi ir šobrīd

76
00:03:58,610 --> 00:04:01,190
esošo rindā.

77
00:04:01,190 --> 00:04:05,300
Tātad, ja mēs sakām q.front Vienāds
0, un q.size izmērs ir vienāds 0--

78
00:04:05,300 --> 00:04:07,120
mēs esam liekot 0s šajās jomās.

79
00:04:07,120 --> 00:04:11,070
Un šajā brīdī, mēs esam diezgan daudz
gatavs sākt strādāt ar mūsu rindā.

80
00:04:11,070 --> 00:04:14,140
>> Tātad pirmais operācija mēs varam
veikt ir ierindod kaut,

81
00:04:14,140 --> 00:04:16,860
pievienot jaunu elementu
beigām, rindā.

82
00:04:16,860 --> 00:04:19,089
Nu ko mums vajag, lai
darīt vispārējā gadījumā?

83
00:04:19,089 --> 00:04:23,690
Nu šī funkcija ierindod vajadzībām
pieņemt rādītāju uz mūsu rindā.

84
00:04:23,690 --> 00:04:26,370
Atkal, ja mēs būtu deklarēta
Mūsu rinda pasaulē,

85
00:04:26,370 --> 00:04:29,490
mēs nebūtu tas jādara
obligāti, bet vispār, mēs

86
00:04:29,490 --> 00:04:32,330
nepieciešams pieņemt norādes
to datu struktūras

87
00:04:32,330 --> 00:04:35,040
kā šis, jo pretējā gadījumā,
mēs esam garām value-- mēs esam

88
00:04:35,040 --> 00:04:38,140
iet uz kopijas rindā,
un tāpēc mēs esam ne faktiski nemainot

89
00:04:38,140 --> 00:04:41,050
rinda, ka mēs plānojam mainīt.

90
00:04:41,050 --> 00:04:44,860
>> Otra lieta, tas ir jādara, ir pieņemt
datu elements no attiecīgā tipa.

91
00:04:44,860 --> 00:04:46,818
Atkal, šajā gadījumā, tas ir
būs veseli skaitļi,

92
00:04:46,818 --> 00:04:49,330
bet jūs varētu patvaļīgi
atzīt datu tipu kā vērtību

93
00:04:49,330 --> 00:04:51,160
un izmantot to vispār.

94
00:04:51,160 --> 00:04:56,030
Tas ir elements, mēs vēlamies ierindod,
mēs vēlamies pievienot rindas beigās.

95
00:04:56,030 --> 00:04:58,573
Tad mēs tiešām gribam
izvietot ka dati rindā.

96
00:04:58,573 --> 00:05:01,490
Šajā gadījumā, ievietojot to
pareizs izvietojums mūsu masīvs,

97
00:05:01,490 --> 00:05:05,040
un tad mēs gribam mainīt izmēru
rindā, cik daudzi elementi Mums

98
00:05:05,040 --> 00:05:07,050
pašlaik ir.

99
00:05:07,050 --> 00:05:07,990
>> Tātad, pieņemsim sāktu.

100
00:05:07,990 --> 00:05:10,890
Te ir, atkal, ka vispārējā
forma funkcija deklarācija

101
00:05:10,890 --> 00:05:13,980
par to, ko Enqueue varētu izskatīties.

102
00:05:13,980 --> 00:05:14,910
Un šeit mēs iet.

103
00:05:14,910 --> 00:05:18,335
Pieņemsim ierindod skaitu
28. rindā.

104
00:05:18,335 --> 00:05:19,460
Tātad, ko mēs gatavojamies darīt?

105
00:05:19,460 --> 00:05:23,390
Nu, priekšā mūsu rindā ir
pie 0, un lielumu mūsu rindas

106
00:05:23,390 --> 00:05:29,680
ir 0, un tāpēc mēs, iespējams, vēlas likt
skaits 28 masīva elementu skaits

107
00:05:29,680 --> 00:05:31,124
0, labi?

108
00:05:31,124 --> 00:05:32,540
Tāpēc mēs esam tagad novietoti ka tur.

109
00:05:32,540 --> 00:05:34,820
Tāpēc tagad, ko mums vajag, lai mainītu?

110
00:05:34,820 --> 00:05:37,090
Mēs nevēlamies, lai mainītu
priekšējā rindā,

111
00:05:37,090 --> 00:05:40,850
jo mēs vēlamies zināt, kāda elementa
mums var būt nepieciešams dequeue vēlāk.

112
00:05:40,850 --> 00:05:44,020
Tātad iemesls mums ir priekšā tur
ir sava veida indikators par to, kas ir

113
00:05:44,020 --> 00:05:46,439
vecākā lieta masīvā.

114
00:05:46,439 --> 00:05:49,730
Nu vecākā lieta array-- in
Fakts, vienīgā lieta masīva tiesības

115
00:05:49,730 --> 00:05:53,540
now-- ir 28, kas ir
pie masīva atrašanās vietā 0.

116
00:05:53,540 --> 00:05:56,160
Tāpēc mēs nevēlamies
mainīt šo zaļo numuru,

117
00:05:56,160 --> 00:05:57,910
jo tas ir vecākā elements.

118
00:05:57,910 --> 00:06:00,510
Drīzāk, mēs gribam mainīt izmēru.

119
00:06:00,510 --> 00:06:04,110
Tātad šajā gadījumā, mēs
pieauguma lielumu līdz 1.

120
00:06:04,110 --> 00:06:08,430
>> Tagad vispārēja veida ideju, kur
Nākamais elements ir gatavojas iet rindā

121
00:06:08,430 --> 00:06:12,310
ir pievienot šos divus skaitļus
kopā, priekšā un izmērs,

122
00:06:12,310 --> 00:06:16,390
un kas būs, ja pateiks, nākamais
elements rindā gatavojas iet.

123
00:06:16,390 --> 00:06:18,130
Tāpēc tagad pieņemsim ierindod citu numuru.

124
00:06:18,130 --> 00:06:20,250
Pieņemsim ierindod 33.

125
00:06:20,250 --> 00:06:24,480
Tātad 33 gatavojas iedziļināties
masīvs location 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Tātad šajā gadījumā, tas notiek
iedziļināties masīva vietā 1,

127
00:06:26,840 --> 00:06:29,500
un tagad lielums mūsu rindā ir 2.

128
00:06:29,500 --> 00:06:31,840
>> Atgādināsim, ka mēs esam nemainot
priekšējo mūsu rindā,

129
00:06:31,840 --> 00:06:34,730
jo 28 joprojām ir
vecākais elements, un mēs

130
00:06:34,730 --> 00:06:38,220
gribu kuri paredzēti, kad mēs beidzot nokļūt
līdz dequeuing, noņemot elementus

131
00:06:38,220 --> 00:06:43,300
no šīs rindas, mēs vēlamies zināt
kur vecākā elements ir.

132
00:06:43,300 --> 00:06:48,620
Un tāpēc mums vienmēr ir nepieciešams saglabāt
daži rādītājs, kur tas ir.

133
00:06:48,620 --> 00:06:50,410
Tātad, tas ir tas, ko 0 ir tur.

134
00:06:50,410 --> 00:06:52,910
Tas ir tas, ko priekšā ir tur.

135
00:06:52,910 --> 00:06:55,022
>> Let 's Enqueue vēl viens elements, 19.

136
00:06:55,022 --> 00:06:56,980
Es esmu pārliecināts, ka jūs varat uzminēt
kur 19 gatavojas iet.

137
00:06:56,980 --> 00:06:59,860
Tas būs iedziļināties
masīvs vietas numurs 2.

138
00:06:59,860 --> 00:07:01,570
Tas ir 0 plus 2.

139
00:07:01,570 --> 00:07:03,199
Un tagad lielums mūsu rindā ir 3.

140
00:07:03,199 --> 00:07:04,240
Mums ir 3 elementi tajā.

141
00:07:04,240 --> 00:07:08,490
Tātad, ja mēs, un mēs nebrauksim
tieši tagad, ierindod citu elementu,

142
00:07:08,490 --> 00:07:11,370
tas varētu iedziļināties masīva vietā
numurs 3, un lielumu mūsu rindā

143
00:07:11,370 --> 00:07:13,160
būtu 4.

144
00:07:13,160 --> 00:07:15,279
Tāpēc mēs esam enqueued vairāki elementi tagad.

145
00:07:15,279 --> 00:07:16,570
Tagad sāksim, lai tos novērstu.

146
00:07:16,570 --> 00:07:19,450
Pieņemsim dequeue tos no rindas.

147
00:07:19,450 --> 00:07:23,340
>> Tik līdzīgs pop, kas ir sava veida
no analogās uz to, lai skursteņi,

148
00:07:23,340 --> 00:07:26,180
dequeue nepieciešams pieņemt
rādītāju uz queue-- atkal,

149
00:07:26,180 --> 00:07:28,140
ja vien tas ir visā pasaulē pasludināts.

150
00:07:28,140 --> 00:07:31,610
Tagad mēs gribam mainīt atrašanās vietu
no priekšpuses rindā.

151
00:07:31,610 --> 00:07:35,050
Tas ir, ja tā veida runa
spēlē, ka priekšā mainīgs,

152
00:07:35,050 --> 00:07:37,310
jo, kad mēs noņemam
elements, mēs gribam

153
00:07:37,310 --> 00:07:40,720
lai to pārvietotu uz nākamo vecāko elementa.

154
00:07:40,720 --> 00:07:44,180
>> Tad mēs gribam, lai samazinātu
lielums rindā,

155
00:07:44,180 --> 00:07:47,130
un tad mēs gribam atgriezties vērtību
kas tika izslēgta no rindas.

156
00:07:47,130 --> 00:07:48,921
Atgādināsim, ka mēs nevēlamies, lai tikai atbrīvoties.

157
00:07:48,921 --> 00:07:51,170
Mēs, iespējams, ir ieguves
tas no queue-- mums esi

158
00:07:51,170 --> 00:07:54,170
dequeuing to, jo mēs rūpējamies par to.

159
00:07:54,170 --> 00:08:01,080
Tāpēc mēs vēlamies, lai šī funkcija, lai atgrieztos
datu elements tipa vērtības.

160
00:08:01,080 --> 00:08:04,360
Atkal, šajā gadījumā, vērtība ir vesels skaitlis.

161
00:08:04,360 --> 00:08:05,670
>> Tāpēc tagad pieņemsim dequeue kaut ko.

162
00:08:05,670 --> 00:08:09,310
Pieņemsim izņemt elements no rindas.

163
00:08:09,310 --> 00:08:15,970
Ja mēs sakām, int x vienāds & q, Ampersand q--
atkal tas ir rādītājs, lai šo q datiem

164
00:08:15,970 --> 00:08:20,177
structure-- ko elements
tiks dequeued?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
Šajā gadījumā, jo tas ir pirmais
iekšā, pirmais ārā datu struktūra, FIFO,

167
00:08:29,480 --> 00:08:33,690
pirmā lieta, mēs nodots šis
rinda bija 28, un tā šajā gadījumā,

168
00:08:33,690 --> 00:08:37,245
mēs spēsim pieņemt 28 no
rinda, ne 19, kas ir tas, ko

169
00:08:37,245 --> 00:08:38,870
mēs būtu darījuši, ja tas bija kaudze.

170
00:08:38,870 --> 00:08:42,220
Mēs ejam, lai 28 no rindā.

171
00:08:42,220 --> 00:08:44,960
>> Līdzīgi tam, ko mēs darījām ar
kaudze, mēs esam faktiski nav

172
00:08:44,960 --> 00:08:47,345
gatavojas dzēst 28
no rindas pati,

173
00:08:47,345 --> 00:08:49,470
mēs esam tikai gatavojas veida
no izlikties tā tur nav.

174
00:08:49,470 --> 00:08:51,678
Tātad tas notiek tur palikt
atmiņā, bet mēs esam tikai

175
00:08:51,678 --> 00:08:57,820
gatavojas veida ignorēt to, pārvietojot
Pārējie divi lauki mūsu q datu

176
00:08:57,820 --> 00:08:58,830
struktūra.

177
00:08:58,830 --> 00:09:00,230
Mēs ejam, lai mainītu priekšā.

178
00:09:00,230 --> 00:09:04,290
Q.front tagad gatavojas
ir 1, jo tas ir tagad

179
00:09:04,290 --> 00:09:07,740
vecākā elements mums ir mūsu
rinda, jo mēs esam jau noņemts 28,

180
00:09:07,740 --> 00:09:10,460
kas bija bijušais vecākais elements.

181
00:09:10,460 --> 00:09:13,540
>> Un tagad, mēs gribam mainīt
lielums rindā

182
00:09:13,540 --> 00:09:15,780
līdz trim diviem elementiem, nevis.

183
00:09:15,780 --> 00:09:20,450
Tagad atceros, agrāk es teicu, kad mēs
vēlaties pievienot elementus rindā,

184
00:09:20,450 --> 00:09:26,000
mēs ieliekam to masīva vietā
kas ir no priekšpuses un lielumu summa.

185
00:09:26,000 --> 00:09:29,050
Tātad šajā gadījumā, mēs joprojām liekot
tā, nākamais elements rindā,

186
00:09:29,050 --> 00:09:33,360
uz masīvu vietā 3, un
mēs redzam, ka sekundē.

187
00:09:33,360 --> 00:09:35,730
>> Tāpēc mēs esam tagad dequeued mūsu
Pirmais elements no rindas.

188
00:09:35,730 --> 00:09:36,480
Darīsim to vēlreiz.

189
00:09:36,480 --> 00:09:38,696
Pieņemsim noņemt cits
elements no rindas.

190
00:09:38,696 --> 00:09:42,400
Gadījumā, pašreizējā vecākā
elements ir masīvs vieta 1.

191
00:09:42,400 --> 00:09:44,220
Tas ko q.front stāsta mums.

192
00:09:44,220 --> 00:09:46,980
Ka green box stāsta mums, ka
tas ir vecākā elements.

193
00:09:46,980 --> 00:09:49,310
Un tā, x kļūs 33.

194
00:09:49,310 --> 00:09:52,130
Mēs tikko veida aizmirst
ka 33 pastāv masīva,

195
00:09:52,130 --> 00:09:55,100
un mēs sakām, ka tagad, tad
Jaunais vecākā elements rindā

196
00:09:55,100 --> 00:09:58,900
ir masīvs vietā 2, un lielumu
no rindā, skaits elementu

197
00:09:58,900 --> 00:10:02,152
mums ir rindā, ir 1.

198
00:10:02,152 --> 00:10:05,110
Tagad pieņemsim ierindod kaut ko, un es
kārtot sniedza šo prom otrs atpakaļ,

199
00:10:05,110 --> 00:10:10,340
bet, ja mēs gribam, lai 40 Into
rinda, kur ir 40 gatavojas iet?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Nu mēs esam liekot to
in q.front plus rindas izmēru,

202
00:10:17,730 --> 00:10:20,850
un tāpēc tas ir jēga, lai
faktiski likt 40 šeit.

203
00:10:20,850 --> 00:10:22,840
Tagad ievēroju, ka pie
Kādā brīdī, mēs ejam

204
00:10:22,840 --> 00:10:27,980
nokļūt līdz beigām
Mūsu masīvs iekšpusē q,

205
00:10:27,980 --> 00:10:32,010
bet izbalējis no 28. un 33--
viņi patiesībā, tehniski

206
00:10:32,010 --> 00:10:33,300
atklātas vietas, vai ne?

207
00:10:33,300 --> 00:10:36,040
Un tā, mēs varam eventually--
ka noteikums, pievienojot

208
00:10:36,040 --> 00:10:40,390
šie divi together-- mēs varam beidzot
nepieciešams mod ar izmēru jaudu

209
00:10:40,390 --> 00:10:41,410
lai mēs varētu aptīt ap.

210
00:10:41,410 --> 00:10:43,620
>> Tātad, ja mēs uz elementu
numuru 10, ja mēs esam

211
00:10:43,620 --> 00:10:48,790
aizstājot to elementu skaitu 10, mēs gribētu
faktiski nodot to masīva atrašanās vietā 0.

212
00:10:48,790 --> 00:10:50,997
Un, ja mēs gatavojamies
masīvs location-- atvainojiet,

213
00:10:50,997 --> 00:10:53,080
ja mēs pievienot tos kopā,
un mēs saņēmām uz numuru

214
00:10:53,080 --> 00:10:56,330
11 būtu, ja mums būtu likts
tas, kas neeksistē šajā array--

215
00:10:56,330 --> 00:10:58,200
tas būtu iet ārpus robežām.

216
00:10:58,200 --> 00:11:03,367
Mēs varētu mod ar 10 un nodot
tas ir masīva vietā 1.

217
00:11:03,367 --> 00:11:04,450
Tātad tas, kā rindas strādāt.

218
00:11:04,450 --> 00:11:08,540
Viņi vienmēr gatavojas aiziet no kreisās
uz labo pusi, un, iespējams, wrap ap.

219
00:11:08,540 --> 00:11:11,280
Un jūs zināt, ka viņi
pilna ja izmēra, ka sarkanā lodziņa,

220
00:11:11,280 --> 00:11:13,710
kļūst vienāds ar jaudu.

221
00:11:13,710 --> 00:11:16,720
Un tā, kad mēs esam pievienojuši 40 uz
rinda, arī to, kas mums jādara?

222
00:11:16,720 --> 00:11:19,890
Nu, vecākā elements
rindā ir vēl 19,

223
00:11:19,890 --> 00:11:21,990
tāpēc mēs nevēlamies, lai mainītu
priekšējā rindā,

224
00:11:21,990 --> 00:11:23,820
bet tagad mums ir divi
elementi rindā,

225
00:11:23,820 --> 00:11:28,710
un tāpēc mēs vēlamies palielināt
Mūsu izmērs no 1 līdz 2.

226
00:11:28,710 --> 00:11:31,820
>> Tas ir diezgan daudz to ar
strādājot ar masīvu bāzes rindas,

227
00:11:31,820 --> 00:11:33,630
un līdzīgi kaudze,
ir arī veids

228
00:11:33,630 --> 00:11:36,450
īstenot rindā kā saistīts sarakstā.

229
00:11:36,450 --> 00:11:40,150
Tagad, ja šī datu struktūra tips
izskatās pazīstams ar jums, tā ir.

230
00:11:40,150 --> 00:11:43,780
Tas nav atsevišķi saistīts saraksts,
tas ir divtik saistīts saraksts.

231
00:11:43,780 --> 00:11:46,790
Un tagad, kā malā, tas ir
reāli iespējams īstenot

232
00:11:46,790 --> 00:11:50,160
rinda kā atsevišķi saistīta sarakstā, bet
Es domāju, ka attiecībā uz vizualizāciju,

233
00:11:50,160 --> 00:11:53,350
tas tiešām var palīdzēt, lai skatītos
tas kā divkārt saistīta sarakstā.

234
00:11:53,350 --> 00:11:56,850
Bet tas noteikti ir iespējams
darīt kā atsevišķi saistīta sarakstā.

235
00:11:56,850 --> 00:12:00,110
>> Tātad, pieņemsim ir apskatīt
ko tas varētu izskatīties.

236
00:12:00,110 --> 00:12:02,750
Ja mēs gribam, lai enquue--
Tāpēc tagad, atkal mēs esam

237
00:12:02,750 --> 00:12:05,360
pārejot uz saistītā sarakstā
orientētu modeli šeit.

238
00:12:05,360 --> 00:12:08,420
Ja mēs vēlamies, lai ierindod, mēs gribam
pievienot jaunu elementu, labi

239
00:12:08,420 --> 00:12:09,730
Ko mums darīt?

240
00:12:09,730 --> 00:12:12,770
Nu, pirmkārt, tāpēc, ka
mēs pievienojot līdz beigām

241
00:12:12,770 --> 00:12:15,520
un noņemot no
sākuma, mēs, iespējams,

242
00:12:15,520 --> 00:12:20,050
vēlas saglabāt norādes gan
galva un aste saistītā saraksta?

243
00:12:20,050 --> 00:12:22,660
Aste ir cits apzīmējums
beigām, kas saistīts saraksta,

244
00:12:22,660 --> 00:12:24,496
pēdējais elements saistīts sarakstā.

245
00:12:24,496 --> 00:12:26,620
Un šie būs iespējams,
atkal būt izdevīga mums

246
00:12:26,620 --> 00:12:28,477
ja tie ir globālie mainīgie.

247
00:12:28,477 --> 00:12:31,060
Bet tagad, ja mēs gribam, lai pievienotu jaunu
elements, ko mums ir jādara?

248
00:12:31,060 --> 00:12:35,262
Ko mēs vienkārši [? malak?] vai dinamiski
piešķirt mūsu jauno mezglā sev.

249
00:12:35,262 --> 00:12:38,220
Un tad, tāpat kā tad, kad mēs pievienot kādu
elements divkārt saistīta saraksta mēs,

250
00:12:38,220 --> 00:12:40,410
vienkārši ir, lai sakārtotu of--
šie pēdējie trīs soļi šeit

251
00:12:40,410 --> 00:12:43,330
ir tikai visu par pārvietojot
norādes, kas pareizi

252
00:12:43,330 --> 00:12:46,710
tā, ka šis elements tiek pievienots
ķēdi, nesalaužot ķēdi

253
00:12:46,710 --> 00:12:49,580
vai veikt kaut kādas kļūdas veida
vai kam ir kāda negadījuma veida

254
00:12:49,580 --> 00:12:54,505
notikt kuru mēs nejauši
bāreņu daži no mūsu rindā elementus.

255
00:12:54,505 --> 00:12:55,880
Lūk, ko tas varētu izskatīties.

256
00:12:55,880 --> 00:13:00,980
Mēs vēlamies, lai pievienotu šo elementu
10 līdz beigām šo rindā.

257
00:13:00,980 --> 00:13:03,380
Tātad vecākā elements šeit
pārstāv galvu.

258
00:13:03,380 --> 00:13:06,800
Tas ir pirmais, ko mēs ieliekam
šajā hipotētiskajā rindā šeit.

259
00:13:06,800 --> 00:13:10,430
Un astes, 13, ir visvairāk
Nesen pievienotās elements.

260
00:13:10,430 --> 00:13:17,030
Un tāpēc, ja mēs gribam, lai ierindod 10 uz
šī rinda, mēs vēlamies, lai tā pēc 13.

261
00:13:17,030 --> 00:13:19,860
Un tā mēs ejam, lai dinamiski
piešķirt telpas uz jaunu mezglu

262
00:13:19,860 --> 00:13:23,280
un pārbaudīt null, lai pārliecinātos,
mums nav atmiņas mazspēja.

263
00:13:23,280 --> 00:13:27,040
Tad mēs ejam
izvietot 10 minētajā mezglā,

264
00:13:27,040 --> 00:13:30,030
un tagad mums ir jābūt uzmanīgiem
par to, kā mēs organizējam norādes

265
00:13:30,030 --> 00:13:32,180
tāpēc mums nav pārtraukumu ķēdi.

266
00:13:32,180 --> 00:13:38,910
>> Mēs varam noteikt 10 līdzšinējo laukumā
norādīt atpakaļ uz veco astes,

267
00:13:38,910 --> 00:13:41,620
un kopš '10 būs
jauna aste kādā brīdī

268
00:13:41,620 --> 00:13:44,459
līdz brīdim, kad visi no šiem
ķēdes ir savienotas,

269
00:13:44,459 --> 00:13:46,250
nekas gatavojas nākt
pēc 10 jau tagad.

270
00:13:46,250 --> 00:13:49,880
Un tā 10 nākamais rādītājs
norādīs uz null,

271
00:13:49,880 --> 00:13:53,580
un tad pēc mēs to darām, kad mēs esam
savienots 10 atpakaļ, lai ķēdes,

272
00:13:53,580 --> 00:13:57,780
mēs varam veikt veco galvu, vai, atvainojiet
mani, veco asti rindā.

273
00:13:57,780 --> 00:14:02,980
Vecais rindas beigās,
13, un padarīt to norāda uz 10.

274
00:14:02,980 --> 00:14:08,220
Un tagad, šajā brīdī, mēs esam
enqueued numuru 10 šajā rindā.

275
00:14:08,220 --> 00:14:14,740
Viss, kas mums jādara, tagad ir tikai pārvietot
asti norādīt līdz 10, nevis 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing faktiski
ļoti līdzīgs popping

277
00:14:17,630 --> 00:14:21,710
no skursteņiem, kas ir
īstenota kā saistīts saraksts

278
00:14:21,710 --> 00:14:24,040
ja esat redzējuši skursteņi video.

279
00:14:24,040 --> 00:14:27,280
Viss, kas mums jādara, ir sākt pie
sākas, atrast otro elementu,

280
00:14:27,280 --> 00:14:30,480
atbrīvotu pirmo elementu,
un pēc tam pārvietot galvu

281
00:14:30,480 --> 00:14:32,930
lai norādītu uz otrā elementa.

282
00:14:32,930 --> 00:14:37,920
Droši vien labāk vizualizēt
tikai, lai būtu papildu skaidrs par to.

283
00:14:37,920 --> 00:14:39,230
Tātad, šeit ir mūsu rinda vēlreiz.

284
00:14:39,230 --> 00:14:42,600
12 ir senākais elements
mūsu rindā, galvas.

285
00:14:42,600 --> 00:14:46,210
10 ir jaunākais elements
mūsu rindā, mūsu asti.

286
00:14:46,210 --> 00:14:49,310
>> Un tad, kad mēs gribam
lai dequeue elementu,

287
00:14:49,310 --> 00:14:52,202
mēs vēlamies, lai noņemtu vecākā elementu.

288
00:14:52,202 --> 00:14:52,910
Tātad, ko mēs darām?

289
00:14:52,910 --> 00:14:55,243
Nu mēs noteikti šķērsošana rādītāju
kas sākas pie galvas,

290
00:14:55,243 --> 00:14:57,840
un mēs pārvietot tā, lai tā
norāda uz otrā elementa

291
00:14:57,840 --> 00:15:02,290
Tas queue-- kaut ko pasakot trav
vienāds Trav arrow blakus, piemēram,

292
00:15:02,290 --> 00:15:07,170
varētu pārcelties trav tur, lai norādītu uz
15, kas, pēc tam, kad mēs dequeue 12,

293
00:15:07,170 --> 00:15:13,030
vai pēc mēs noņemam 12, būs
kļūt par tolaik vecākā elements.

294
00:15:13,030 --> 00:15:16,360
>> Tagad mēs esam ieguvuši turēt uz pirmo
elements, izmantojot rādītāja galvas

295
00:15:16,360 --> 00:15:19,440
un otrais elements
izmantojot rādītāja trav.

296
00:15:19,440 --> 00:15:25,170
Mēs tagad var bez galvas, un tad mēs varam
teikt nekas nāk pirms 15 vairs.

297
00:15:25,170 --> 00:15:29,990
Tātad, mēs varam mainīt 15 iepriekšējo
rādītāju norādīt uz null,

298
00:15:29,990 --> 00:15:31,874
un mēs vienkārši pārvietot galvu.

299
00:15:31,874 --> 00:15:32,540
Un tur mēs ejam.

300
00:15:32,540 --> 00:15:35,840
Tagad mums ir veiksmīgi
dequeued 12, un tagad mēs

301
00:15:35,840 --> 00:15:39,180
ir cita rindā 4 elementiem.

302
00:15:39,180 --> 00:15:41,700
Tas ir diezgan daudz viss
tur ir rindas,

303
00:15:41,700 --> 00:15:45,810
gan masīvs bāzes un saistītas sarakstu pamatā.

304
00:15:45,810 --> 00:15:46,860
Es esmu Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Tas ir CS 50.

306
00:15:49,100 --> 00:15:50,763