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

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Jadi jika Anda sudah
menonton video di stack,

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

4
00:00:09,870 --> 00:00:13,850
Ini akan konsep yang sangat mirip,
hanya dengan sedikit twist di atasnya.

5
00:00:13,850 --> 00:00:15,530
Kita akan bicara sekarang tentang antrian.

6
00:00:15,530 --> 00:00:19,350
Jadi antrian, mirip dengan tumpukan,
adalah jenis lain dari struktur data

7
00:00:19,350 --> 00:00:22,412
yang bisa kita gunakan untuk mempertahankan
Data secara terorganisasi.

8
00:00:22,412 --> 00:00:24,120
Mirip dengan tumpukan,
dapat diimplementasikan

9
00:00:24,120 --> 00:00:27,000
sebagai array atau linked list.

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

11
00:00:30,320 --> 00:00:34,210
ketika hal-hal akan ditambahkan dan dihapus dari
antrian yang sedikit berbeda.

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

13
00:00:36,590 --> 00:00:45,610
bertahan di, keluar pertama, antrian adalah FIFO
struktur, FIFO, pertama, keluar pertama.

14
00:00:45,610 --> 00:00:49,320
Sekarang antrian, Anda mungkin
memiliki analogi antrian.

15
00:00:49,320 --> 00:00:52,820
Jika Anda pernah berada di baris di
sebuah taman hiburan atau di bank,

16
00:00:52,820 --> 00:00:56,430
ada semacam keadilan yang
menerapkan struktur.

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

18
00:00:59,160 --> 00:01:00,760
siapa yang akan berbicara dengan teller.

19
00:01:00,760 --> 00:01:03,522
>> Ini akan menjadi semacam perlombaan
ke bawah jika satu-satunya cara

20
00:01:03,522 --> 00:01:06,730
Anda harus berbicara dengan teller di
Bank adalah untuk menjadi orang terakhir di line.

21
00:01:06,730 --> 00:01:09,146
Semua orang selalu ingin
menjadi orang terakhir di line,

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

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

24
00:01:14,715 --> 00:01:17,590
sebelum mereka memiliki kesempatan untuk benar-benar
menarik uang di bank.

25
00:01:17,590 --> 00:01:22,510
Dan jadi antrian semacam itu
keadilan menerapkan struktur.

26
00:01:22,510 --> 00:01:25,780
Tapi itu tidak berarti
yang tumpukan adalah hal yang buruk, hanya

27
00:01:25,780 --> 00:01:28,160
yang antrian adalah cara lain untuk melakukannya.

28
00:01:28,160 --> 00:01:32,420
Jadi sekali lagi antrian pertama di, pertama
keluar, versus tumpukan yang berlangsung di,

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

30
00:01:34,440 --> 00:01:36,190
Mirip dengan tumpukan,
kita memiliki dua operasi

31
00:01:36,190 --> 00:01:38,470
bahwa kita dapat melakukan pada antrian.

32
00:01:38,470 --> 00:01:43,910
Nama-nama yang enqueue, yang menambahkan
elemen baru ke akhir antrian,

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

34
00:01:47,330 --> 00:01:49,670
elemen dari depan antrian.

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

36
00:01:53,600 --> 00:01:57,220
dan kita akan menghapus elemen
dari depan antrian.

37
00:01:57,220 --> 00:02:00,790
Sekali lagi, dengan tumpukan, kami menambahkan
elemen ke atas tumpukan

38
00:02:00,790 --> 00:02:03,380
dan menghapus elemen
dari puncak stack.

39
00:02:03,380 --> 00:02:07,570
Jadi dengan enqueue, itu menambah
akhir, menghapus dari depan.

40
00:02:07,570 --> 00:02:10,639
Jadi hal tertua di sana
selalu hal berikutnya

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

42
00:02:13,620 --> 00:02:18,330
>> Jadi sekali lagi, dengan antrian, kita bisa
implementasi array berbasis

43
00:02:18,330 --> 00:02:20,110
dan terkait-daftar implementasi berbasis.

44
00:02:20,110 --> 00:02:24,620
Kita akan mulai lagi dengan
implementasi berbasis array.

45
00:02:24,620 --> 00:02:27,070
Definisi struktur
terlihat sangat mirip.

46
00:02:27,070 --> 00:02:30,720
Kami memiliki array lain
ada tipe data nilai,

47
00:02:30,720 --> 00:02:32,690
sehingga dapat menahan tipe data yang sewenang-wenang.

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

49
00:02:35,570 --> 00:02:39,830
>> Dan seperti dengan kami
implementasi tumpukan berbasis array,

50
00:02:39,830 --> 00:02:42,340
karena kita menggunakan
array, kita tentu

51
00:02:42,340 --> 00:02:46,850
memiliki keterbatasan bahwa C jenis
dari memaksa kita, yang kita

52
00:02:46,850 --> 00:02:51,670
tidak memiliki dinamika di kami
kemampuan untuk tumbuh dan menyusut array.

53
00:02:51,670 --> 00:02:55,710
Kita harus memutuskan di awal
apa jumlah maksimum hal

54
00:02:55,710 --> 00:02:59,300
bahwa kita dapat dimasukkan ke dalam ini
antrian, dan dalam hal ini,

55
00:02:59,300 --> 00:03:02,070
Kapasitas akan beberapa pound
didefinisikan konstan dalam kode kita.

56
00:03:02,070 --> 00:03:05,430
Dan untuk tujuan ini
video, kapasitas akan menjadi 10.

57
00:03:05,430 --> 00:03:07,690
>> Kita perlu untuk melacak
bagian depan antrian

58
00:03:07,690 --> 00:03:11,160
jadi kita tahu mana elemen
kami ingin dequeue,

59
00:03:11,160 --> 00:03:15,070
dan kita juga perlu melacak
sesuatu else-- jumlah elemen

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

61
00:03:16,690 --> 00:03:19,360
Perhatikan kita tidak melacak
dari akhir antrian, hanya

62
00:03:19,360 --> 00:03:21,150
ukuran antrian.

63
00:03:21,150 --> 00:03:24,310
Dan alasan untuk itu akan mudah-mudahan
menjadi sedikit lebih jelas dalam sekejap.

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

65
00:03:26,143 --> 00:03:29,080
kami memiliki tipe data baru
disebut antrian, yang sekarang kita bisa

66
00:03:29,080 --> 00:03:30,630
mendeklarasikan variabel dari jenis data.

67
00:03:30,630 --> 00:03:35,350
Dan agak membingungkan, saya telah memutuskan
untuk memanggil antrian q ini, surat itu

68
00:03:35,350 --> 00:03:38,090
q bukan tipe data q.

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

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

71
00:03:40,700 --> 00:03:45,730
Ini berisi tiga anggota atau tiga
bidang, array ukuran KAPASITAS.

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

73
00:03:47,340 --> 00:03:49,580
Dan array ini adalah
akan terus bilangan bulat.

74
00:03:49,580 --> 00:03:55,240
Hijau adalah depan antrian kami,
Unsur berikutnya yang akan dihapus, dan merah

75
00:03:55,240 --> 00:03:58,610
akan menjadi ukuran antrian,
berapa banyak elemen saat ini

76
00:03:58,610 --> 00:04:01,190
ada dalam antrian.

77
00:04:01,190 --> 00:04:05,300
Jadi jika kita mengatakan equals q.front
0, dan ukuran q.size sama 0--

78
00:04:05,300 --> 00:04:07,120
kami menempatkan 0s ke bidang-bidang.

79
00:04:07,120 --> 00:04:11,070
Dan pada titik ini, kami cukup banyak
siap untuk mulai bekerja dengan antrian kami.

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

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

82
00:04:16,860 --> 00:04:19,089
Nah apa yang kita butuhkan untuk
lakukan dalam kasus umum?

83
00:04:19,089 --> 00:04:23,690
Nah fungsi ini enqueue kebutuhan
untuk menerima pointer ke antrian kami.

84
00:04:23,690 --> 00:04:26,370
Sekali lagi, jika kita telah menyatakan
antrian kami secara global,

85
00:04:26,370 --> 00:04:29,490
kita tidak perlu melakukan hal ini
tentu, tetapi secara umum, kami

86
00:04:29,490 --> 00:04:32,330
harus menerima pointer
untuk struktur data

87
00:04:32,330 --> 00:04:35,040
seperti ini, karena jika tidak,
kita lewat value-- kami

88
00:04:35,040 --> 00:04:38,140
lewat di salinan antrian,
dan jadi kita tidak benar-benar berubah

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

90
00:04:41,050 --> 00:04:44,860
>> Hal lain yang perlu dilakukan adalah menerima
elemen data jenis yang sesuai.

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

92
00:04:46,818 --> 00:04:49,330
tapi Anda bisa sewenang-wenang
mendeklarasikan tipe data sebagai nilai

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

94
00:04:51,160 --> 00:04:56,030
Itulah unsur kita ingin enqueue,
kita ingin menambahkan ke akhir antrian.

95
00:04:56,030 --> 00:04:58,573
Kemudian kita benar-benar ingin
menempatkan data yang dalam antrian.

96
00:04:58,573 --> 00:05:01,490
Dalam hal ini, menempatkannya di
lokasi yang benar dari array kita,

97
00:05:01,490 --> 00:05:05,040
dan kemudian kita ingin mengubah ukuran
antrian, berapa banyak elemen yang kita

98
00:05:05,040 --> 00:05:07,050
saat ini.

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

100
00:05:07,990 --> 00:05:10,890
Berikut ini adalah, sekali lagi, yang umum
Fungsi bentuk deklarasi

101
00:05:10,890 --> 00:05:13,980
untuk apa enqueue mungkin terlihat 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 enqueue nomor
28 ke dalam antrian.

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

105
00:05:19,460 --> 00:05:23,390
Nah, bagian depan antrian kami adalah
pada 0, dan ukuran antrian kami

106
00:05:23,390 --> 00:05:29,680
adalah pada 0, dan jadi kita mungkin ingin menempatkan
jumlah 28 jumlah elemen array

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

108
00:05:31,124 --> 00:05:32,540
Jadi sekarang kami telah ditempatkan bahwa dalam sana.

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

110
00:05:34,820 --> 00:05:37,090
Kami tidak ingin mengubah
bagian depan antrian,

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

112
00:05:40,850 --> 00:05:44,020
Jadi alasan kita harus depan ada
adalah semacam indikator apa

113
00:05:44,020 --> 00:05:46,439
hal tertua di array.

114
00:05:46,439 --> 00:05:49,730
Nah hal tertua di array-- dalam
Bahkan, satu-satunya hal dalam array yang tepat

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

116
00:05:53,540 --> 00:05:56,160
Jadi kita tidak ingin
mengubah nomor hijau,

117
00:05:56,160 --> 00:05:57,910
karena itulah unsur tertua.

118
00:05:57,910 --> 00:06:00,510
Sebaliknya, kita ingin mengubah ukuran.

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

120
00:06:04,110 --> 00:06:08,430
>> Sekarang semacam umum ide di mana
Elemen berikutnya akan masuk antrian

121
00:06:08,430 --> 00:06:12,310
adalah untuk menambahkan dua angka
bersama-sama, depan dan ukuran,

122
00:06:12,310 --> 00:06:16,390
dan yang akan memberitahu Anda di mana selanjutnya
elemen dalam antrian akan pergi.

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

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

125
00:06:20,250 --> 00:06:24,480
Jadi 33 akan masuk ke
Array lokasi 0 ditambah 1.

126
00:06:24,480 --> 00:06:26,840
Jadi dalam hal ini, itu akan
untuk pergi ke dalam array lokasi 1,

127
00:06:26,840 --> 00:06:29,500
dan sekarang ukuran antrian kami adalah 2.

128
00:06:29,500 --> 00:06:31,840
>> Sekali lagi, kita tidak mengubah
bagian depan antrian kami,

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

130
00:06:34,730 --> 00:06:38,220
ingin to-- ketika kita akhirnya mendapatkan
untuk dequeuing, menghapus elemen

131
00:06:38,220 --> 00:06:43,300
dari antrian ini, kami ingin tahu
di mana unsur tertua adalah.

132
00:06:43,300 --> 00:06:48,620
Dan jadi kita selalu perlu untuk mempertahankan
beberapa indikator 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 sana untuk.

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

136
00:06:55,022 --> 00:06:56,980
Saya yakin Anda bisa menebak
di mana 19 akan pergi.

137
00:06:56,980 --> 00:06:59,860
Ini akan masuk ke
Array lokasi nomor 2.

138
00:06:59,860 --> 00:07:01,570
Itu 0 ditambah 2.

139
00:07:01,570 --> 00:07:03,199
Dan sekarang ukuran antrian kami adalah 3.

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

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

142
00:07:08,490 --> 00:07:11,370
itu akan masuk ke lokasi array yang
nomor 3, dan ukuran antrian kami

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

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

145
00:07:15,279 --> 00:07:16,570
Sekarang mari kita mulai untuk menghapusnya.

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

147
00:07:19,450 --> 00:07:23,340
>> Jadi mirip dengan pop, yang merupakan semacam
dari analog ini untuk tumpukan,

148
00:07:23,340 --> 00:07:26,180
dequeue perlu menerima
pointer ke queue-- lagi,

149
00:07:26,180 --> 00:07:28,140
kecuali jika dinyatakan secara global.

150
00:07:28,140 --> 00:07:31,610
Sekarang kita ingin mengubah lokasi
dari depan antrian.

151
00:07:31,610 --> 00:07:35,050
Ini adalah di mana ia semacam datang
ke dalam bermain, bahwa variabel depan,

152
00:07:35,050 --> 00:07:37,310
karena sekali kita hapus
elemen, kita ingin

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

154
00:07:40,720 --> 00:07:44,180
>> Kemudian kita ingin menurunkan
ukuran antrian,

155
00:07:44,180 --> 00:07:47,130
dan kemudian kita ingin mengembalikan nilai
yang telah dihapus dari antrian.

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

157
00:07:48,921 --> 00:07:51,170
Kami mungkin penggalian
itu dari queue-- kami

158
00:07:51,170 --> 00:07:54,170
dequeuing itu karena kami peduli tentang hal itu.

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

160
00:08:01,080 --> 00:08:04,360
Sekali lagi, dalam kasus ini, nilai adalah bilangan bulat.

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 menghapus elemen dari antrian.

163
00:08:09,310 --> 00:08:15,970
Jika kita mengatakan int x sama & q, ampersand q--
lagi itu pointer ke data yang q ini

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

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

166
00:08:23,840 --> 00:08:29,480
Dalam hal ini, karena merupakan pertama
, keluar pertama struktur data, FIFO,

167
00:08:29,480 --> 00:08:33,690
hal pertama yang kita dimasukkan ke dalam ini
antrian adalah 28, dan dalam hal ini,

168
00:08:33,690 --> 00:08:37,245
kita akan mengambil 28 dari
antrian, tidak 19, yang adalah apa yang

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

170
00:08:38,870 --> 00:08:42,220
Kita akan mengambil 28 dari antrian.

171
00:08:42,220 --> 00:08:44,960
>> Mirip dengan apa yang kita lakukan dengan
stack, kami tidak benar-benar

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

173
00:08:47,345 --> 00:08:49,470
kami hanya akan jenis
dari berpura-pura itu tidak ada.

174
00:08:49,470 --> 00:08:51,678
Jadi itu akan tinggal di sana
dalam memori, tapi kami hanya

175
00:08:51,678 --> 00:08:57,820
akan jenis mengabaikannya dengan memindahkan
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
Kita akan mengubah bagian depan.

178
00:09:00,230 --> 00:09:04,290
Q.front sekarang akan
menjadi 1, karena yang sekarang

179
00:09:04,290 --> 00:09:07,740
unsur tertua yang kita miliki di kami
antrian, karena kita sudah dihapus 28,

180
00:09:07,740 --> 00:09:10,460
yang merupakan mantan unsur tertua.

181
00:09:10,460 --> 00:09:13,540
>> Dan sekarang, kami ingin mengubah
ukuran antrian

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

183
00:09:15,780 --> 00:09:20,450
Sekarang ingat sebelumnya saya katakan ketika kita
ingin menambahkan elemen ke antrian,

184
00:09:20,450 --> 00:09:26,000
kita meletakkannya di lokasi array yang
yang merupakan jumlah dari depan dan ukuran.

185
00:09:26,000 --> 00:09:29,050
Jadi dalam hal ini, kami masih menempatkan
itu, elemen berikutnya dalam antrian,

186
00:09:29,050 --> 00:09:33,360
ke dalam array lokasi 3, dan
kita akan melihat bahwa dalam satu detik.

187
00:09:33,360 --> 00:09:35,730
>> Jadi kita sekarang sudah dequeued kami
elemen pertama dari antrian.

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

189
00:09:36,480 --> 00:09:38,696
Mari kita hapus lain
elemen dari antrian.

190
00:09:38,696 --> 00:09:42,400
Dalam kasus ini, saat tertua
elemen Array lokasi 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
Kotak hijau memberitahu kita bahwa
itulah unsur tertua.

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
yang 33 ada di array,

195
00:09:52,130 --> 00:09:55,100
dan kami akan mengatakan bahwa saat ini,
Unsur tertua baru dalam antrian

196
00:09:55,100 --> 00:09:58,900
di berbagai lokasi 2, dan ukuran
antrian, jumlah elemen

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

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

199
00:10:05,110 --> 00:10:10,340
tetapi jika kita ingin menempatkan 40 ke
antrian, di mana yang 40 akan pergi?

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

201
00:10:12,880 --> 00:10:17,730
Nah kita sudah menempatkan
di q.front ditambah antrian ukuran,

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

203
00:10:20,850 --> 00:10:22,840
Sekarang perhatikan bahwa pada
beberapa titik, kita akan

204
00:10:22,840 --> 00:10:27,980
untuk sampai ke akhir
array kita dalam q,

205
00:10:27,980 --> 00:10:32,010
tapi itu memudar keluar 28 dan 33--
mereka sebenarnya, secara teknis

206
00:10:32,010 --> 00:10:33,300
ruang terbuka, kan?

207
00:10:33,300 --> 00:10:36,040
Dan, kita dapat eventually--
bahwa aturan menambahkan

208
00:10:36,040 --> 00:10:40,390
dua together-- kita mungkin akhirnya
perlu mod dengan ukuran kapasitas

209
00:10:40,390 --> 00:10:41,410
sehingga kita bisa membungkus.

210
00:10:41,410 --> 00:10:43,620
>> Jadi jika kita mendapatkan elemen
nomor 10, jika kita

211
00:10:43,620 --> 00:10:48,790
menggantinya jumlahnya elemen 10, kami akan
benar-benar menempatkan itu dalam array lokasi 0.

212
00:10:48,790 --> 00:10:50,997
Dan jika kita akan
Array yang lokasi permisi,

213
00:10:50,997 --> 00:10:53,080
jika kita menambahkan mereka bersama-sama,
dan kita harus nomor

214
00:10:53,080 --> 00:10:56,330
11 akan di mana kita harus menempatkan
itu, yang tidak ada di array-- ini

215
00:10:56,330 --> 00:10:58,200
itu akan terjadi di luar batas.

216
00:10:58,200 --> 00:11:03,367
Kita bisa mod 10 dan menempatkan
itu dalam array lokasi 1.

217
00:11:03,367 --> 00:11:04,450
Jadi itulah cara antrian bekerja.

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

219
00:11:08,540 --> 00:11:11,280
Dan Anda tahu bahwa mereka
penuh jika ukuran, kotak merah,

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

221
00:11:13,710 --> 00:11:16,720
Dan setelah kami telah menambahkan 40 ke
antrian, baik apa yang perlu kita lakukan?

222
00:11:16,720 --> 00:11:19,890
Nah, elemen tertua
dalam antrian masih 19,

223
00:11:19,890 --> 00:11:21,990
jadi kami tidak ingin mengubah
bagian depan antrian,

224
00:11:21,990 --> 00:11:23,820
tapi sekarang kami memiliki dua
elemen dalam antrian,

225
00:11:23,820 --> 00:11:28,710
dan jadi kami ingin meningkatkan
ukuran kami 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Itu cukup banyak itu dengan
bekerja dengan antrian berbasis array,

227
00:11:31,820 --> 00:11:33,630
dan mirip dengan stack,
ada juga cara

228
00:11:33,630 --> 00:11:36,450
untuk menerapkan antrian sebagai linked list.

229
00:11:36,450 --> 00:11:40,150
Sekarang jika ini jenis struktur data
tampak akrab bagi Anda, itu.

230
00:11:40,150 --> 00:11:43,780
Ini bukan daftar sendiri-sendiri terkait,
itu daftar ganda terkait.

231
00:11:43,780 --> 00:11:46,790
Dan sekarang, sebagai samping, itu adalah
sebenarnya mungkin untuk mengimplementasikan

232
00:11:46,790 --> 00:11:50,160
antrian sebagai daftar tunggal terkait, tapi
Saya pikir dalam hal visualisasi,

233
00:11:50,160 --> 00:11:53,350
itu benar-benar dapat membantu untuk melihat
ini sebagai daftar ganda terkait.

234
00:11:53,350 --> 00:11:56,850
Tapi pasti mungkin untuk
melakukan hal ini sebagai daftar tunggal terkait.

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

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

237
00:12:02,750 --> 00:12:05,360
beralih ke-linked list
Model berbasis di sini.

238
00:12:05,360 --> 00:12:08,420
Jika kita ingin enqueue, kami ingin
untuk menambahkan 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
Yah, pertama-tama, karena
kita menambahkan sampai akhir

241
00:12:12,770 --> 00:12:15,520
dan menghapus dari
mulai, kita mungkin

242
00:12:15,520 --> 00:12:20,050
ingin mempertahankan pointer ke kedua
kepala dan ekor dari linked list?

243
00:12:20,050 --> 00:12:22,660
Ekor menjadi istilah lain untuk
akhir linked list,

244
00:12:22,660 --> 00:12:24,496
elemen terakhir dalam linked list.

245
00:12:24,496 --> 00:12:26,620
Dan mungkin ini akan,
lagi, bermanfaat bagi kami

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

247
00:12:28,477 --> 00:12:31,060
Tapi sekarang jika kita ingin menambahkan baru
unsur apa yang harus kita lakukan?

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

249
00:12:35,262 --> 00:12:38,220
Dan kemudian, sama seperti ketika kita menambahkan
elemen ke ganda terkait daftar kami,

250
00:12:38,220 --> 00:12:40,410
hanya perlu memilah of--
tiga langkah terakhir di sini

251
00:12:40,410 --> 00:12:43,330
hanya semua tentang memindahkan
pointer dalam cara yang benar

252
00:12:43,330 --> 00:12:46,710
sehingga elemen akan ditambahkan ke
rantai tanpa melanggar rantai

253
00:12:46,710 --> 00:12:49,580
atau membuat semacam kesalahan
atau memiliki semacam kecelakaan

254
00:12:49,580 --> 00:12:54,505
terjadi dimana kami sengaja
yatim beberapa elemen dari antrian kami.

255
00:12:54,505 --> 00:12:55,880
Inilah yang ini mungkin terlihat seperti.

256
00:12:55,880 --> 00:13:00,980
Kita ingin menambahkan elemen
10 sampai akhir antrian ini.

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

258
00:13:03,380 --> 00:13:06,800
Itulah hal pertama yang kita menempatkan
ke dalam antrian hipotetis ini di sini.

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

260
00:13:10,430 --> 00:13:17,030
Dan jika kita ingin enqueue 10 ke
antrian ini, kita ingin menempatkan setelah 13.

261
00:13:17,030 --> 00:13:19,860
Dan kita akan dinamis
mengalokasikan ruang untuk node baru

262
00:13:19,860 --> 00:13:23,280
dan memeriksa null untuk memastikan
kita tidak memiliki kegagalan memori.

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

264
00:13:27,040 --> 00:13:30,030
dan sekarang kita harus berhati-hati
tentang bagaimana kita mengatur pointer

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

266
00:13:32,180 --> 00:13:38,910
>> Kita dapat mengatur bidang 10 sebelumnya
untuk menunjuk kembali ke ekor tua,

267
00:13:38,910 --> 00:13:41,620
dan karena '10 akan menjadi
ekor baru di beberapa titik

268
00:13:41,620 --> 00:13:44,459
pada saat semua ini
rantai yang terhubung,

269
00:13:44,459 --> 00:13:46,250
tidak ada yang akan datang
setelah 10 sekarang.

270
00:13:46,250 --> 00:13:49,880
Dan 10 untuk pointer berikutnya
akan menunjuk ke null,

271
00:13:49,880 --> 00:13:53,580
dan kemudian setelah kami melakukan hal ini, setelah kami sudah
Koneksi 10 belakang untuk rantai,

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

273
00:13:57,780 --> 00:14:02,980
Akhir lama antrian,
13, dan membuatnya menunjuk ke 10.

274
00:14:02,980 --> 00:14:08,220
Dan sekarang, pada titik ini, kita memiliki
enqueued nomor 10 ke dalam antrian ini.

275
00:14:08,220 --> 00:14:14,740
Semua yang perlu kita lakukan sekarang adalah hanya memindahkan
ekor untuk menunjuk ke 10 bukan ke 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing sebenarnya
sangat mirip dengan bermunculan

277
00:14:17,630 --> 00:14:21,710
dari tumpukan yang
diimplementasikan sebagai linked list

278
00:14:21,710 --> 00:14:24,040
jika Anda pernah melihat tumpukan video.

279
00:14:24,040 --> 00:14:27,280
Semua yang perlu kita lakukan adalah mulai di
mulai, menemukan elemen kedua,

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

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

282
00:14:32,930 --> 00:14:37,920
Mungkin lebih baik untuk memvisualisasikan itu
hanya untuk menjadi tambahan yang jelas tentang hal itu.

283
00:14:37,920 --> 00:14:39,230
Jadi, inilah antrian kami lagi.

284
00:14:39,230 --> 00:14:42,600
12 adalah unsur tertua
dalam antrian kami, kepala.

285
00:14:42,600 --> 00:14:46,210
10 adalah elemen terbaru
dalam antrian kami, ekor kami.

286
00:14:46,210 --> 00:14:49,310
>> Dan ketika kita ingin
untuk dequeue elemen,

287
00:14:49,310 --> 00:14:52,202
kita ingin menghapus elemen tertua.

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 pointer traversal
yang dimulai di kepala,

290
00:14:55,243 --> 00:14:57,840
dan kami memindahkannya sehingga
menunjuk ke elemen kedua

291
00:14:57,840 --> 00:15:02,290
ini queue-- sesuatu dengan mengatakan trav
sama trav panah berikutnya, misalnya,

292
00:15:02,290 --> 00:15:07,170
akan pindah trav ada untuk menunjuk ke
15, yang, setelah kami dequeue 12,

293
00:15:07,170 --> 00:15:13,030
atau setelah kita menghapus 12, akan
menjadi elemen kemudian tertua.

294
00:15:13,030 --> 00:15:16,360
>> Sekarang kita punya pegangan pada pertama
Unsur melalui kepala pointer

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

296
00:15:19,440 --> 00:15:25,170
Kita bisa kepala sekarang bebas, dan kemudian kita bisa
mengatakan tidak ada yang datang sebelum 15 lagi.

297
00:15:25,170 --> 00:15:29,990
Jadi kita dapat mengubah 15 sebelumnya
pointer untuk menunjuk ke null,

298
00:15:29,990 --> 00:15:31,874
dan kami hanya memindahkan kepala lebih.

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

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

301
00:15:35,840 --> 00:15:39,180
memiliki antrian lain 4 elemen.

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

303
00:15:41,700 --> 00:15:45,810
baik-array berbasis dan terkait-daftar berbasis.

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

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

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