1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: Baiklah,
sehingga pada titik ini Anda

3
00:00:05,990 --> 00:00:09,020
mungkin cukup familiar
dengan array dan daftar terkait

4
00:00:09,020 --> 00:00:10,950
yang merupakan dua utama
struktur data kita sudah

5
00:00:10,950 --> 00:00:16,810
berbicara tentang untuk menjaga set
Data dari jenis data yang sama terorganisir.

6
00:00:16,810 --> 00:00:19,080
>> Sekarang kita akan berbicara
tentang beberapa variasi

7
00:00:19,080 --> 00:00:20,330
pada array dan daftar terkait.

8
00:00:20,330 --> 00:00:22,362
Dalam video ini kita akan
untuk berbicara tentang tumpukan.

9
00:00:22,362 --> 00:00:25,320
Secara khusus kita akan berbicara
tentang struktur data yang disebut stack.

10
00:00:25,320 --> 00:00:28,510
Ingat dari diskusi sebelumnya
tentang pointer dan memori,

11
00:00:28,510 --> 00:00:32,060
bahwa tumpukan juga
nama untuk segmen memori

12
00:00:32,060 --> 00:00:34,980
mana statis dideklarasikan
memori memory-- yang Anda

13
00:00:34,980 --> 00:00:38,730
nama, variabel yang Anda nama, et
sebagainya dan fungsi frame yang kami juga

14
00:00:38,730 --> 00:00:41,000
tumpukan frame panggilan ada.

15
00:00:41,000 --> 00:00:45,421
Jadi ini adalah struktur data stack
tidak segmen tumpukan memori.

16
00:00:45,421 --> 00:00:45,920
OKE.

17
00:00:45,920 --> 00:00:46,890
>> Tapi apa stack?

18
00:00:46,890 --> 00:00:49,220
Sehingga cukup banyak hanya
jenis khusus dari struktur

19
00:00:49,220 --> 00:00:51,190
yang mempertahankan data dalam cara yang terorganisir.

20
00:00:51,190 --> 00:00:53,760
Dan ada dua yang sangat
cara umum untuk melaksanakan

21
00:00:53,760 --> 00:00:57,380
tumpukan menggunakan dua struktur data
bahwa kita sudah akrab dengan,

22
00:00:57,380 --> 00:01:00,340
array dan daftar terkait.

23
00:01:00,340 --> 00:01:04,430
Apa yang membuat tumpukan khusus adalah
cara di mana kita menaruh informasi

24
00:01:04,430 --> 00:01:08,200
ke dalam stack, dan cara kita
menghapus informasi dari stack.

25
00:01:08,200 --> 00:01:11,600
Khususnya dengan tumpukan
Aturan ini hanya yang paling

26
00:01:11,600 --> 00:01:15,830
baru-baru ini elemen ditambahkan dapat dihapus.

27
00:01:15,830 --> 00:01:17,660
>> Jadi pikirkan tentang hal itu seolah-olah itu stack.

28
00:01:17,660 --> 00:01:21,170
Kami menumpuk informasi
di atas itu sendiri,

29
00:01:21,170 --> 00:01:24,271
dan hanya hal di atas
tumpukan dapat dihapus.

30
00:01:24,271 --> 00:01:27,020
Kita tidak dapat menghapus hal di bawahnya
karena segala sesuatu yang lain akan

31
00:01:27,020 --> 00:01:28,020
runtuh dan jatuh.

32
00:01:28,020 --> 00:01:32,580
Jadi kita benar-benar sedang membangun tumpukan yang
kita kemudian harus menghapus sepotong demi sepotong.

33
00:01:32,580 --> 00:01:36,590
Karena ini kita sering merujuk
untuk stack sebagai struktur LIFO,

34
00:01:36,590 --> 00:01:38,940
bertahan di, keluar pertama.

35
00:01:38,940 --> 00:01:42,290
LIFO, bertahan, keluar pertama.

36
00:01:42,290 --> 00:01:45,635
>> Jadi karena pembatasan ini pada
bagaimana informasi dapat ditambahkan ke

37
00:01:45,635 --> 00:01:49,080
dan dihapus dari tumpukan, ada benar-benar
hanya ada dua hal yang dapat kita lakukan dengan tumpukan.

38
00:01:49,080 --> 00:01:52,010
Kita dapat mendorong, yang merupakan
istilah yang kita gunakan untuk menambahkan

39
00:01:52,010 --> 00:01:55,130
elemen baru ke atas
tumpukan, atau jika stack tidak ada

40
00:01:55,130 --> 00:01:58,550
dan kami menciptakan dari awal,
menciptakan tumpukan di tempat pertama

41
00:01:58,550 --> 00:02:00,110
akan mendorong.

42
00:02:00,110 --> 00:02:04,990
Dan kemudian pop, itulah semacam CS
istilah yang kita gunakan untuk menghapus yang paling baru

43
00:02:04,990 --> 00:02:08,330
menambahkan elemen dari puncak stack.

44
00:02:08,330 --> 00:02:11,130
>> Jadi kita akan melihat kedua
implementasi, baik array yang berdasarkan

45
00:02:11,130 --> 00:02:13,120
dan daftar link berbasis.

46
00:02:13,120 --> 00:02:14,870
Dan kita akan
mulai dengan berbagai berbasis.

47
00:02:14,870 --> 00:02:19,990
Jadi, inilah ide dasar dari apa yang
struktur data stack array yang berdasarkan

48
00:02:19,990 --> 00:02:21,140
akan terlihat seperti.

49
00:02:21,140 --> 00:02:23,740
Kami memiliki definisi diketik di sini.

50
00:02:23,740 --> 00:02:27,790
Dalam bahwa kita memiliki dua anggota
atau bidang struktur.

51
00:02:27,790 --> 00:02:29,880
Kami memiliki sebuah array.

52
00:02:29,880 --> 00:02:32,400
Dan lagi aku menggunakan
sewenang-wenang nilai tipe data.

53
00:02:32,400 --> 00:02:35,180
>> Jadi ini bisa menjadi jenis data,
int Char atau beberapa data lainnya

54
00:02:35,180 --> 00:02:37,080
ketik sebelumnya Anda buat.

55
00:02:37,080 --> 00:02:39,861
Jadi kita memiliki sebuah array ukuran kapasitas.

56
00:02:39,861 --> 00:02:44,010
Kapasitas yang pon didefinisikan konstan,
mungkin di tempat lain dalam file kami.

57
00:02:44,010 --> 00:02:47,550
Jadi melihat sudah dengan khusus ini
implementasi kita berlari

58
00:02:47,550 --> 00:02:49,800
diri seperti biasanya
kasus dengan array,

59
00:02:49,800 --> 00:02:53,170
yang kita tidak bisa mengubah ukuran dinamis,
di mana ada sejumlah

60
00:02:53,170 --> 00:02:55,450
elemen maksimum yang
kita bisa dimasukkan ke dalam tumpukan kami.

61
00:02:55,450 --> 00:02:57,930
Dalam hal ini itu unsur kapasitas.

62
00:02:57,930 --> 00:03:00,310
>> Kami juga melacak
bagian atas tumpukan.

63
00:03:00,310 --> 00:03:04,350
Apa elemen yang paling
baru-baru ini ditambahkan ke stack?

64
00:03:04,350 --> 00:03:07,470
Dan jadi kami melacak yang
dalam variabel yang disebut atas.

65
00:03:07,470 --> 00:03:11,692
Dan semua ini akan dibungkus bersama-sama
menjadi tipe data baru yang disebut stack.

66
00:03:11,692 --> 00:03:13,400
Dan setelah kita buat
tipe data baru

67
00:03:13,400 --> 00:03:15,410
kita bisa memperlakukannya seperti
jenis data lainnya.

68
00:03:15,410 --> 00:03:20,970
Kita dapat mendeklarasikan tumpukan s, seperti
kita bisa melakukan int x, y atau arang.

69
00:03:20,970 --> 00:03:22,990
Dan ketika kita mengatakan tumpukan
s, baik apa yang terjadi

70
00:03:22,990 --> 00:03:26,420
adalah kita mendapatkan satu set
memori disisihkan bagi kita.

71
00:03:26,420 --> 00:03:28,770
>> Dalam kapasitas hal ini
Saya tampaknya telah memutuskan

72
00:03:28,770 --> 00:03:33,470
adalah 10 karena saya punya
variabel tunggal jenis tumpukan

73
00:03:33,470 --> 00:03:35,320
yang berisi dua bidang ingat.

74
00:03:35,320 --> 00:03:38,330
Array, dalam hal ini akan
menjadi sebuah array bilangan bulat

75
00:03:38,330 --> 00:03:40,440
seperti halnya di sebagian besar contoh saya.

76
00:03:40,440 --> 00:03:43,996
Dan variabel integer lain
mampu menyimpan atas,

77
00:03:43,996 --> 00:03:45,870
paling baru ditambahkan
elemen ke stack.

78
00:03:45,870 --> 00:03:50,290
Jadi satu tumpukan tunggal apa yang kita
hanya didefinisikan terlihat seperti ini.

79
00:03:50,290 --> 00:03:53,190
Ini sebuah kotak yang berisi
array 10 apa

80
00:03:53,190 --> 00:03:57,280
akan bilangan bulat dalam kasus ini dan
variabel lain bilangan bulat ada di green

81
00:03:57,280 --> 00:04:00,010
untuk menunjukkan bagian atas tumpukan.

82
00:04:00,010 --> 00:04:02,600
>> Untuk mengatur atas
tumpukan kita hanya mengatakan s.top.

83
00:04:02,600 --> 00:04:04,890
Itulah cara kita mengakses
bidang penarikan struktur.

84
00:04:04,890 --> 00:04:10,460
s.top sama dengan 0 efektif
melakukan hal ini untuk tumpukan kami.

85
00:04:10,460 --> 00:04:12,960
Jadi sekali lagi kita memiliki dua operasi
bahwa kita dapat melakukan sekarang.

86
00:04:12,960 --> 00:04:14,270
Kita dapat mendorong dan kita bisa pop.

87
00:04:14,270 --> 00:04:15,635
Mari kita mulai dengan push.

88
00:04:15,635 --> 00:04:18,260
Sekali lagi, mendorong adalah menambahkan baru
elemen ke atas tumpukan.

89
00:04:18,260 --> 00:04:21,460
>> Jadi apa yang perlu kita lakukan di
array ini pelaksanaan berdasarkan?

90
00:04:21,460 --> 00:04:23,210
Baik di umum
fungsi push akan

91
00:04:23,210 --> 00:04:26,160
perlu untuk menerima
pointer ke stack.

92
00:04:26,160 --> 00:04:28,610
Sekarang mengambil kedua dan berpikir tentang hal itu.

93
00:04:28,610 --> 00:04:32,840
Mengapa kita ingin menerima
pointer ke stack?

94
00:04:32,840 --> 00:04:36,830
Ingat dari video sebelumnya pada
lingkup variabel dan petunjuk,

95
00:04:36,830 --> 00:04:42,350
apa yang akan terjadi jika kita hanya mengirim
stack, s lebih dalam sebagai parameter?

96
00:04:42,350 --> 00:04:45,770
Apa yang sebenarnya akan berlalu di dalam sana?

97
00:04:45,770 --> 00:04:49,430
Ingat kita sedang menciptakan salinan
ketika kita lulus ke fungsi

98
00:04:49,430 --> 00:04:51,160
kecuali kita menggunakan pointer.

99
00:04:51,160 --> 00:04:55,380
Dan fungsi ini mendorong kebutuhan
untuk menerima pointer ke stack

100
00:04:55,380 --> 00:04:59,160
sehingga kita benar-benar mengubah
stack kami berniat untuk berubah.

101
00:04:59,160 --> 00:05:03,060
>> Push Hal lain mungkin ingin
menerima adalah elemen data jenis nilai.

102
00:05:03,060 --> 00:05:06,970
Dalam hal ini, sekali lagi, integer yang
kita akan menambah atas tumpukan.

103
00:05:06,970 --> 00:05:08,680
Jadi kita punya dua parameter kami.

104
00:05:08,680 --> 00:05:11,310
Apa yang akan kita
sekarang lakukan dalam mendorong?

105
00:05:11,310 --> 00:05:14,860
Nah, sederhana, kami hanya akan menambahkan
bahwa unsur ke atas tumpukan

106
00:05:14,860 --> 00:05:22,860
dan kemudian mengubah mana bagian atas
stack adalah, bahwa s dot nilai atas.

107
00:05:22,860 --> 00:05:25,639
Jadi ini adalah apa fungsi
deklarasi untuk push

108
00:05:25,639 --> 00:05:27,680
mungkin terlihat seperti dalam
-array berbasis implementasi.

109
00:05:27,680 --> 00:05:30,967
>> Sekali lagi ini bukan aturan keras dan cepat
Anda bisa mengubah ini dan memiliki

110
00:05:30,967 --> 00:05:32,050
itu bervariasi dalam cara yang berbeda.

111
00:05:32,050 --> 00:05:33,840
Mungkin s dinyatakan secara global.

112
00:05:33,840 --> 00:05:36,180
Dan sehingga Anda bahkan tidak perlu
untuk lulus itu sebagai parameter.

113
00:05:36,180 --> 00:05:39,125
Ini lagi hanya
kasus umum untuk push.

114
00:05:39,125 --> 00:05:41,000
Dan ada yang berbeda
cara untuk menerapkannya.

115
00:05:41,000 --> 00:05:42,810
Tapi dalam kasus ini kami
push akan mengambil

116
00:05:42,810 --> 00:05:48,540
dua argumen, pointer ke stack dan
elemen data nilai jenis, integer

117
00:05:48,540 --> 00:05:49,840
pada kasus ini.

118
00:05:49,840 --> 00:05:52,100
>> Jadi kami menyatakan, kami
kata s.top sama dengan 0.

119
00:05:52,100 --> 00:05:55,969
Sekarang mari kita mendorong
nomor 28 ke stack.

120
00:05:55,969 --> 00:05:57,010
Nah apa artinya?

121
00:05:57,010 --> 00:05:59,600
Nah saat ini
atas tumpukan adalah 0.

122
00:05:59,600 --> 00:06:01,350
Dan jadi apa dasarnya
akan terjadi adalah

123
00:06:01,350 --> 00:06:05,820
kita akan tetap nomor
28 ke dalam array lokasi 0.

124
00:06:05,820 --> 00:06:09,540
Cukup sederhana, tepat, yang
adalah atas dan sekarang kami baik untuk pergi.

125
00:06:09,540 --> 00:06:12,910
Dan kemudian kita perlu mengubah apa
bagian atas tumpukan akan.

126
00:06:12,910 --> 00:06:15,130
Sehingga waktu berikutnya
kami mendorong elemen di,

127
00:06:15,130 --> 00:06:18,017
kita akan menyimpannya dalam
Lokasi array, mungkin tidak 0.

128
00:06:18,017 --> 00:06:20,100
Kami tidak ingin menimpa
apa yang baru saja kita diletakkan di sana.

129
00:06:20,100 --> 00:06:23,510
Dan jadi kami hanya akan memindahkan atas ke 1.

130
00:06:23,510 --> 00:06:24,890
Itu mungkin masuk akal.

131
00:06:24,890 --> 00:06:28,940
>> Sekarang jika kita ingin menempatkan elemen lain
ke stack, mengatakan kami ingin mendorong 33,

132
00:06:28,940 --> 00:06:33,190
nah sekarang kita hanya akan mengambil 33
dan meletakkannya di nomor lokasi array yang

133
00:06:33,190 --> 00:06:37,580
1, dan kemudian mengubah atas kami
tumpukan menjadi berbagai lokasi nomor dua.

134
00:06:37,580 --> 00:06:40,650
Jadi jika lain kali kita ingin
mendorong elemen ke stack,

135
00:06:40,650 --> 00:06:43,087
itu akan dimasukkan dalam array lokasi 2.

136
00:06:43,087 --> 00:06:44,420
Dan mari kita melakukan itu sekali lagi.

137
00:06:44,420 --> 00:06:45,753
Kami akan mendorong 19 off dari tumpukan.

138
00:06:45,753 --> 00:06:48,940
Kami akan menempatkan 19 dalam array lokasi 2
dan mengubah atas tumpukan kami

139
00:06:48,940 --> 00:06:51,220
menjadi berbagai lokasi 3
jadi jika waktu kita selanjutnya

140
00:06:51,220 --> 00:06:54,780
perlu membuat dorongan kami baik untuk pergi.

141
00:06:54,780 --> 00:06:56,980
>> OK, jadi yang mendorong singkatnya.

142
00:06:56,980 --> 00:06:57,830
Bagaimana bermunculan?

143
00:06:57,830 --> 00:07:00,240
Jadi popping adalah semacam
mitra untuk mendorong.

144
00:07:00,240 --> 00:07:02,720
Ini bagaimana kita menghapus data dari stack.

145
00:07:02,720 --> 00:07:04,610
Dan dalam kebutuhan pop umum
untuk melakukan hal berikut.

146
00:07:04,610 --> 00:07:07,600
Ini perlu menerima pointer ke
tumpukan, lagi dalam kasus umum.

147
00:07:07,600 --> 00:07:10,480
Dalam beberapa kasus lain Anda mungkin
telah menyatakan stack global,

148
00:07:10,480 --> 00:07:13,910
dalam hal ini Anda tidak perlu lulus
di karena sudah memiliki akses ke sana

149
00:07:13,910 --> 00:07:15,541
sebagai variabel global.

150
00:07:15,541 --> 00:07:17,040
Tapi kemudian apa lagi yang perlu kita lakukan?

151
00:07:17,040 --> 00:07:21,000
Yah kami incrementing
bagian atas tumpukan di push,

152
00:07:21,000 --> 00:07:24,050
jadi kita mungkin akan ingin
untuk pengurangan atas tumpukan

153
00:07:24,050 --> 00:07:25,009
di pop, kan?

154
00:07:25,009 --> 00:07:26,800
Dan tentu saja
kami juga akan ingin

155
00:07:26,800 --> 00:07:29,240
untuk mengembalikan nilai yang kita keluarkan.

156
00:07:29,240 --> 00:07:32,125
Jika kita menambahkan elemen, kita ingin
untuk mendapatkan elemen keluar nanti,

157
00:07:32,125 --> 00:07:34,000
kita mungkin benar-benar
ingin menyimpannya sehingga kita

158
00:07:34,000 --> 00:07:36,490
tidak hanya menghapus mereka dari
stack dan kemudian melakukan apa-apa dengan mereka.

159
00:07:36,490 --> 00:07:38,500
Umumnya jika kita
mendorong dan muncul di sini

160
00:07:38,500 --> 00:07:41,250
kita ingin menyimpan ini
informasi dalam cara yang berarti

161
00:07:41,250 --> 00:07:43,250
dan sehingga tidak membuat
akal untuk hanya membuangnya.

162
00:07:43,250 --> 00:07:46,380
Jadi fungsi ini harus
mungkin mengembalikan nilai kepada kami.

163
00:07:46,380 --> 00:07:51,040
>> Jadi ini adalah apa deklarasi untuk pop
mungkin terlihat seperti ada di bagian kiri atas.

164
00:07:51,040 --> 00:07:53,870
Fungsi kembali ini
data jenis nilai.

165
00:07:53,870 --> 00:07:56,320
Sekali lagi kami sudah menggunakan
bilangan bulat seluruh.

166
00:07:56,320 --> 00:08:01,916
Dan ia menerima pointer ke stack sebagai
argumen sendiri atau parameter tunggal.

167
00:08:01,916 --> 00:08:03,040
Jadi apa yang pop akan lakukan?

168
00:08:03,040 --> 00:08:07,990
Katakanlah kita ingin sekarang
pop elemen off s.

169
00:08:07,990 --> 00:08:14,000
Jadi ingat saya mengatakan bahwa tumpukan yang lalu
, keluar pertama, LIFO struktur data.

170
00:08:14,000 --> 00:08:17,855
Yang elemen akan
dihapus dari stack?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Apakah Anda menebak 19?

173
00:08:24,150 --> 00:08:25,290
Karena Anda akan benar.

174
00:08:25,290 --> 00:08:28,836
19 adalah elemen terakhir kami ditambahkan ke
tumpukan ketika kami mendorong elemen pada,

175
00:08:28,836 --> 00:08:31,210
dan itu akan pertama
elemen yang akan dihapus.

176
00:08:31,210 --> 00:08:34,780
Seolah-olah kita mengatakan 28, dan
maka kita menempatkan 33 di atasnya,

177
00:08:34,780 --> 00:08:36,659
dan kami menempatkan 19 di atas itu.

178
00:08:36,659 --> 00:08:40,650
Satu-satunya elemen yang bisa kita ambil off 19.

179
00:08:40,650 --> 00:08:45,019
>> Sekarang dalam diagram di sini apa yang telah saya lakukan
adalah semacam dihapus 19 dari array.

180
00:08:45,019 --> 00:08:46,810
Itu tidak benar-benar
apa yang akan kita lakukan.

181
00:08:46,810 --> 00:08:48,934
Kami hanya akan jenis
dari berpura-pura itu tidak ada.

182
00:08:48,934 --> 00:08:51,441
Itu masih ada di
lokasi memori,

183
00:08:51,441 --> 00:08:54,190
tapi kami hanya akan mengabaikannya
dengan mengubah atas tumpukan kami

184
00:08:54,190 --> 00:08:56,080
dari menjadi 3-2.

185
00:08:56,080 --> 00:08:58,720
Jadi jika kita sekarang mendorong
elemen lain ke stack,

186
00:08:58,720 --> 00:09:00,720
itu lebih akan menulis 19.

187
00:09:00,720 --> 00:09:03,990
>> Tapi mari kita tidak pergi melalui kesulitan
menghapus 19 dari stack.

188
00:09:03,990 --> 00:09:05,830
Kami hanya bisa berpura-pura itu tidak ada.

189
00:09:05,830 --> 00:09:11,107
Untuk tujuan tumpukan itu hilang jika
kita mengubah atas menjadi 2 bukan 3.

190
00:09:11,107 --> 00:09:12,690
Baiklah, jadi itu cukup banyak itu.

191
00:09:12,690 --> 00:09:15,080
Itu semua yang perlu kita lakukan
pop elemen off.

192
00:09:15,080 --> 00:09:16,090
Mari kita melakukannya lagi.

193
00:09:16,090 --> 00:09:18,610
Jadi saya sudah disorot dalam warna merah di sini untuk
menunjukkan kita membuat panggilan lain.

194
00:09:18,610 --> 00:09:19,720
Kami akan melakukan hal yang sama.

195
00:09:19,720 --> 00:09:20,803
>> Jadi apa yang akan terjadi?

196
00:09:20,803 --> 00:09:23,670
Nah, kita akan menyimpan
33 di x dan kita akan

197
00:09:23,670 --> 00:09:26,217
untuk mengubah atas tumpukan untuk 1.

198
00:09:26,217 --> 00:09:29,050
Sehingga jika kita sekarang untuk mendorong sebuah
elemen ke stack yang kami

199
00:09:29,050 --> 00:09:31,610
akan lakukan sekarang,
apa yang akan terjadi

200
00:09:31,610 --> 00:09:36,367
adalah kita akan menimpa
Array lokasi nomor 1.

201
00:09:36,367 --> 00:09:38,950
Sehingga 33 yang semacam tersisa
balik bahwa kita hanya berpura-pura

202
00:09:38,950 --> 00:09:44,390
sudah tidak ada lagi, kita hanya akan
untuk mengalahkan itu dan menempatkan 40 di sana sebagai gantinya.

203
00:09:44,390 --> 00:09:46,290
Dan tentu saja,
karena kami membuat dorongan,

204
00:09:46,290 --> 00:09:48,780
kita akan kenaikan
atas tumpukan 1-2

205
00:09:48,780 --> 00:09:50,950
sehingga jika kita sekarang menambahkan
elemen lain itu akan

206
00:09:50,950 --> 00:09:54,700
pergi ke berbagai lokasi nomor dua.

207
00:09:54,700 --> 00:09:57,590
>> Sekarang daftar terkait yang lain
cara untuk menerapkan tumpukan.

208
00:09:57,590 --> 00:10:01,210
Dan jika definisi ini pada
Layar sini tampak akrab bagi Anda,

209
00:10:01,210 --> 00:10:04,260
itu karena terlihat hampir
persis sama, pada kenyataannya,

210
00:10:04,260 --> 00:10:07,790
itu cukup banyak adalah persis
sama seperti daftar tunggal terkait,

211
00:10:07,790 --> 00:10:11,990
jika Anda ingat dari diskusi kami
tunggal terkait daftar di video lain.

212
00:10:11,990 --> 00:10:15,510
Satu-satunya batasan di sini
adalah bagi kita sebagai programmer,

213
00:10:15,510 --> 00:10:17,900
kita tidak diperbolehkan untuk
memasukkan atau menghapus secara acak

214
00:10:17,900 --> 00:10:20,620
dari daftar sendiri-sendiri terkait
yang kita sebelumnya bisa melakukan.

215
00:10:20,620 --> 00:10:25,820
Hanya sekarang kita dapat menyisipkan dan menghapus dari
bagian depan atau bagian atas terkait

216
00:10:25,820 --> 00:10:26,320
daftar.

217
00:10:26,320 --> 00:10:28,028
Itu benar-benar satu-satunya
Perbedaan sekalipun.

218
00:10:28,028 --> 00:10:29,700
Ini adalah jika daftar tunggal terkait.

219
00:10:29,700 --> 00:10:32,060
Ini hanya pembatasan
mengganti pada diri kita sendiri

220
00:10:32,060 --> 00:10:35,770
sebagai programmer yang
perubahan ke stack.

221
00:10:35,770 --> 00:10:39,280
>> Aturan di sini adalah untuk selalu menjaga
pointer ke kepala linked list.

222
00:10:39,280 --> 00:10:41,520
Hal ini tentu saja umumnya
aturan penting pertama.

223
00:10:41,520 --> 00:10:44,260
Untuk tunggal linked list tetap Anda
hanya perlu pointer ke kepala

224
00:10:44,260 --> 00:10:46,160
dalam rangka untuk memiliki
rantai dapat merujuk

225
00:10:46,160 --> 00:10:48,596
untuk setiap elemen lain
dalam linked list.

226
00:10:48,596 --> 00:10:50,470
Tapi itu sangat
penting dengan stack.

227
00:10:50,470 --> 00:10:52,386
Dan umumnya Anda
akan benar-benar ingin

228
00:10:52,386 --> 00:10:54,090
pointer ini menjadi variabel global.

229
00:10:54,090 --> 00:10:56,574
Ini mungkin akan
menjadi lebih mudah seperti itu.

230
00:10:56,574 --> 00:10:58,240
Jadi apa yang analog push dan pop?

231
00:10:58,240 --> 00:10:58,740
Benar.

232
00:10:58,740 --> 00:11:01,812
Jadi mendorong lagi adalah menambahkan
elemen baru ke stack.

233
00:11:01,812 --> 00:11:03,770
Dalam daftar link yang
berarti kita akan memiliki

234
00:11:03,770 --> 00:11:07,770
untuk membuat node baru yang kami
akan menambahkan ke dalam daftar link,

235
00:11:07,770 --> 00:11:10,500
dan kemudian ikuti langkah-langkah hati-hati
yang telah diuraikan sebelumnya kami

236
00:11:10,500 --> 00:11:16,050
dalam daftar sendiri-sendiri terkait dengan menambahkannya ke
rantai tanpa melanggar rantai

237
00:11:16,050 --> 00:11:18,900
dan kehilangan atau orphaning setiap
elemen dari linked list.

238
00:11:18,900 --> 00:11:21,820
Dan itu pada dasarnya apa yang
sedikit gumpalan teks ada merangkum.

239
00:11:21,820 --> 00:11:23,740
Dan mari kita lihat
itu sebagai sebuah diagram.

240
00:11:23,740 --> 00:11:24,823
>> Jadi, inilah daftar link kami.

241
00:11:24,823 --> 00:11:26,620
Ini bersamaan berisi empat elemen.

242
00:11:26,620 --> 00:11:30,420
Dan lebih sempurna inilah kami
tumpukan mengandung empat unsur.

243
00:11:30,420 --> 00:11:36,030
Dan katakanlah kita sekarang ingin
mendorong item baru ke stack ini.

244
00:11:36,030 --> 00:11:39,792
Dan kami ingin mendorong baru
Item yang nilainya data 12.

245
00:11:39,792 --> 00:11:41,000
Nah apa yang akan kita lakukan?

246
00:11:41,000 --> 00:11:43,420
Yah pertama kita akan
ruang malloc, dinamis

247
00:11:43,420 --> 00:11:45,411
mengalokasikan ruang untuk node baru.

248
00:11:45,411 --> 00:11:48,160
Dan tentu saja segera setelah
kami membuat panggilan ke malloc kami selalu

249
00:11:48,160 --> 00:11:52,989
pastikan untuk memeriksa null,
karena jika kita punya nol kembali

250
00:11:52,989 --> 00:11:54,280
ada semacam masalah.

251
00:11:54,280 --> 00:11:57,570
Kami tidak ingin dereference nol bahwa
pointer atau Anda akan menderita kesalahan seg.

252
00:11:57,570 --> 00:11:58,510
Itu tidak baik.

253
00:11:58,510 --> 00:11:59,760
Jadi kita sudah malloced dari node.

254
00:11:59,760 --> 00:12:01,260
Kami akan menganggap kita sudah sukses di sini.

255
00:12:01,260 --> 00:12:06,090
Kita akan dimasukkan ke dalam 12
bidang data simpul tersebut.

256
00:12:06,090 --> 00:12:11,570
Sekarang Anda ingat yang pointer kami
bergerak berikutnya sehingga kita tidak memutuskan rantai?

257
00:12:11,570 --> 00:12:15,100
Kami memiliki beberapa pilihan di sini tapi
satu-satunya yang akan menjadi aman

258
00:12:15,100 --> 00:12:19,330
adalah untuk mengatur berita pointer di sebelah
arahkan ke kepala lama daftar

259
00:12:19,330 --> 00:12:21,360
atau apa yang akan segera menjadi
Kepala lama daftar.

260
00:12:21,360 --> 00:12:23,610
Dan sekarang bahwa semua kita
elemen dirantai bersama-sama,

261
00:12:23,610 --> 00:12:27,370
kita hanya dapat memindahkan daftar ke titik
ke tempat yang sama yang melakukan baru.

262
00:12:27,370 --> 00:12:33,550
Dan kita sekarang secara efektif mendorong
elemen baru ke depan tumpukan.

263
00:12:33,550 --> 00:12:36,420
>> Pop kita hanya ingin
menghapus elemen pertama.

264
00:12:36,420 --> 00:12:38,150
Dan pada dasarnya apa
yang harus kita lakukan di sini,

265
00:12:38,150 --> 00:12:40,050
baik kita harus menemukan elemen kedua.

266
00:12:40,050 --> 00:12:43,540
Akhirnya yang akan menjadi baru
kepala setelah kami hapus yang pertama.

267
00:12:43,540 --> 00:12:47,300
Jadi kita hanya perlu mulai dari
awalnya, bergerak maju satu.

268
00:12:47,300 --> 00:12:50,340
Setelah kita punya pegangan pada satu
maju dari mana kita saat ini

269
00:12:50,340 --> 00:12:53,850
kita dapat menghapus yang pertama aman
dan kemudian kita bisa bergerak kepala

270
00:12:53,850 --> 00:12:57,150
untuk menunjuk ke apa adalah
jabatan kedua dan kemudian sekarang

271
00:12:57,150 --> 00:12:59,170
adalah yang pertama setelah itu
simpul telah dihapus.

272
00:12:59,170 --> 00:13:01,160
>> Jadi sekali lagi, mengambil melihat
itu sebagai sebuah diagram kita

273
00:13:01,160 --> 00:13:05,022
ingin sekarang pop
Unsur off dari tumpukan ini.

274
00:13:05,022 --> 00:13:05,730
Jadi apa yang kita lakukan?

275
00:13:05,730 --> 00:13:08,188
Yah kita pertama akan menciptakan
pointer baru yang akan

276
00:13:08,188 --> 00:13:10,940
untuk menunjuk ke tempat yang sama sebagai kepala.

277
00:13:10,940 --> 00:13:13,790
Kami akan memindahkannya satu posisi
maju dengan mengatakan equals trav

278
00:13:13,790 --> 00:13:17,510
trav berikutnya misalnya, yang
akan memajukan satu trav pointer

279
00:13:17,510 --> 00:13:19,324
posisi depan.

280
00:13:19,324 --> 00:13:21,240
Sekarang kita punya
berpegang pada elemen pertama

281
00:13:21,240 --> 00:13:24,573
melalui pointer disebut daftar, dan
Elemen kedua melalui pointer disebut

282
00:13:24,573 --> 00:13:28,692
trav, kita dapat menghapus yang
elemen pertama dari stack

283
00:13:28,692 --> 00:13:30,650
tanpa kehilangan sisanya
rantai karena kita

284
00:13:30,650 --> 00:13:32,358
memiliki cara untuk merujuk
untuk elemen kedua

285
00:13:32,358 --> 00:13:34,780
meneruskan dengan cara dari
pointer disebut trav.

286
00:13:34,780 --> 00:13:37,100
>> Jadi sekarang kita bisa membebaskan simpul tersebut.

287
00:13:37,100 --> 00:13:38,404
Kita bisa membebaskan daftar.

288
00:13:38,404 --> 00:13:41,320
Dan kemudian semua yang perlu kita lakukan sekarang adalah
memindahkan daftar ke titik ke tempat yang sama

289
00:13:41,320 --> 00:13:44,482
trav yang tidak, dan kami semacam kembali
di mana kita mulai sebelum kita mendorong 12

290
00:13:44,482 --> 00:13:45,690
pada di tempat pertama, tepat.

291
00:13:45,690 --> 00:13:46,940
Ini adalah persis di mana kita berada.

292
00:13:46,940 --> 00:13:48,840
Kami memiliki empat elemen ini stack.

293
00:13:48,840 --> 00:13:49,690
Kami menambahkan gol kelima.

294
00:13:49,690 --> 00:13:51,910
Kami mendorong kelima
elemen, dan kemudian kita

295
00:13:51,910 --> 00:13:55,980
muncul yang paling baru
menambahkan elemen mundur.

296
00:13:55,980 --> 00:13:58,816
>> Itu benar-benar cukup banyak
semua yang ada untuk tumpukan.

297
00:13:58,816 --> 00:14:00,190
Anda dapat menerapkannya sebagai array.

298
00:14:00,190 --> 00:14:01,815
Anda dapat menerapkan mereka sebagai daftar terkait.

299
00:14:01,815 --> 00:14:04,810
Ada, tentu saja, lainnya
cara untuk menerapkan mereka juga.

300
00:14:04,810 --> 00:14:09,060
Pada dasarnya alasan kita akan menggunakan
tumpukan adalah untuk memelihara data sedemikian rupa

301
00:14:09,060 --> 00:14:12,090
yang paling baru ditambahkan
Unsur adalah hal pertama yang kami

302
00:14:12,090 --> 00:14:14,980
akan ingin untuk kembali.

303
00:14:14,980 --> 00:14:17,900
Aku Doug Lloyd, ini CS50.

304
00:14:17,900 --> 00:14:19,926