1
00:00:04,074 --> 00:00:07,258
DUGSDAGS LOIDS: Labi, tāpēctātad
šajā brīdī jūs, iespējams, jau labi 

2
00:00:07,258 --> 00:00:10,442
pārzināt masīvus un saistītos
sarakstus, kas ir divas primārās datu 

3
00:00:10,442 --> 00:00:13,626
struktūras, par kurām mēs runājām,
lai sakārtotu līdzīga veida datu 

4
00:00:13,626 --> 00:00:16,810
kopas. 

5
00:00:16,810 --> 00:00:20,330
 Tagad mēs runāsim par pāris masīvu
un saistīto sarakstu variācijām.

6
00:00:20,330 --> 00:00:22,362
Šajā video mēs runāsim par
skursteņiemstekiem.

7
00:00:22,362 --> 00:00:25,320
Konkrēti, mēs runāsim par datu
struktūru, ko sauc par steku.

8
00:00:25,320 --> 00:00:28,456
AtgādinietAtcerieties no
iepriekšējām diskusijām par rādītājiem un 

9
00:00:28,456 --> 00:00:31,592
atmiņu, ka kaudzesteks ir arī
nosaukums atmiņas segmentam, kurā 

10
00:00:31,592 --> 00:00:34,728
statiski deklarēta atmiņa — jūsu
nosauktā atmiņa, jūsu nosauktie 

11
00:00:34,728 --> 00:00:37,864
mainīgie utt., un funkciju rāmji,
kurus mēs arī saucam par steka 

12
00:00:37,864 --> 00:00:41,000
kadriem/rāmjiem/ietvariem. 

13
00:00:41,000 --> 00:00:45,421
Tātad šī ir steka datu struktūra,
nevis atmiņas steka segments.

14
00:00:45,421 --> 00:00:45,920
Labi.

15
00:00:45,920 --> 00:00:46,890
 Bet kas ir kaudzesteks?

16
00:00:46,890 --> 00:00:49,040
Tātad tā ir gandrīz tikai īpaša
veida struktūra, kas organizētā veidā 

17
00:00:49,040 --> 00:00:51,190
uztur datus. 

18
00:00:51,190 --> 00:00:55,765
Un ir divi ļoti izplatīti veidi, kā
ieviest stekus, izmantojot divas 

19
00:00:55,765 --> 00:01:00,340
mums jau zināmas datu struktūras —
masīvus un saistītos sarakstus. 

20
00:01:00,340 --> 00:01:04,270
Tas, kas padara steku īpašu, ir
veids, kā mēs ievietojam informāciju 

21
00:01:04,270 --> 00:01:08,200
stekā, un veids, kā mēs noņemam
informāciju no steka. 

22
00:01:08,200 --> 00:01:12,015
Jo īpaši ar skursteņiemAttiecībā uz
stekiem noteikums ir tāds, ka var 

23
00:01:12,015 --> 00:01:15,830
noņemt tikai pēdējo pievienoto
elementu. 

24
00:01:15,830 --> 00:01:17,660
 Tāpēc domājiet par to tā, it kā
tas būtu kaudzesteks.

25
00:01:17,660 --> 00:01:20,965
Mēs sakrājam informāciju sev
virsūvienu uz otras, un var noņemt tikai 

26
00:01:20,965 --> 00:01:24,271
to, kas atrodas kaudzessteka
augšpusē. 

27
00:01:24,271 --> 00:01:26,145
Mēs nevaram noņemt apakšā esošo
lietu, jo viss pārējais sabruktu un 

28
00:01:26,145 --> 00:01:28,020
apgāztos. 

29
00:01:28,020 --> 00:01:30,300
Tātad mēs patiešām veidojam
kaudzisteku, kas mums pēc tam ir jāizņem 

30
00:01:30,300 --> 00:01:32,580
pa gabalufragmentam. 

31
00:01:32,580 --> 00:01:35,760
Šī iemesla dēļ mēs parasti saucam
par steku kāsteku par LIFO 

32
00:01:35,760 --> 00:01:38,940
struktūru, pēdējais iekšā, pirmais
ārā. 

33
00:01:38,940 --> 00:01:42,290
LIFO, pēdējais iekšā, pirmais ārā.

34
00:01:42,290 --> 00:01:45,685
Tāpēc šī ierobežojuma dēļ, kā
informāciju var pievienot stekam un 

35
00:01:45,685 --> 00:01:49,080
izņemt no tāstā, ar steku mēs varam
darīt tikai divas lietas. 

36
00:01:49,080 --> 00:01:52,756
Mēs varam pushpush, ko mēs
lietojam, lai pievienotu jaunu elementu 

37
00:01:52,756 --> 00:01:56,433
steka augšpusē, vai arī, ja
stekasteks nepastāv un mēs to veidojam no 

38
00:01:56,433 --> 00:02:00,110
nulles, steka izveide vispirms būtu
stumšanaievietošana. 

39
00:02:00,110 --> 00:02:04,220
Un tad pop, tāds ir CS termins, ko
mēs izmantojam, lai noņemtu pēdējo 

40
00:02:04,220 --> 00:02:08,330
pievienoto elementu no steka
augšdaļas. 

41
00:02:08,330 --> 00:02:10,725
Tāpēc mēs apskatīsim abas
ieviešanas — gan uz masīvu, gan uz saistīto 

42
00:02:10,725 --> 00:02:13,120
sarakstu bāzes. 

43
00:02:13,120 --> 00:02:14,870
Un mēs sāksim ar masīvu bāzesbāzi.

44
00:02:14,870 --> 00:02:18,005
Tātad, lūk, pamatideja par to, kā
izskatītos uz masīvu balstīta steka 

45
00:02:18,005 --> 00:02:21,140
datu struktūra. 

46
00:02:21,140 --> 00:02:23,740
Šeit mums ir drukāta definīcija.

47
00:02:23,740 --> 00:02:27,790
Tajā mums ir divi struktūras
locekļielementi vai lauki.

48
00:02:27,790 --> 00:02:29,880
Mums ir masīvs.

49
00:02:29,880 --> 00:02:32,400
Un atkal es izmantoju patvaļīgu
datu tipa vērtību.

50
00:02:32,400 --> 00:02:34,740
Tātad tas varētu būt jebkurš datu
tips, int char vai kāds cits datu 

51
00:02:34,740 --> 00:02:37,080
tips, ko iepriekš izveidojāt. 

52
00:02:37,080 --> 00:02:39,861
Tātad mums ir dažādu izmēru
jaudasizmēra ietilpības masīvs.

53
00:02:39,861 --> 00:02:41,935
JaudaIetilpība ir
mārciņajaucējzīmes noteikta konstante, iespējams, 

54
00:02:41,935 --> 00:02:44,010
kaut kur citur mūsu failā. 

55
00:02:44,010 --> 00:02:46,870
Tāpēc ņemiet vērā, ka jau ar šo
konkrēto ieviešanu mēs ierobežojam 

56
00:02:46,870 --> 00:02:49,730
sevi, kā tas parasti notika ar
masīviem, kuru izmērus nevaram 

57
00:02:49,730 --> 00:02:52,590
dinamiski mainīt, kur ir noteikts
maksimālais elementu skaits, ko 

58
00:02:52,590 --> 00:02:55,450
varam ievietot savā kaudzēstekā. 

59
00:02:55,450 --> 00:02:57,930
Šajā gadījumā tie ir
jaudasietilpības elementi.

60
00:02:57,930 --> 00:03:00,310
 Mēs arī sekojam līdzi kaudzessteka
augšdaļai.

61
00:03:00,310 --> 00:03:04,350
Kurš elements ir pēdējo
reizipēdējais, kas pievienots stekam?

62
00:03:04,350 --> 00:03:07,470
Un tāpēc mēs tam sekojam līdzi
mainīgajā, ko sauc par top.

63
00:03:07,470 --> 00:03:11,692
Un tas viss tiek apvienots jaunā
datu tipā, ko sauc par kaudzisteku.

64
00:03:11,692 --> 00:03:13,551
Kad esam izveidojuši šo jauno datu
tipu, mēs varam to apstrādāt tāpat 

65
00:03:13,551 --> 00:03:15,410
kā jebkuru citu datu tipu. 

66
00:03:15,410 --> 00:03:18,190
Mēs varam deklarēt kaudzistack s,
tāpat kā mēs varētu darīt ar int x 

67
00:03:18,190 --> 00:03:20,970
vai char y. 

68
00:03:20,970 --> 00:03:23,695
Un, kad mēs sakām kaudzestack s,
tad notiek tā, ka mēs iegūstam 

69
00:03:23,695 --> 00:03:26,420
atmiņas kopu, kas mums ir
paredzēta. 

70
00:03:26,420 --> 00:03:29,386
Šajā gadījumā es acīmredzot esmu
nolēmis, ka ietilpība ir 10, jo man 

71
00:03:29,386 --> 00:03:32,353
ir viens steka tipa mainīgais, kas
satur divus laukusdivu lauku 

72
00:03:32,353 --> 00:03:35,320
atsaukšanu. 

73
00:03:35,320 --> 00:03:37,880
Masīvs, šajā gadījumā būs veselu
skaitļu masīvs, kā tas ir lielākajā 

74
00:03:37,880 --> 00:03:40,440
daļā manu piemēru. 

75
00:03:40,440 --> 00:03:43,155
Un vēl viens veselsvesela skaitļa
mainīgais, kas spēj saglabāt 

76
00:03:43,155 --> 00:03:45,870
augšējo daļu, kas ir pēdējais
pievienotais elements kaudzīteistekam. 

77
00:03:45,870 --> 00:03:48,080
Tātad viena mūsu tikko definētā
kaudzeviens mūsu tikko definētais 

78
00:03:48,080 --> 00:03:50,290
steks izskatās šādi. 

79
00:03:50,290 --> 00:03:53,530
Tas ir lodziņš, kurā ir 10 masīvs,
kas šajā gadījumā būs veseli 

80
00:03:53,530 --> 00:03:56,770
skaitļi, un vēl viens veselsvesela
skaitļa mainīgais zaļā krāsā, lai 

81
00:03:56,770 --> 00:04:00,010
norādītu kaudzessteka augšdaļu. 

82
00:04:00,010 --> 00:04:02,600
 Lai iestatītu kaudzessteka
augšdaļu, mēs vienkārši sakām s.top.

83
00:04:02,600 --> 00:04:04,890
Tādā veidā mēs piekļūstam
struktūras atsaukšanas laukam.

84
00:04:04,890 --> 00:04:10,460
s.top ir vienāds arequals 0
efektīvi to dara mūsu kaudzeistekā.

85
00:04:10,460 --> 00:04:12,960
Tātad atkal mums ir divas darbības,
kuras mēs varam veikt tagad.

86
00:04:12,960 --> 00:04:14,270
Mēs varam spiestpush un mēs varam
poppop.

87
00:04:14,270 --> 00:04:15,635
Sāksim ar grūdienuievietošanu.

88
00:04:15,635 --> 00:04:16,947
Atkal stumšanaievietošana ir jauna
elementa pievienošana kaudzessteka 

89
00:04:16,947 --> 00:04:18,260
augšdaļai. 

90
00:04:18,260 --> 00:04:21,460
 Tātad, kas mums jādara šajā masīva
īstenošanā?

91
00:04:21,460 --> 00:04:26,160
Kopumā push funkcijaifunction būs
jāpieņem rādītājs uz steku.

92
00:04:26,160 --> 00:04:28,610
Tagad nedaudz padomājiet par to.

93
00:04:28,610 --> 00:04:32,840
Kāpēc mēs vēlamies pieņemt rādītāju
uz steku?

94
00:04:32,840 --> 00:04:36,010
AtgādinātAtcerieties no
iepriekšējiem videoklipiem par mainīgo 

95
00:04:36,010 --> 00:04:39,180
tvērumu un norādēm, kas notiktu, ja
mēs vienkārši nosūtītu steku, s 

96
00:04:39,180 --> 00:04:42,350
drīzāk kā parametru? 

97
00:04:42,350 --> 00:04:45,770
Kas tur īsti tiktu nodots?

98
00:04:45,770 --> 00:04:48,465
Atcerieties, ka mēs veidojam
kopiju, kad to nododam funkcijai, ja 

99
00:04:48,465 --> 00:04:51,160
vien neizmantojam norādesrādītājus.


100
00:04:51,160 --> 00:04:55,160
Un tāpēc šai funkcijai ir jāpieņem
rādītājs uz steku, lai mēs 

101
00:04:55,160 --> 00:04:59,160
faktiski mainītu steku, kuru
plānojam mainīt. 

102
00:04:59,160 --> 00:05:01,110
Otra lieta, ko pushpush, iespējams,
vēlas pieņemt, ir datu elements 

103
00:05:01,110 --> 00:05:03,060
ar tipa vērtību. 

104
00:05:03,060 --> 00:05:05,015
Šajā gadījumā atkal vesels
skaitlis, ko mēs pievienosim kaudzessteka 

105
00:05:05,015 --> 00:05:06,970
augšdaļai. 

106
00:05:06,970 --> 00:05:08,680
Tātad mums ir divi parametri.

107
00:05:08,680 --> 00:05:11,310
Ko mēs tagad darīsim
grūdienaievietošanas iekšpusē?

108
00:05:11,310 --> 00:05:15,160
VienkāršiNu, mēs vienkārši
pievienosim šo elementu kaudzessteka 

109
00:05:15,160 --> 00:05:19,010
augšdaļai un pēc tam mainīsim to,
kur atrodas kaudzessteka augšdaļa, 

110
00:05:19,010 --> 00:05:22,860
šī punktveidas dot top
vērtībavērtību. 

111
00:05:22,860 --> 00:05:25,270
Tātad šādi varētu izskatīties
funkcijas deklarācija push uz masīvu 

112
00:05:25,270 --> 00:05:27,680
balstītā
implementācijāimplementēšanā. 

113
00:05:27,680 --> 00:05:29,865
Atkal šis nav stingrs noteikums, ka
varat toko varētu mainīt un 

114
00:05:29,865 --> 00:05:32,050
mainītkas atšķirtos dažādos veidos.


115
00:05:32,050 --> 00:05:33,840
Varbūt s ir deklarēts globāli.

116
00:05:33,840 --> 00:05:36,180
Un tāpēc jums pat nav nepieciešams
to nokārtotnodot kā parametru.

117
00:05:36,180 --> 00:05:39,125
Šis atkal ir tikai vispārējs
grūdienapush gadījums.

118
00:05:39,125 --> 00:05:41,000
Un ir dažādi veidi, kā to īstenot.

119
00:05:41,000 --> 00:05:43,946
Bet šajā gadījumā mūsu pushpush
izmantos divus argumentus, rādītāju 

120
00:05:43,946 --> 00:05:46,893
uz steku un datu elementu ar tipa
vērtību, šajā gadījumā vesels 

121
00:05:46,893 --> 00:05:49,840
skaitlisveselu skaitli. 

122
00:05:49,840 --> 00:05:52,100
 Tātad mēs deklarējām s, mēs
teicām, ka s.top ir vienāds arequals 0.

123
00:05:52,100 --> 00:05:55,969
Tagad uzspiedīsim uz kaudzes
numuruievietosim stekā skaitli 28.

124
00:05:55,969 --> 00:05:57,010
Nu, ko tas nozīmē?

125
00:05:57,010 --> 00:05:59,600
Šobrīd steka augšdaļa ir 0.

126
00:05:59,600 --> 00:06:02,710
Tātad būtībā notiks tas, ka mēs
ielīmēsimievietosim skaitli 28 masīva 

127
00:06:02,710 --> 00:06:05,820
vietā 0. 

128
00:06:05,820 --> 00:06:07,680
Diezgan vienkārši, labi, tā bija
virsotneaugšdaļa, un tagad mēs varam 

129
00:06:07,680 --> 00:06:09,540
iet. 

130
00:06:09,540 --> 00:06:12,910
Un tad mums ir jāmaina, kāda būs
kaudzessteka augšdaļa.

131
00:06:12,910 --> 00:06:15,463
Lai nākamreiz, kad ievietosim
elementu, mēs to saglabāsim masīva 

132
00:06:15,463 --> 00:06:18,017
vietā, iespējams, nevisvisticamāk,
ne 0. 

133
00:06:18,017 --> 00:06:20,100
Mēs nevēlamies pārrakstīt to, ko
tikko ievietojām.

134
00:06:20,100 --> 00:06:23,510
Tāpēc mēs tikai pārvietosim
augšdaļu uz 1.

135
00:06:23,510 --> 00:06:24,890
TasTam droši vien ir jēga.

136
00:06:24,890 --> 00:06:27,428
Tagad, ja mēs vēlamies ievietot
kaudzēstekā vēl vienu elementu, 

137
00:06:27,428 --> 00:06:29,966
sakiet, kateiksim, mēs vēlamies
nospiestievietot 33, tagad mēs 

138
00:06:29,966 --> 00:06:32,504
vienkārši paņemsim 33 un ievietosim
to masīva vietā ar numuru 1 un 

139
00:06:32,504 --> 00:06:35,042
pēc tam mainīsim steka augšdaļu uz
masīva atrašanās vietu. numur 

140
00:06:35,042 --> 00:06:37,580
divi. 

141
00:06:37,580 --> 00:06:40,333
Tātad, ja nākamreiz mēs vēlamies
ievietot elementu stekā, tas tiks 

142
00:06:40,333 --> 00:06:43,087
ievietots masīva 2. vietā 2. 

143
00:06:43,087 --> 00:06:44,420
Un darīsim to vēl vienu reizi.

144
00:06:44,420 --> 00:06:45,753
Mēs izspiedīsimizņemsim 19 no
skursteņiemstekiem.

145
00:06:45,753 --> 00:06:48,762
Mēs ievietosim 19. masīva
2. vietā19 masīva vietā 2 un mainīsim mūsu 

146
00:06:48,762 --> 00:06:51,771
kaudzessteka augšdaļu uz 3. masīva
atrašanās vietu 3, tāpēc, ja 

147
00:06:51,771 --> 00:06:54,780
nākamreiz mums būs jāveic
grūdiensievietošana, mēs esam gatavi. 

148
00:06:54,780 --> 00:06:56,980
 Labi, tātad tā ir ievietošana
īsumā.

149
00:06:56,980 --> 00:06:57,830
Kā ar poppingpopping?

150
00:06:57,830 --> 00:06:59,035
Tātad poppingizņemšana ir sava
veida līdzinieks 

151
00:06:59,035 --> 00:07:00,240
grūstīšanaiievietošanai. 

152
00:07:00,240 --> 00:07:02,720
Tādā veidā mēs noņemam datus no
steka.

153
00:07:02,720 --> 00:07:04,610
Un vispār poppop ir jādara šādi.

154
00:07:04,610 --> 00:07:07,600
Tai ir jāpieņem rādītājs uz steku,
atkal vispārīgā gadījumā.

155
00:07:07,600 --> 00:07:10,247
Citā gadījumā jūs, iespējams, esat
deklarējis steku globāli, un tādā 

156
00:07:10,247 --> 00:07:12,894
gadījumā jums tas nav jānodod, jo
tai jau ir piekļuve kā globālajam 

157
00:07:12,894 --> 00:07:15,541
mainīgajam. 

158
00:07:15,541 --> 00:07:17,040
Bet kas tad vēl mums jādara?

159
00:07:17,040 --> 00:07:19,696
Mēs palielinājām steka augšdaļu
stumšanaspush režīmā, tāpēc mēs, 

160
00:07:19,696 --> 00:07:22,352
iespējams, vēlēsimies samazināt
steka augšējo daļu poppop 

161
00:07:22,352 --> 00:07:25,009
spēlērežīmā, vai ne? 

162
00:07:25,009 --> 00:07:29,240
Un tad, protams, mēs arī vēlēsimies
atgriezt noņemto vērtību.

163
00:07:29,240 --> 00:07:31,656
Ja mēs pievienojam elementus, mēs
vēlamies tos iegūt vēlāk, mēs, 

164
00:07:31,656 --> 00:07:34,073
iespējams, vēlamies tos saglabāt,
lai mēs vienkārši neizdzēstu tos no 

165
00:07:34,073 --> 00:07:36,490
steka un pēc tam ar tiem neko
nedarītu. 

166
00:07:36,490 --> 00:07:38,743
Parasti, ja mēs šeit spiežam un
uzspiežamizmantojam pushing un 

167
00:07:38,743 --> 00:07:40,996
popping, mēs vēlamies šo
informāciju glabāt jēgpilnā veidā, tāpēc nav 

168
00:07:40,996 --> 00:07:43,250
jēgas to vienkārši izmest. 

169
00:07:43,250 --> 00:07:46,380
Tāpēc šai funkcijai, iespējams,
mums vajadzētu atgriezt vērtību.

170
00:07:46,380 --> 00:07:48,710
Tātad šādi varētu izskatīties
popmūzikaspop deklarācija augšējā 

171
00:07:48,710 --> 00:07:51,040
kreisajā stūrī. 

172
00:07:51,040 --> 00:07:53,870
Šī funkcija atgriež datus ar tipa
vērtību.

173
00:07:53,870 --> 00:07:56,320
Mēs atkal esam izmantojuši veselus
skaitļus.

174
00:07:56,320 --> 00:07:59,118
Un tas pieņem rādītāju uz steku kā
vienīgo argumentu vai vienīgo 

175
00:07:59,118 --> 00:08:01,916
parametru. 

176
00:08:01,916 --> 00:08:03,040
Ko tad popspop darīs?

177
00:08:03,040 --> 00:08:07,990
Pieņemsim, ka tagad vēlamies
izceltizņemt elementu no s.

178
00:08:07,990 --> 00:08:10,995
Tāpēc atcerieties, ka es teicu, ka
steki ir pēdējie iekšā, pirmie 

179
00:08:10,995 --> 00:08:14,000
ārā, LIFO datu struktūras. 

180
00:08:14,000 --> 00:08:17,855
Kurš elements tiks noņemts no
kaudzessteka?

181
00:08:21,780 --> 00:08:24,150
Vai tu uzminējiuzminējāt 19?

182
00:08:24,150 --> 00:08:25,290
Jo tevjums būtu taisnība.

183
00:08:25,290 --> 00:08:27,263
19 bija pēdējais elements, ko
pievienojām skursteistekam, kad 

184
00:08:27,263 --> 00:08:29,236
uzspiežāmpievienojām elementus, un
tādējādi tas attiecas uz pirmo 

185
00:08:29,236 --> 00:08:31,210
elementu, kas tiek noņemts. 

186
00:08:31,210 --> 00:08:33,934
Tas ir tā, it kā mēs teicām 28, un
tad mēs tam uzlikām 33 uz tā, un 

187
00:08:33,934 --> 00:08:36,659
mēs uzliekam 19 uz tā. 

188
00:08:36,659 --> 00:08:40,650
Vienīgais elements, ko varam
paceltiesnoņemt, ir 19.

189
00:08:40,650 --> 00:08:42,834
Tagad šajā diagrammā tas, ko esmu
izdarījis, ir it kā izdzēsts 19 no 

190
00:08:42,834 --> 00:08:45,019
masīva. 

191
00:08:45,019 --> 00:08:46,810
Tas patiesībā nav tas, ko mēs
darīsim.

192
00:08:46,810 --> 00:08:48,934
Mēs tikai izliksimies, ka tā tur
nav.

193
00:08:48,934 --> 00:08:52,507
Tas joprojām atrodas šajā atmiņas
vietā, taču mēs to vienkārši to 

194
00:08:52,507 --> 00:08:56,080
ignorēsim, mainot mūsu kaudzessteka
augšdaļu no 3 uz 2. 

195
00:08:56,080 --> 00:08:58,400
Tātad, ja mēs tagad ievietotu citu
elementu kaudzēstekā, tas 

196
00:08:58,400 --> 00:09:00,720
pārrakstītu 19. 

197
00:09:00,720 --> 00:09:03,990
 Bet nepiedzīvosim problēmas ar 19
dzēšanu no steka.

198
00:09:03,990 --> 00:09:05,830
Mēs varam izlikties, ka tā tur nav.

199
00:09:05,830 --> 00:09:08,468
KaudzītesSteka vajadzībām tas vairs
nebūs, ja augšējo daļu mainām uz 

200
00:09:08,468 --> 00:09:11,107
2, nevis 3. 

201
00:09:11,107 --> 00:09:12,690
Labi, tātad gandrīz viss tas bija
gandrīz viss.

202
00:09:12,690 --> 00:09:15,080
Tas ir viss, kas mums jādara, lai
noņemtu kādu elementu.

203
00:09:15,080 --> 00:09:16,090
Darīsim to vēlreiz.

204
00:09:16,090 --> 00:09:17,350
Tāpēc šeit esmu to iezīmējis
sarkanā krāsā, lai norādītu, ka mēs 

205
00:09:17,350 --> 00:09:18,610
veicam vēl vienu zvanuizsaukumu. 

206
00:09:18,610 --> 00:09:19,720
Mēs darīsim to pašu.

207
00:09:19,720 --> 00:09:20,803
 Kas tad notiks?

208
00:09:20,803 --> 00:09:26,217
Nu, mēs saglabāsim 33 x un mainīsim
kaudzessteka augšdaļu uz 1.

209
00:09:26,217 --> 00:09:29,600
Tātad, ja mēs tagad ievietosim
elementu kaudzēstekā, tas, ko mēs 

210
00:09:29,600 --> 00:09:32,983
tūlīt darīsim, mēs pārrakstīsim
masīva atrašanās vietas 

211
00:09:32,983 --> 00:09:36,367
numuruskaitli 1. 

212
00:09:36,367 --> 00:09:39,041
Tā, ka 33, kas palika aiz mugurasTā
kā 33 tika atstāts, mēs 

213
00:09:39,041 --> 00:09:41,715
izlikāmies, ka tā vairs nav, mēs to
vienkārši noplēsimnoņemsim un 

214
00:09:41,715 --> 00:09:44,390
ievietosim 40. 

215
00:09:44,390 --> 00:09:47,826
Un tad, protams, tā kā mēs veicām
grūdienuievietošanu, mēs 

216
00:09:47,826 --> 00:09:51,263
palielināsim kaudzessteka augšdaļu
no 1 līdz 2, lai, ja tagad 

217
00:09:51,263 --> 00:09:54,700
pievienosim vēl vienu elementu, tas
nonāktu masīva otrajā vietā divi. 

218
00:09:54,700 --> 00:09:57,590
 Tagad saistītie saraksti ir vēl
viens veids, kā ieviest stekus.

219
00:09:57,590 --> 00:10:01,190
Un, ja šī ekrānā redzamā definīcija
jums šķiet pazīstama, tas ir 

220
00:10:01,190 --> 00:10:04,790
tāpēc, ka tā izskatās gandrīz tieši
tāda pati, patiesībā tā ir 

221
00:10:04,790 --> 00:10:08,390
gandrīz tāda pati kā atsevišķi
saistītais saraksts, ja atceraties no 

222
00:10:08,390 --> 00:10:11,990
mūsu diskusijas par atsevišķi
saistītajiem sarakstiem citā. video. 

223
00:10:11,990 --> 00:10:14,866
Vienīgais ierobežojums šeit
attiecas uz mums kā programmētājiem, mēs 

224
00:10:14,866 --> 00:10:17,743
nedrīkstam ievietot vai dzēst
nejauši no atsevišķi saistītā saraksta, 

225
00:10:17,743 --> 00:10:20,620
ko mēs varējām darīt iepriekš. 

226
00:10:20,620 --> 00:10:23,470
Mēs varam ievietot un dzēst tikai
saistītā saraksta priekšpusē vai 

227
00:10:23,470 --> 00:10:26,320
augšpusē. 

228
00:10:26,320 --> 00:10:28,028
Tomēr tā patiešām ir vienīgā
atšķirība.

229
00:10:28,028 --> 00:10:29,700
Citādi šis ir atsevišķi saistīts
saraksts.

230
00:10:29,700 --> 00:10:32,735
Tas ir tikai ierobežojums, kas
aizstāj mūs kā programmētājus, kas to 

231
00:10:32,735 --> 00:10:35,770
pārvērš kaudzēstekā. 

232
00:10:35,770 --> 00:10:37,525
Noteikums šeit ir vienmēr saglabāt
rādītāju uz saistītā saraksta 

233
00:10:37,525 --> 00:10:39,280
galvgaligalvu. 

234
00:10:39,280 --> 00:10:41,520
Tas, protams, vispirms ir vispārīgi
svarīgs noteikums.

235
00:10:41,520 --> 00:10:43,878
Atsevišķi saistītam sarakstam
jebkurā gadījumā ir nepieciešams 

236
00:10:43,878 --> 00:10:46,237
rādītājs tikai uz galvu, lai šī
ķēde varētu atsaukties uz katru citu 

237
00:10:46,237 --> 00:10:48,596
saistītā saraksta elementu. 

238
00:10:48,596 --> 00:10:50,470
Bet tas ir īpaši svarīgi ar
kaudzisteku.

239
00:10:50,470 --> 00:10:52,280
Tātad kopumā jūs patiešām vēlaties,
lai šis rādītājs būtu globāls 

240
00:10:52,280 --> 00:10:54,090
mainīgais. 

241
00:10:54,090 --> 00:10:56,574
Iespējams, ka šādā veidā būs vēl
vieglāk.

242
00:10:56,574 --> 00:10:58,240
Tātad, kādi ir push un pop analogi?

243
00:10:58,240 --> 00:10:58,740
Pareizi.

244
00:10:58,740 --> 00:11:00,276
Tātad atkārtota spiešanapushing
nozīmē jauna elementa pievienošanu 

245
00:11:00,276 --> 00:11:01,812
kaudzīteistekam. 

246
00:11:01,812 --> 00:11:04,660
Saistītajā sarakstā tas nozīmē, ka
mums būs jāizveido jauns mezgls, 

247
00:11:04,660 --> 00:11:07,508
ko pievienosim saistītajam
sarakstam, un pēc tam veiciet rūpīgās 

248
00:11:07,508 --> 00:11:10,356
darbības, kuras iepriekš
aprakstījām atsevišķi saistītajos sarakstos, 

249
00:11:10,356 --> 00:11:13,204
lai to pievienotu ķēdiķēdei,
nepārraujot ķēdi un 

250
00:11:13,204 --> 00:11:16,052
pazaudējotnepazaudējot vai
nepadarot par bāreņiemneiznīcinot 

251
00:11:16,052 --> 00:11:18,900
saistītos saraksta elementus. 

252
00:11:18,900 --> 00:11:20,360
Un tas būtībā ir tas, ko tā mazā
teksta lāsetas nelielais teksts tur 

253
00:11:20,360 --> 00:11:21,820
apkopo. 

254
00:11:21,820 --> 00:11:23,740
Un aplūkosim to kā diagrammu.

255
00:11:23,740 --> 00:11:24,823
 Tātad, šeit ir mūsu saistītais
saraksts.

256
00:11:24,823 --> 00:11:26,620
Tajā vienlaikus ir četri elementi.

257
00:11:26,620 --> 00:11:28,520
Un vēl perfektāklabāk šeit ir mūsu
kaudzesteks, kurā ir četri 

258
00:11:28,520 --> 00:11:30,420
elementi. 

259
00:11:30,420 --> 00:11:33,225
Un pieņemsim, ka mēs tagad vēlamies
ievietot jaunu vienumu šajā 

260
00:11:33,225 --> 00:11:36,030
kaudzēstekā. 

261
00:11:36,030 --> 00:11:37,911
Un mēs vēlamies nosūtītievietot
jaunu vienumu, kura datu vērtība ir 

262
00:11:37,911 --> 00:11:39,792
12. 

263
00:11:39,792 --> 00:11:41,000
Nu, ko mēs darīsim?

264
00:11:41,000 --> 00:11:43,205
Vispirms mēs izmantosim
mallocizvēlēsimies vietu, dinamiski 

265
00:11:43,205 --> 00:11:45,411
piešķirsim vietu jaunam mezglam. 

266
00:11:45,411 --> 00:11:48,367
Un, protams, tūlīt pēc zvanīšanas
uz malloc izsaukuma mēs vienmēr 

267
00:11:48,367 --> 00:11:51,323
pārliecināmies, vai nav nulles, jo,
ja mēs saņemam nulli, radās kāda 

268
00:11:51,323 --> 00:11:54,280
veida problēma. 

269
00:11:54,280 --> 00:11:55,925
Mēs nevēlamies atsaukties uz šo
nulles rādītāju, pretējā gadījumā jūs 

270
00:11:55,925 --> 00:11:57,570
cietīsit seg kļūdu. 

271
00:11:57,570 --> 00:11:58,510
Tas nav labi.

272
00:11:58,510 --> 00:11:59,760
Tātad mēs esam novirzījušies no
mezglaizveidojuši mezglu.

273
00:11:59,760 --> 00:12:01,260
Mēs pieņemsim, ka mums šeit ir
panākumi.

274
00:12:01,260 --> 00:12:06,090
Mēs ievietosim 12 šī mezgla datu
laukā.

275
00:12:06,090 --> 00:12:08,830
Vai atceraties, kurš no mūsu
rādītājiem virzās tālāk, lai mēs 

276
00:12:08,830 --> 00:12:11,570
nepārrautu ķēdi? 

277
00:12:11,570 --> 00:12:14,833
Šeit ir dažas iespējas, taču
vienīgā drošadrošā ir iestatīt ziņu 

278
00:12:14,833 --> 00:12:18,096
nākamo rādītāju, lai norādītu uz
veco saraksta galveni vai to, kas 

279
00:12:18,096 --> 00:12:21,360
drīzumā būs vecā saraksta
galvgalīgalvene. 

280
00:12:21,360 --> 00:12:23,363
Un tagad, kad visi mūsu elementi ir
savienoti kopā, mēs varam 

281
00:12:23,363 --> 00:12:25,366
vienkārši pārvietot sarakstu, lai
norādītu uz to pašu vietu, kur to 

282
00:12:25,366 --> 00:12:27,370
darauz kuru norāda jaunais. 

283
00:12:27,370 --> 00:12:30,460
Tagad mēs esam efektīvi ievietojuši
jaunu elementu kaudzessteka 

284
00:12:30,460 --> 00:12:33,550
priekšpusē. 

285
00:12:33,550 --> 00:12:34,985
Lai parādītuizmantotu pop, mēs
vienkārši vēlamies izdzēst pirmo 

286
00:12:34,985 --> 00:12:36,420
elementu. 

287
00:12:36,420 --> 00:12:38,235
Un tāpēc būtībā tas, kas mums šeit
ir jādara, mums ir jāatrod otrais 

288
00:12:38,235 --> 00:12:40,050
elements. 

289
00:12:40,050 --> 00:12:43,540
Galu galā tas kļūs par jauno galvu
pēc tam, kad mēs izdzēsīsim pirmo.

290
00:12:43,540 --> 00:12:47,300
Tāpēc mums vienkārši jāsāk no
sākuma, jāvirzās uz priekšu.

291
00:12:47,300 --> 00:12:50,267
Kad esam sapratušiieguvuši vienu uz
priekšu, kur mēs pašlaik 

292
00:12:50,267 --> 00:12:53,235
atrodamies, varam droši dzēst
pirmo, un tad mēs varam vienkārši 

293
00:12:53,235 --> 00:12:56,202
pārvietot galvu, lai norādītu uz
to, kas bija otrais termins, un 

294
00:12:56,202 --> 00:12:59,170
tagad ir pirmais pēc šī mezgla
dzēšanas. . 

295
00:12:59,170 --> 00:13:02,096
Tātad vēlreiz, aplūkojot to kā
diagrammu, mēs tagad vēlamies noņemt 

296
00:13:02,096 --> 00:13:05,022
elementu no šīs kaudzesšī steka. 

297
00:13:05,022 --> 00:13:05,730
Tātad, ko mēs darām?

298
00:13:05,730 --> 00:13:08,335
Vispirms mēs izveidosim jaunu
rādītāju, kas norādīs uz to pašu vietu, 

299
00:13:08,335 --> 00:13:10,940
kur galva. 

300
00:13:10,940 --> 00:13:13,734
Mēs to pārvietosim par vienu
pozīciju uz priekšu, piemēram, sakot, ka 

301
00:13:13,734 --> 00:13:16,529
trav ir vienāds ar trav nākamotrav
equals trav , kas virzīs trav 

302
00:13:16,529 --> 00:13:19,324
rādītāju par vienu pozīciju uz
priekšu. 

303
00:13:19,324 --> 00:13:22,415
Tagad, kad esam noturējušiieguvuši
pirmo elementu, izmantojot 

304
00:13:22,415 --> 00:13:25,506
rādītāju, ko sauc par sarakstu, un
otro elementu, izmantojot rādītāju 

305
00:13:25,506 --> 00:13:28,597
trav, mēs varam droši izdzēst šo
pirmo elementu no steka, nezaudējot 

306
00:13:28,597 --> 00:13:31,688
pārējo ķēdes daļu, jo mums ir
veids, kā lai atsauktosatsaukties uz 

307
00:13:31,688 --> 00:13:34,780
otro elementu uz priekšu,
izmantojot rādītāju trav. 

308
00:13:34,780 --> 00:13:37,100
 Tātad tagad mēs varam atbrīvot šo
mezglu.

309
00:13:37,100 --> 00:13:38,404
Mēs varam brīviatbrīvot sarakstu.

310
00:13:38,404 --> 00:13:40,225
Un tad viss, kas mums tagad jādara,
ir jāpārvieto saraksts, lai 

311
00:13:40,225 --> 00:13:42,047
norādītu uz to pašu vietu, kur to
dara trav, un mēs esam atgriezušies 

312
00:13:42,047 --> 00:13:43,868
tur, kur sākām, pirms 12. virsmas
palielinājāmievietojām 12 pirmajā 

313
00:13:43,868 --> 00:13:45,690
vietā, pareizi. 

314
00:13:45,690 --> 00:13:46,940
Tieši šeit mēs bijām.

315
00:13:46,940 --> 00:13:48,840
Mums bija šīšis četru elementu
kaudzesteks.

316
00:13:48,840 --> 00:13:49,690
Mēs pievienojām piekto.

317
00:13:49,690 --> 00:13:52,835
Mēs uzspiedāmievietojām piekto
elementu un pēc tam atslēdzāmizņemām 

318
00:13:52,835 --> 00:13:55,980
pēdējo pievienoto elementu. 

319
00:13:55,980 --> 00:13:58,816
 Tas tiešām ir gandrīz viss, kas
saistīts ar skursteņiemstekiem.

320
00:13:58,816 --> 00:14:00,190
Jūs varat tos ieviest kā masīvus.

321
00:14:00,190 --> 00:14:01,815
Varat tos ieviest kā saistītos
sarakstus.

322
00:14:01,815 --> 00:14:04,810
Protams, ir arī citi veidi, kā tos
īstenot.

323
00:14:04,810 --> 00:14:08,200
Būtībā iemesls, kāpēc mēs izmantotu
skursteņusstekus, ir datu 

324
00:14:08,200 --> 00:14:11,590
uzturēšana tā, lai pēdējais
pievienotais elements būtu pirmais, ko 

325
00:14:11,590 --> 00:14:14,980
mēs vēlamies atgūt. 

326
00:14:14,980 --> 00:14:17,900
Es esmu Dags Loids, šis ir cs50.