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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Jadi jika anda telah
menonton video pada timbunan,

3
00:00:07,370 --> 00:00:09,870
ini mungkin akan berasa
seperti sedikit deja vu.

4
00:00:09,870 --> 00:00:13,850
Ia akan konsep yang hampir sama,
hanya dengan sentuhan sedikit di atasnya.

5
00:00:13,850 --> 00:00:15,530
Kami akan bercakap kini kira-kira beratur.

6
00:00:15,530 --> 00:00:19,350
Jadi barisan, sama dengan timbunan,
satu lagi jenis struktur data

7
00:00:19,350 --> 00:00:22,412
yang boleh kita gunakan untuk mengekalkan
data dengan cara yang teratur.

8
00:00:22,412 --> 00:00:24,120
Sama seperti timbunan,
ia boleh dilaksanakan

9
00:00:24,120 --> 00:00:27,000
sebagai pelbagai atau senarai berpaut.

10
00:00:27,000 --> 00:00:30,320
Tidak seperti timbunan, peraturan
yang kita gunakan untuk menentukan

11
00:00:30,320 --> 00:00:34,210
apabila perkara yang ditambah dan dikeluarkan daripada
barisan yang sedikit berbeza.

12
00:00:34,210 --> 00:00:36,590
>> Tidak seperti timbunan, yang
adalah struktur LIFO,

13
00:00:36,590 --> 00:00:45,610
bertahan dalam, dahulu, barisan adalah FIFO yang
struktur, FIFO, masuk dahulu, keluar dahulu.

14
00:00:45,610 --> 00:00:49,320
Sekarang beratur, anda mungkin
mempunyai analogi untuk beratur.

15
00:00:49,320 --> 00:00:52,820
Jika anda pernah berada dalam talian di
taman hiburan atau di bank,

16
00:00:52,820 --> 00:00:56,430
ada jenis keadilan yang
melaksanakan struktur.

17
00:00:56,430 --> 00:00:59,160
Orang pertama dalam talian di
bank adalah orang yang pertama

18
00:00:59,160 --> 00:01:00,760
siapa yang boleh bercakap dengan juruwang.

19
00:01:00,760 --> 00:01:03,522
>> Ia akan menjadi jenis perlumbaan
ke bawah jika satu-satunya cara

20
00:01:03,522 --> 00:01:06,730
anda mendapat untuk bercakap dengan juruwang di
bank adalah untuk menjadi orang yang terakhir dalam barisan.

21
00:01:06,730 --> 00:01:09,146
Semua orang akan sentiasa mahu
untuk menjadi orang yang terakhir di dalam talian,

22
00:01:09,146 --> 00:01:12,580
dan orang yang berada di sana pertama
yang telah menunggu untuk seketika,

23
00:01:12,580 --> 00:01:14,715
boleh berada di sana selama berjam-jam,
dan jam, dan jam

24
00:01:14,715 --> 00:01:17,590
sebelum mereka mempunyai peluang untuk benar-benar
mengeluarkan apa-apa wang di bank.

25
00:01:17,590 --> 00:01:22,510
Dan supaya beratur adalah jenis yang
keadilan melaksanakan struktur.

26
00:01:22,510 --> 00:01:25,780
Tetapi itu tidak bermakna
yang susunan adalah satu perkara yang buruk, hanya

27
00:01:25,780 --> 00:01:28,160
yang beratur adalah satu lagi cara untuk melakukannya.

28
00:01:28,160 --> 00:01:32,420
Jadi sekali lagi beratur adalah masuk dahulu,
keluar, berbanding timbunan yang bertahan dalam,

29
00:01:32,420 --> 00:01:34,440
pertama keluar.

30
00:01:34,440 --> 00:01:36,190
Sama seperti timbunan,
kita mempunyai dua operasi

31
00:01:36,190 --> 00:01:38,470
yang kita boleh melakukan pada beratur.

32
00:01:38,470 --> 00:01:43,910
Nama-nama yang enqueue, iaitu untuk menambah
elemen baru ke akhir barisan,

33
00:01:43,910 --> 00:01:47,330
dan dequeue, yang
untuk membuang tertua

34
00:01:47,330 --> 00:01:49,670
unsur dari depan barisan.

35
00:01:49,670 --> 00:01:53,600
Jadi, kita akan menambah elemen
ke akhir barisan,

36
00:01:53,600 --> 00:01:57,220
dan kita akan membuang unsur-unsur
dari bahagian depan barisan.

37
00:01:57,220 --> 00:02:00,790
Sekali lagi, dengan timbunan, kita telah menambah
unsur-unsur untuk bahagian atas timbunan

38
00:02:00,790 --> 00:02:03,380
dan membuang unsur-unsur
dari bahagian atas timbunan.

39
00:02:03,380 --> 00:02:07,570
Jadi dengan enqueue, ia menambah kepada
Akhirnya, mengeluarkan dari hadapan.

40
00:02:07,570 --> 00:02:10,639
Jadi perkara yang paling tua di sana
sentiasa perkara yang akan datang

41
00:02:10,639 --> 00:02:13,620
untuk keluar jika kita cuba
dan dequeue sesuatu.

42
00:02:13,620 --> 00:02:18,330
>> Jadi sekali lagi, dengan beratur, kita boleh
pelaksanaan berdasarkan lokasi-

43
00:02:18,330 --> 00:02:20,110
dan dihubungkan-senarai pelaksanaan berasaskan.

44
00:02:20,110 --> 00:02:24,620
Kami akan bermula sekali lagi dengan
pelaksanaan berdasarkan lokasi.

45
00:02:24,620 --> 00:02:27,070
Takrif struktur
kelihatan agak sama.

46
00:02:27,070 --> 00:02:30,720
Kami mempunyai pelbagai lain
terdapat nilai jenis data,

47
00:02:30,720 --> 00:02:32,690
sehingga dapat memegang jenis data yang sewenang-wenangnya.

48
00:02:32,690 --> 00:02:35,570
Kami sekali lagi akan menggunakan
bilangan bulat dalam contoh ini.

49
00:02:35,570 --> 00:02:39,830
>> Dan seperti dengan kami
pelaksanaan timbunan berdasarkan lokasi-,

50
00:02:39,830 --> 00:02:42,340
kerana kita menggunakan
pelbagai, kita semestinya

51
00:02:42,340 --> 00:02:46,850
mempunyai batasan yang bahawa C jenis
daripada menguatkuasakan kepada kita, yang kita

52
00:02:46,850 --> 00:02:51,670
tidak mempunyai dinamisme dalam kita
keupayaan untuk berkembang dan mengecut array.

53
00:02:51,670 --> 00:02:55,710
Kita perlu membuat keputusan pada permulaan
apa yang bilangan maksimum perkara

54
00:02:55,710 --> 00:02:59,300
bahawa kita boleh dimasukkan ke dalam ini
barisan, dan dalam hal ini,

55
00:02:59,300 --> 00:03:02,070
kapasiti akan menjadi beberapa pound
ditakrifkan berterusan dalam kod kami.

56
00:03:02,070 --> 00:03:05,430
Dan bagi maksud ini
video, kapasiti akan menjadi 10.

57
00:03:05,430 --> 00:03:07,690
>> Kita perlu untuk mengesan
bahagian depan barisan

58
00:03:07,690 --> 00:03:11,160
supaya kita tahu mana elemen
kita mahu dequeue,

59
00:03:11,160 --> 00:03:15,070
dan kita juga perlu untuk mengesan
sesuatu else-- bilangan elemen

60
00:03:15,070 --> 00:03:16,690
yang kita ada dalam barisan kami.

61
00:03:16,690 --> 00:03:19,360
Perhatikan kami tidak mengesan
akhir barisan, hanya

62
00:03:19,360 --> 00:03:21,150
saiz barisan.

63
00:03:21,150 --> 00:03:24,310
Dan sebab yang akan diharapkan
menjadi sedikit lebih jelas dalam seketika.

64
00:03:24,310 --> 00:03:26,143
Setelah kami selesai
ini definisi jenis,

65
00:03:26,143 --> 00:03:29,080
kita mempunyai jenis data baru
dipanggil barisan, yang kita kini boleh

66
00:03:29,080 --> 00:03:30,630
mengisytiharkan pembolehubah yang jenis data.

67
00:03:30,630 --> 00:03:35,350
Dan agak mengelirukan, saya telah membuat keputusan
untuk memanggil barisan q ini, surat itu

68
00:03:35,350 --> 00:03:38,090
q bukannya jenis data q.

69
00:03:38,090 --> 00:03:39,600
>> Jadi di sini adalah giliran kami.

70
00:03:39,600 --> 00:03:40,700
Ia adalah struktur.

71
00:03:40,700 --> 00:03:45,730
Ia mengandungi tiga anggota atau tiga
telah disiapkan, pelbagai saiz KEUPAYAAN.

72
00:03:45,730 --> 00:03:47,340
Dalam kes ini, KEUPAYAAN adalah 10.

73
00:03:47,340 --> 00:03:49,580
Dan lokasi ini adalah
akan mengadakan integer.

74
00:03:49,580 --> 00:03:55,240
Dalam hijau hadapan barisan kita,
Elemen seterusnya yang akan dikeluarkan, dan merah

75
00:03:55,240 --> 00:03:58,610
akan menjadi saiz barisan,
berapa banyak elemen kini

76
00:03:58,610 --> 00:04:01,190
yang sedia ada dalam barisan.

77
00:04:01,190 --> 00:04:05,300
Jadi, jika kita katakan setaraf q.front
0, dan saiz q.size sama 0--

78
00:04:05,300 --> 00:04:07,120
kita meletakkan 0-an dalam bidang-bidang.

79
00:04:07,120 --> 00:04:11,070
Dan pada ketika ini, kami cukup banyak
bersedia untuk mula bekerja dengan barisan kami.

80
00:04:11,070 --> 00:04:14,140
>> Jadi operasi pertama kita boleh
melaksanakan adalah untuk enqueue sesuatu,

81
00:04:14,140 --> 00:04:16,860
untuk menambah elemen baru untuk
akhir barisan.

82
00:04:16,860 --> 00:04:19,089
Baik apa yang perlu kita
lakukan dalam kes umum?

83
00:04:19,089 --> 00:04:23,690
Well fungsi ini enqueue keperluan
untuk menerima penunjuk kepada barisan kami.

84
00:04:23,690 --> 00:04:26,370
Sekali lagi, jika kita telah mengisytiharkan
giliran kami di seluruh dunia,

85
00:04:26,370 --> 00:04:29,490
kita tidak perlu untuk melakukan ini
semestinya, tetapi secara umum, kita

86
00:04:29,490 --> 00:04:32,330
perlu menerima petunjuk
kepada struktur data

87
00:04:32,330 --> 00:04:35,040
seperti ini, kerana jika tidak,
kita lulus oleh value-- kami

88
00:04:35,040 --> 00:04:38,140
lulus dalam salinan barisan,
dan sebagainya kita tidak benar-benar berubah

89
00:04:38,140 --> 00:04:41,050
barisan yang kami berhasrat untuk berubah.

90
00:04:41,050 --> 00:04:44,860
>> Perkara lain yang diperlukan untuk lakukan ialah menerima
elemen data dari jenis yang sesuai.

91
00:04:44,860 --> 00:04:46,818
Sekali lagi, dalam kes ini, ia
akan menjadi bilangan bulat,

92
00:04:46,818 --> 00:04:49,330
tetapi anda boleh sewenang-wenangnya
mengisytiharkan jenis data sebagai nilai

93
00:04:49,330 --> 00:04:51,160
dan menggunakan ini amnya.

94
00:04:51,160 --> 00:04:56,030
Itulah elemen yang kita mahu enqueue,
kita mahu menambah hingga akhir barisan.

95
00:04:56,030 --> 00:04:58,573
Maka kita benar-benar ingin
meletakkan data yang dalam barisan.

96
00:04:58,573 --> 00:05:01,490
Dalam kes ini, penempatannya dalam
lokasi yang betul pelbagai kami,

97
00:05:01,490 --> 00:05:05,040
dan kemudian kita mahu menukar saiz
barisan, berapa banyak elemen kita

98
00:05:05,040 --> 00:05:07,050
kini mempunyai.

99
00:05:07,050 --> 00:05:07,990
>> Jadi mari kita mulakan.

100
00:05:07,990 --> 00:05:10,890
Di sini, sekali lagi, bahawa umum
pengisytiharan fungsi bentuk

101
00:05:10,890 --> 00:05:13,980
untuk apa enqueue mungkin kelihatan seperti.

102
00:05:13,980 --> 00:05:14,910
Dan di sini kita pergi.

103
00:05:14,910 --> 00:05:18,335
Mari kita enqueue jumlah
28 ke dalam barisan.

104
00:05:18,335 --> 00:05:19,460
Jadi apa yang kita akan lakukan?

105
00:05:19,460 --> 00:05:23,390
Nah, hadapan barisan kita
pada 0, dan saiz barisan kami

106
00:05:23,390 --> 00:05:29,680
adalah pada 0, dan dengan itu kita mungkin mahu meletakkan
angka 28 dalam bilangan elemen array

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

108
00:05:31,124 --> 00:05:32,540
Jadi, sekarang kita telah meletakkan bahawa di sana.

109
00:05:32,540 --> 00:05:34,820
Jadi sekarang apa yang kita perlu berubah?

110
00:05:34,820 --> 00:05:37,090
Kami tidak mahu berubah
bahagian depan barisan,

111
00:05:37,090 --> 00:05:40,850
kerana kita ingin tahu apa elemen
kita mungkin perlu dequeue kemudian.

112
00:05:40,850 --> 00:05:44,020
Jadi sebab kita ada depan terdapat
adalah jenis petunjuk apa yang

113
00:05:44,020 --> 00:05:46,439
Perkara yang tertua dalam array.

114
00:05:46,439 --> 00:05:49,730
Baik perkara yang tertua di array-- dalam
Malah, satu-satunya perkara dalam array yang betul

115
00:05:49,730 --> 00:05:53,540
sekarang-- adalah 28, yang merupakan
di pelbagai lokasi 0.

116
00:05:53,540 --> 00:05:56,160
Oleh itu, kita tidak mahu
menukar bilangan hijau,

117
00:05:56,160 --> 00:05:57,910
kerana itulah elemen yang paling lama.

118
00:05:57,910 --> 00:06:00,510
Sebaliknya, kita mahu menukar saiz.

119
00:06:00,510 --> 00:06:04,110
Jadi dalam kes ini, kita akan
kenaikan saiz 1.

120
00:06:04,110 --> 00:06:08,430
>> Sekarang semacam umum idea di mana yang
Elemen seterusnya akan pergi dalam barisan

121
00:06:08,430 --> 00:06:12,310
adalah untuk menambah kedua-dua nombor
bersama-sama, depan dan saiz,

122
00:06:12,310 --> 00:06:16,390
dan yang akan memberitahu anda di mana seterusnya
elemen dalam barisan akan pergi.

123
00:06:16,390 --> 00:06:18,130
Jadi sekarang mari kita enqueue nombor lain.

124
00:06:18,130 --> 00:06:20,250
Mari kita enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Jadi 33 akan pergi ke dalam
pelbagai lokasi 0 tambah 1.

126
00:06:24,480 --> 00:06:26,840
Jadi dalam kes ini, ia akan
untuk pergi ke lokasi mudah 1,

127
00:06:26,840 --> 00:06:29,500
dan sekarang saiz barisan kita 2.

128
00:06:29,500 --> 00:06:31,840
>> Sekali lagi, kita tidak akan menukar
hadapan barisan kita,

129
00:06:31,840 --> 00:06:34,730
kerana 28 masih
unsur tertua, dan kami

130
00:06:34,730 --> 00:06:38,220
mahu supaya- apabila kita akhirnya mendapatkan
untuk dequeuing, mengeluarkan unsur-unsur

131
00:06:38,220 --> 00:06:43,300
dari barisan ini, kami ingin tahu
mana elemen tertua.

132
00:06:43,300 --> 00:06:48,620
Dan dengan itu kita sentiasa perlu untuk mengekalkan
beberapa petunjuk mana yang.

133
00:06:48,620 --> 00:06:50,410
Jadi itulah yang 0 ada untuk.

134
00:06:50,410 --> 00:06:52,910
Itulah yang depan ada untuk.

135
00:06:52,910 --> 00:06:55,022
>> Mari kita di enqueue satu lagi elemen, 19.

136
00:06:55,022 --> 00:06:56,980
Saya pasti anda boleh meneka
di mana 19 akan pergi.

137
00:06:56,980 --> 00:06:59,860
Ia akan pergi ke
pelbagai nombor lokasi 2.

138
00:06:59,860 --> 00:07:01,570
Itulah 0 tambah 2.

139
00:07:01,570 --> 00:07:03,199
Dan kini saiz barisan kami ialah 3.

140
00:07:03,199 --> 00:07:04,240
Kami mempunyai 3 elemen di dalamnya.

141
00:07:04,240 --> 00:07:08,490
Jadi jika kita, dan kita tidak akan
untuk sekarang, enqueue unsur lain,

142
00:07:08,490 --> 00:07:11,370
ia akan pergi ke lokasi mudah
nombor 3, dan saiz barisan kami

143
00:07:11,370 --> 00:07:13,160
akan menjadi 4.

144
00:07:13,160 --> 00:07:15,279
Oleh itu, kita enqueued beberapa elemen sekarang.

145
00:07:15,279 --> 00:07:16,570
Sekarang mari kita mulakan untuk menghapuskan mereka.

146
00:07:16,570 --> 00:07:19,450
Mari kita dequeue mereka dari barisan.

147
00:07:19,450 --> 00:07:23,340
>> Jadi sama untuk pop, yang merupakan jenis
daripada analog ini untuk susunan,

148
00:07:23,340 --> 00:07:26,180
dequeue perlu menerima
penunjuk kepada queue-- sekali lagi,

149
00:07:26,180 --> 00:07:28,140
melainkan jika ia di peringkat global diisytiharkan.

150
00:07:28,140 --> 00:07:31,610
Sekarang kita ingin menukar lokasi
bahagian depan barisan.

151
00:07:31,610 --> 00:07:35,050
Ini adalah di mana ia semacam datang
ke dalam bermain, yang berubah-ubah hadapan,

152
00:07:35,050 --> 00:07:37,310
kerana sekali kita mengeluarkan
elemen, kita mahu

153
00:07:37,310 --> 00:07:40,720
untuk bergerak ke elemen tertua depan.

154
00:07:40,720 --> 00:07:44,180
>> Kemudian kita mahu untuk mengurangkan
saiz barisan,

155
00:07:44,180 --> 00:07:47,130
dan kemudian kita mahu kembali nilai
yang telah dikeluarkan dari barisan.

156
00:07:47,130 --> 00:07:48,921
Sekali lagi, kita tidak mahu hanya membuangnya.

157
00:07:48,921 --> 00:07:51,170
Kami mungkin akan mengeluarkan
dari queue-- kita berada

158
00:07:51,170 --> 00:07:54,170
dequeuing ia kerana kita mengambil berat mengenainya.

159
00:07:54,170 --> 00:08:01,080
Oleh itu, kita mahu fungsi ini untuk kembali
elemen data nilai jenis.

160
00:08:01,080 --> 00:08:04,360
Sekali lagi, dalam kes ini, nilai integer.

161
00:08:04,360 --> 00:08:05,670
>> Jadi sekarang mari kita dequeue sesuatu.

162
00:08:05,670 --> 00:08:09,310
Mari kita keluarkan unsur dari barisan.

163
00:08:09,310 --> 00:08:15,970
Jika kita mengatakan int x sama & q, Ampersand q--
sekali lagi bahawa adalah penunjuk kepada q data ini

164
00:08:15,970 --> 00:08:20,177
structure-- apa unsur
akan dapat dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Dalam kes ini, kerana ia adalah yang pertama
, keluar dahulu struktur data, FIFO,

167
00:08:29,480 --> 00:08:33,690
perkara pertama yang kita dimasukkan ke dalam ini
barisan adalah 28, dan sebagainya dalam kes ini,

168
00:08:33,690 --> 00:08:37,245
kita akan mengambil 28 daripada
barisan, tidak 19, iaitu apa yang

169
00:08:37,245 --> 00:08:38,870
kita akan lakukan jika ini adalah timbunan.

170
00:08:38,870 --> 00:08:42,220
Kami akan mengambil 28 daripada barisan.

171
00:08:42,220 --> 00:08:44,960
>> Sama dengan apa yang kita lakukan dengan
timbunan, kita tidak benar-benar

172
00:08:44,960 --> 00:08:47,345
akan memadam 28
dari barisan itu sendiri,

173
00:08:47,345 --> 00:08:49,470
kita hanya akan jenis
daripada berpura-pura ia tidak ada.

174
00:08:49,470 --> 00:08:51,678
Jadi ia akan tinggal di sana
dalam ingatan, tetapi kami hanya

175
00:08:51,678 --> 00:08:57,820
akan jenis mengabaikannya dengan menggerakkan
kedua-dua bidang lain data q kami

176
00:08:57,820 --> 00:08:58,830
struktur.

177
00:08:58,830 --> 00:09:00,230
Kami akan menukar bahagian depan.

178
00:09:00,230 --> 00:09:04,290
Q.front kini akan
1, kerana itu adalah sekarang

179
00:09:04,290 --> 00:09:07,740
unsur tertua kita ada dalam kita
barisan, kerana kita telah pun dikeluarkan 28,

180
00:09:07,740 --> 00:09:10,460
yang merupakan bekas elemen yang paling lama.

181
00:09:10,460 --> 00:09:13,540
>> Dan sekarang, kita ingin menukar
saiz barisan

182
00:09:13,540 --> 00:09:15,780
dua unsur dan bukannya tiga.

183
00:09:15,780 --> 00:09:20,450
Sekarang ingat sebelum ini saya katakan apabila kita
ingin menambah unsur-unsur untuk barisan,

184
00:09:20,450 --> 00:09:26,000
kami memasukkannya ke dalam lokasi yang mudah
yang adalah jumlah depan dan saiz.

185
00:09:26,000 --> 00:09:29,050
Jadi dalam kes ini, kami masih meletakkan
itu, elemen seterusnya dalam barisan,

186
00:09:29,050 --> 00:09:33,360
ke lokasi mudah 3, dan
kita akan melihat bahawa dalam satu saat.

187
00:09:33,360 --> 00:09:35,730
>> Jadi, sekarang kita telah dequeued kami
Elemen pertama dari barisan.

188
00:09:35,730 --> 00:09:36,480
Mari kita buat sekali lagi.

189
00:09:36,480 --> 00:09:38,696
Mari kita keluarkan lain
unsur dari barisan.

190
00:09:38,696 --> 00:09:42,400
Dalam kes itu, yang tertua semasa
elemen adalah lokasi mudah 1.

191
00:09:42,400 --> 00:09:44,220
Itulah yang q.front memberitahu kita.

192
00:09:44,220 --> 00:09:46,980
Bahawa kotak hijau memberitahu kita bahawa
itulah elemen yang paling lama.

193
00:09:46,980 --> 00:09:49,310
Dan sebagainya, x akan menjadi 33.

194
00:09:49,310 --> 00:09:52,130
Kami akan hanya jenis lupa
bahawa 33 wujud dalam array,

195
00:09:52,130 --> 00:09:55,100
dan kami akan mengatakan bahawa sekarang,
elemen baru tertua dalam barisan

196
00:09:55,100 --> 00:09:58,900
adalah di pelbagai lokasi 2, dan saiz
barisan, bilangan unsur

197
00:09:58,900 --> 00:10:02,152
kita ada dalam barisan, adalah 1.

198
00:10:02,152 --> 00:10:05,110
Sekarang mari kita enqueue sesuatu, dan saya
semacam memberikan ini jauh kedua yang lalu,

199
00:10:05,110 --> 00:10:10,340
tetapi jika kita mahu meletakkan 40 ke dalam
giliran, di mana adalah 40 akan pergi?

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

201
00:10:12,880 --> 00:10:17,730
Baik kita telah meletakkan ia
dalam q.front ditambah barisan saiz,

202
00:10:17,730 --> 00:10:20,850
dan jadi ia masuk akal untuk
sebenarnya untuk meletakkan 40 di sini.

203
00:10:20,850 --> 00:10:22,840
Sekarang perhatikan bahawa pada
satu ketika, kita akan

204
00:10:22,840 --> 00:10:27,980
untuk sampai ke akhir
pelbagai kami di dalam q,

205
00:10:27,980 --> 00:10:32,010
tetapi itu pudar 28 dan 33--
mereka benar-benar, dari segi teknikal

206
00:10:32,010 --> 00:10:33,300
kawasan lapang, bukan?

207
00:10:33,300 --> 00:10:36,040
Dan sebagainya, kita boleh eventually--
bahawa peraturan untuk menambah

208
00:10:36,040 --> 00:10:40,390
kedua-dua together-- kami mungkin akhirnya
perlu arena dengan saiz kapasiti

209
00:10:40,390 --> 00:10:41,410
supaya kita boleh membalut di sekitar.

210
00:10:41,410 --> 00:10:43,620
>> Jadi, jika kita dapat unsur
nombor 10, jika kita

211
00:10:43,620 --> 00:10:48,790
menggantikannya dalam bilangan elemen 10, kita akan
sebenarnya memasukkannya ke dalam pelbagai lokasi 0.

212
00:10:48,790 --> 00:10:50,997
Dan jika kami pergi ke
lokasi location-- maafkan saya,

213
00:10:50,997 --> 00:10:53,080
Kami tambahi mereka bersama-sama,
dan kami mendapat ke nombor

214
00:10:53,080 --> 00:10:56,330
11 adalah di mana kita perlu meletakkan
itu, yang tidak wujud dalam array-- ini

215
00:10:56,330 --> 00:10:58,200
ia akan keluar dari batas.

216
00:10:58,200 --> 00:11:03,367
Kita boleh arena oleh 10 dan meletakkan
dalam lokasi mudah 1.

217
00:11:03,367 --> 00:11:04,450
Jadi itulah bagaimana beratur bekerja.

218
00:11:04,450 --> 00:11:08,540
Mereka sentiasa akan pergi dari kiri
ke kanan dan mungkin membungkus.

219
00:11:08,540 --> 00:11:11,280
Dan anda tahu bahawa mereka
jika saiz penuh, bahawa kotak merah,

220
00:11:11,280 --> 00:11:13,710
menjadi sama dengan keupayaan.

221
00:11:13,710 --> 00:11:16,720
Dan jadi selepas kami telah menambah 40 kepada
giliran, akan apa yang perlu kita lakukan?

222
00:11:16,720 --> 00:11:19,890
Nah, elemen yang paling tua
dalam barisan masih 19,

223
00:11:19,890 --> 00:11:21,990
jadi kami tidak mahu berubah
bahagian depan barisan,

224
00:11:21,990 --> 00:11:23,820
tetapi kini kita mempunyai dua
unsur-unsur dalam barisan,

225
00:11:23,820 --> 00:11:28,710
dan dengan itu kita mahu meningkatkan
saiz kami 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Yang cukup banyak dengan
bekerja dengan beratur berdasarkan lokasi-,

227
00:11:31,820 --> 00:11:33,630
dan sama dengan timbunan,
terdapat juga cara yang

228
00:11:33,630 --> 00:11:36,450
untuk melaksanakan satu barisan sebagai senarai berpaut.

229
00:11:36,450 --> 00:11:40,150
Sekarang jika jenis struktur data ini
kelihatan biasa kepada anda, ia adalah.

230
00:11:40,150 --> 00:11:43,780
Ia bukan senarai secara tunggal berkaitan,
ia adalah senarai duanya adalah terpakai dikaitkan.

231
00:11:43,780 --> 00:11:46,790
Dan kini, sebagai diketepikan, ia adalah
sebenarnya mungkin untuk melaksanakan

232
00:11:46,790 --> 00:11:50,160
barisan sebagai satu senarai secara tunggal dikaitkan, tetapi
Saya rasa dari segi visualisasi,

233
00:11:50,160 --> 00:11:53,350
ia sebenarnya mungkin membantu untuk melihat
ini sebagai satu senarai duanya adalah terpakai dikaitkan.

234
00:11:53,350 --> 00:11:56,850
Tetapi ia pasti mungkin untuk
melakukan ini sebagai satu senarai secara tunggal berkaitan.

235
00:11:56,850 --> 00:12:00,110
>> Jadi mari kita lihat
apa ini mungkin kelihatan seperti.

236
00:12:00,110 --> 00:12:02,750
Jika kita mahu enquue--
jadi sekarang, sekali lagi kami

237
00:12:02,750 --> 00:12:05,360
beralih kepada berpaut-senarai
model berpangkalan di sini.

238
00:12:05,360 --> 00:12:08,420
Jika kita mahu enqueue, kita mahu
untuk menambah elemen baru, baik

239
00:12:08,420 --> 00:12:09,730
apa yang perlu kita lakukan?

240
00:12:09,730 --> 00:12:12,770
Well, pertama sekali, kerana
kami menambah hingga akhir

241
00:12:12,770 --> 00:12:15,520
dan mengeluarkan dari
bermula, kita mungkin

242
00:12:15,520 --> 00:12:20,050
mahu mengekalkan petunjuk kepada kedua-dua
kepala dan ekor senarai dikaitkan?

243
00:12:20,050 --> 00:12:22,660
Ekor yang satu lagi istilah untuk
akhir senarai berkaitan,

244
00:12:22,660 --> 00:12:24,496
elemen terakhir dalam senarai berkaitan.

245
00:12:24,496 --> 00:12:26,620
Dan ini akan mungkin,
sekali lagi, memberi manfaat kepada kami

246
00:12:26,620 --> 00:12:28,477
jika mereka adalah pembolehubah global.

247
00:12:28,477 --> 00:12:31,060
Tetapi sekarang jika kita mahu untuk menambah yang baru
unsur apa yang kita perlu lakukan?

248
00:12:31,060 --> 00:12:35,262
Apa yang kita hanya [? malak?] atau dinamik
memperuntukkan nod baru kami untuk diri kita sendiri.

249
00:12:35,262 --> 00:12:38,220
Dan kemudian, sama seperti ketika kita menambah apa-apa
elemen untuk senarai kita duanya adalah terpakai dikaitkan,

250
00:12:38,220 --> 00:12:40,410
hanya perlu menyusun daripada-
ketiga-tiga langkah terakhir di sini

251
00:12:40,410 --> 00:12:43,330
hanya tentang menggerakkan
petunjuk dengan cara yang betul

252
00:12:43,330 --> 00:12:46,710
supaya elemen akan ditambah ke
rantaian tanpa melanggar rantai

253
00:12:46,710 --> 00:12:49,580
atau membuat beberapa jenis kesilapan
atau mempunyai beberapa jenis kemalangan

254
00:12:49,580 --> 00:12:54,505
berlaku di mana kita tidak sengaja
anak yatim beberapa unsur-unsur barisan kami.

255
00:12:54,505 --> 00:12:55,880
Berikut adalah apa yang ini mungkin kelihatan seperti.

256
00:12:55,880 --> 00:13:00,980
Kami mahu menambah unsur
10 hingga akhir barisan ini.

257
00:13:00,980 --> 00:13:03,380
Jadi elemen tertua di sini
diwakili oleh kepala.

258
00:13:03,380 --> 00:13:06,800
Itu perkara yang pertama kita meletakkan
ke dalam barisan andaian ini di sini.

259
00:13:06,800 --> 00:13:10,430
Dan ekor, 13, adalah yang paling
baru-baru ini menambah unsur.

260
00:13:10,430 --> 00:13:17,030
Dan jadi jika kita mahu enqueue 10 ke dalam
barisan ini, kita mahu untuk meletakkan ia selepas 13.

261
00:13:17,030 --> 00:13:19,860
Dan dengan itu kita akan secara dinamik
memperuntukkan ruang untuk nod baru

262
00:13:19,860 --> 00:13:23,280
dan periksa null memastikan
kita tidak mempunyai kegagalan memori.

263
00:13:23,280 --> 00:13:27,040
Kemudian kita akan
meletakkan 10 ke nod itu,

264
00:13:27,040 --> 00:13:30,030
dan kini kita perlu berhati-hati
mengenai cara kami menyusun petunjuk

265
00:13:30,030 --> 00:13:32,180
jadi kami tidak memecahkan rantai.

266
00:13:32,180 --> 00:13:38,910
>> Kita boleh menetapkan bidang 10 sebelum ini
untuk menunjukkan kembali ke ekor yang lama,

267
00:13:38,910 --> 00:13:41,620
dan sejak '10 akan menjadi
ekor baru pada satu ketika

268
00:13:41,620 --> 00:13:44,459
dengan masa yang semua ini
rantai yang berkaitan,

269
00:13:44,459 --> 00:13:46,250
apa-apa yang akan datang
selepas 10 sekarang.

270
00:13:46,250 --> 00:13:49,880
Dan sebagainya penunjuk berikut 10 ini
akan menunjukkan kepada batal,

271
00:13:49,880 --> 00:13:53,580
dan kemudian selepas kita melakukan ini, selepas kami telah
disambungkan 10 ke belakang untuk rantai,

272
00:13:53,580 --> 00:13:57,780
kita boleh mengambil kepala lama, atau, alasan
saya, ekor lama barisan.

273
00:13:57,780 --> 00:14:02,980
Hujung lama barisan,
13, dan membuat ia menunjukkan 10.

274
00:14:02,980 --> 00:14:08,220
Dan sekarang, pada masa ini, kami mempunyai
enqueued nombor 10 ke dalam barisan ini.

275
00:14:08,220 --> 00:14:14,740
Apa yang kita perlu lakukan sekarang hanya menggerakkan
ekor untuk menghala ke 10 dan bukannya hingga 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing sebenarnya
hampir sama dengan bermunculan

277
00:14:17,630 --> 00:14:21,710
dari timbunan yang
dilaksanakan sebagai senarai berpaut

278
00:14:21,710 --> 00:14:24,040
jika anda telah melihat video susunan itu.

279
00:14:24,040 --> 00:14:27,280
Apa yang kita perlu lakukan adalah bermula pada
bermula, cari elemen kedua,

280
00:14:27,280 --> 00:14:30,480
membebaskan elemen pertama,
dan kemudian bergerak kepala

281
00:14:30,480 --> 00:14:32,930
untuk menunjukkan elemen kedua.

282
00:14:32,930 --> 00:14:37,920
Mungkin lebih baik untuk menggambarkan ia
hanya untuk menjadi tambahan yang jelas mengenainya.

283
00:14:37,920 --> 00:14:39,230
Jadi inilah barisan kita lagi.

284
00:14:39,230 --> 00:14:42,600
12 adalah unsur yang paling tua
dalam barisan kita, kepala.

285
00:14:42,600 --> 00:14:46,210
10 adalah unsur yang terbaru
dalam barisan kami, ekor kami.

286
00:14:46,210 --> 00:14:49,310
>> Dan supaya apabila kita hendak
untuk dequeue elemen,

287
00:14:49,310 --> 00:14:52,202
kita mahu mengeluarkan unsur yang paling lama.

288
00:14:52,202 --> 00:14:52,910
Jadi, apa yang kita lakukan?

289
00:14:52,910 --> 00:14:55,243
Baik kita menetapkan penunjuk penyusuran
yang bermula di kepala,

290
00:14:55,243 --> 00:14:57,840
dan kita bergerak ia supaya ia
mata kepada elemen kedua

291
00:14:57,840 --> 00:15:02,290
ini queue-- sesuatu dengan mengatakan trav
sama trav arrow akan datang, sebagai contoh,

292
00:15:02,290 --> 00:15:07,170
akan bergerak trav sana untuk menunjukkan
15, yang, selepas kami dequeue 12,

293
00:15:07,170 --> 00:15:13,030
atau selepas kita mengeluarkan 12, akan
menjadi elemen yang ketika itu yang paling lama.

294
00:15:13,030 --> 00:15:16,360
>> Sekarang kami mempunyai pegangan ke atas yang pertama
unsur melalui kepala penunjuk

295
00:15:16,360 --> 00:15:19,440
dan elemen kedua
melalui trav penunjuk.

296
00:15:19,440 --> 00:15:25,170
Kita boleh kepala kini bebas, dan kemudian kita boleh
berkata apa-apa datang sebelum 15 lagi.

297
00:15:25,170 --> 00:15:29,990
Oleh itu, kita boleh menukar 15 yang lepas
penunjuk kepada menunjukkan batal,

298
00:15:29,990 --> 00:15:31,874
dan kita hanya menggerakkan kepala ke atas.

299
00:15:31,874 --> 00:15:32,540
Dan kita pergi.

300
00:15:32,540 --> 00:15:35,840
Sekarang kita telah berjaya
dequeued 12, dan sekarang kita

301
00:15:35,840 --> 00:15:39,180
mempunyai satu lagi barisan 4 elemen.

302
00:15:39,180 --> 00:15:41,700
Yang cukup banyak semua
ada untuk beratur,

303
00:15:41,700 --> 00:15:45,810
kedua-dua lokasi berasaskan dan dihubungkan-senarai berasaskan.

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

305
00:15:46,860 --> 00:15:49,100
Ini adalah CS 50.

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