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

2
00:00:04,074 --> 00:00:05,990
Дъг LLOYD: Добре,
така от този момент вие сте

3
00:00:05,990 --> 00:00:09,020
Вероятно доста запознат
с масиви и свързани списъци

4
00:00:09,020 --> 00:00:10,950
която е два основни
структури от данни с които сме се

5
00:00:10,950 --> 00:00:16,810
Говорихме за за поддържане на комплекта
данни от подобни типове данни, организирана.

6
00:00:16,810 --> 00:00:19,080
>> Сега ние ще говорим
за няколко вариации

7
00:00:19,080 --> 00:00:20,330
на масиви и свързани списъци.

8
00:00:20,330 --> 00:00:22,362
В това видео отиваме
да се говори за стакове.

9
00:00:22,362 --> 00:00:25,320
Конкретно, ние ще говорим
за структурата на данните, наречена стек.

10
00:00:25,320 --> 00:00:28,510
Спомнете си от предишни дискусии
за указатели и паметта,

11
00:00:28,510 --> 00:00:32,060
че топчето е и
име за един сегмент на паметта

12
00:00:32,060 --> 00:00:34,980
където статично декларирани
memory-- памет, която ви

13
00:00:34,980 --> 00:00:38,730
назове, променливи, които ви име, et
и така нататък функция рамки които също

14
00:00:38,730 --> 00:00:41,000
съществуват кол стека рамки.

15
00:00:41,000 --> 00:00:45,421
Така че това е структура комин данни
Не комин сегмент на паметта.

16
00:00:45,421 --> 00:00:45,920
ДОБРЕ.

17
00:00:45,920 --> 00:00:46,890
>> Но това, което е комин?

18
00:00:46,890 --> 00:00:49,220
Така че това е доста много просто
специален вид структура

19
00:00:49,220 --> 00:00:51,190
която поддържа данни по организиран начин.

20
00:00:51,190 --> 00:00:53,760
И има две много
общи начини за изпълнение

21
00:00:53,760 --> 00:00:57,380
стекове използват две структури от данни
че вече сте запознати с,

22
00:00:57,380 --> 00:01:00,340
масиви и свързани списъци.

23
00:01:00,340 --> 00:01:04,430
Какво прави един стек специален, е
начин, по който ще се постави информация

24
00:01:04,430 --> 00:01:08,200
в стека, а ние пътя
премахване на информация от комина.

25
00:01:08,200 --> 00:01:11,600
По-специално със стекове
правилото е само най-

26
00:01:11,600 --> 00:01:15,830
наскоро добавя елемент може да бъде отстранен.

27
00:01:15,830 --> 00:01:17,660
>> Така че мисля за това като че ли е комин.

28
00:01:17,660 --> 00:01:21,170
Ние сме трупат информация
на върха на себе си,

29
00:01:21,170 --> 00:01:24,271
и само нещо в горната
на купчината могат да бъдат отстранени.

30
00:01:24,271 --> 00:01:27,020
Ние не можем да се премахне нещо отдолу
защото всичко останало би

31
00:01:27,020 --> 00:01:28,020
срине и да падне.

32
00:01:28,020 --> 00:01:32,580
Така че ние наистина са изграждането на стека, че
тогава ние трябва да се отстранят парче по парче.

33
00:01:32,580 --> 00:01:36,590
Поради това ние обикновено наричаме
да комин като структура LIFO,

34
00:01:36,590 --> 00:01:38,940
издържи, първа изходяща.

35
00:01:38,940 --> 00:01:42,290
LIFO, издържи, първа изходяща.

36
00:01:42,290 --> 00:01:45,635
>> Така че, тъй като на това ограничение върху
как информацията може да се добави

37
00:01:45,635 --> 00:01:49,080
и отстранен от комин, там наистина
само две неща които можем да направим със стак.

38
00:01:49,080 --> 00:01:52,010
Ние можем да бута, която е най-
Терминът ние използваме за добавяне

39
00:01:52,010 --> 00:01:55,130
нов елемент към върха на
стека, или ако топчето не съществува

40
00:01:55,130 --> 00:01:58,550
и ние сме го създаде от нулата,
създаване на стека на първо място

41
00:01:58,550 --> 00:02:00,110
Би било бутане.

42
00:02:00,110 --> 00:02:04,990
И тогава се появи, това е нещо като CS
Терминът ние използваме, за да се отстрани най-скоро

43
00:02:04,990 --> 00:02:08,330
добавен елемент от върха на стека.

44
00:02:08,330 --> 00:02:11,130
>> Така че ние ще разгледаме и двете
реализации, въз основа както масив

45
00:02:11,130 --> 00:02:13,120
и свързан списък на базата.

46
00:02:13,120 --> 00:02:14,870
И ние ще се
започнем с масив на базата.

47
00:02:14,870 --> 00:02:19,990
Така че тук е основната идея на това, което
Структурата стека данни на масива основава

48
00:02:19,990 --> 00:02:21,140
ще изглежда така.

49
00:02:21,140 --> 00:02:23,740
Ние се даде определение на въведените от тук.

50
00:02:23,740 --> 00:02:27,790
Вътре на които имаме двама членове
или области на структурата.

51
00:02:27,790 --> 00:02:29,880
Ние имаме масив.

52
00:02:29,880 --> 00:02:32,400
И пак аз съм с помощта на
произволна стойност тип данни.

53
00:02:32,400 --> 00:02:35,180
>> Така че това би могло да бъде всеки тип данни,
инт Чар или някои други данни

54
00:02:35,180 --> 00:02:37,080
написали сте създали преди това.

55
00:02:37,080 --> 00:02:39,861
Така че ние имаме масив от капацитета размер.

56
00:02:39,861 --> 00:02:44,010
Капацитет бъде един паунд дефинирана константа,
може би някъде другаде в нашата файл.

57
00:02:44,010 --> 00:02:47,550
Така че забележите вече с този конкретен
прилагане ние очертаващ

58
00:02:47,550 --> 00:02:49,800
себе си като е типично
случаят с масиви,

59
00:02:49,800 --> 00:02:53,170
които не можем динамично преоразмеряване,
където има определен брой

60
00:02:53,170 --> 00:02:55,450
Елементи максимална че
можем да сложим в нашия стак.

61
00:02:55,450 --> 00:02:57,930
В този случай това е елементи капацитет.

62
00:02:57,930 --> 00:03:00,310
>> Ние също така да следите
на върха на купчината.

63
00:03:00,310 --> 00:03:04,350
Какво елемент е най-
Наскоро беше добавен в стека?

64
00:03:04,350 --> 00:03:07,470
И така, ние следим, че
в променлива наречена отгоре.

65
00:03:07,470 --> 00:03:11,692
И всичко това бъде пренесена заедно
в нов тип данни, наречена стек.

66
00:03:11,692 --> 00:03:13,400
И след като сме създали
този нов тип данни

67
00:03:13,400 --> 00:03:15,410
можем да го третират като
всеки друг тип информация.

68
00:03:15,410 --> 00:03:20,970
Ние може да обяви стека ите, точно като
бихме могли да направим инт х или у Чар.

69
00:03:20,970 --> 00:03:22,990
И когато казваме, стека
ите, и какво се случва,

70
00:03:22,990 --> 00:03:26,420
е да стигнем набор от
памет, заделена за нас.

71
00:03:26,420 --> 00:03:28,770
>> В този случай капацитет
Аз бях очевидно реши

72
00:03:28,770 --> 00:03:33,470
е 10, защото аз имам
една променлива от тип стак

73
00:03:33,470 --> 00:03:35,320
който съдържа две полета изземване.

74
00:03:35,320 --> 00:03:38,330
Масивът, в този случай ще
да бъде масив от числа

75
00:03:38,330 --> 00:03:40,440
какъвто е случаят в повечето от моите примери.

76
00:03:40,440 --> 00:03:43,996
И още една целочислена променлива
възможност за съхраняване на върха,

77
00:03:43,996 --> 00:03:45,870
най Последно добавени
елемент към стека.

78
00:03:45,870 --> 00:03:50,290
Така че един-единствен пакет от това, което ние
Просто определено изглежда по този начин.

79
00:03:50,290 --> 00:03:53,190
Това е кутия, съдържаща
масив от 10, което

80
00:03:53,190 --> 00:03:57,280
ще бъде числа в този случай и в
друго число променлива има в зелено

81
00:03:57,280 --> 00:04:00,010
за обозначаване на върха на купчината.

82
00:04:00,010 --> 00:04:02,600
>> За задаване на върха на
стак можем просто да кажем s.top.

83
00:04:02,600 --> 00:04:04,890
Ето как можем достъп до
поле на структура изземване.

84
00:04:04,890 --> 00:04:10,460
s.top е равна на 0 ефективно
прави това в нашия стак.

85
00:04:10,460 --> 00:04:12,960
Така че отново имаме две операции
че можем да се извърши сега.

86
00:04:12,960 --> 00:04:14,270
Ние можем да бутнете и ние можем да поп.

87
00:04:14,270 --> 00:04:15,635
Нека да започнем с натискане.

88
00:04:15,635 --> 00:04:18,260
Отново, бутане е добавянето на нов
елемент на върха на купчината.

89
00:04:18,260 --> 00:04:21,460
>> Така че това, което ние трябва да направим в
този масив базирани изпълнение?

90
00:04:21,460 --> 00:04:23,210
Ами като цяло на
тласък функция ще

91
00:04:23,210 --> 00:04:26,160
да се наложи да приеме
указател към стека.

92
00:04:26,160 --> 00:04:28,610
Сега вземете втори и мисля за това.

93
00:04:28,610 --> 00:04:32,840
Защо искаме да приемем
указател към стека?

94
00:04:32,840 --> 00:04:36,830
Спомнете си от предишните клипове на
променлива обхват и указатели,

95
00:04:36,830 --> 00:04:42,350
какво ще се случи, ако ние просто изпраща
стак, е по-скоро в като параметър?

96
00:04:42,350 --> 00:04:45,770
Какво всъщност ще бъде приет там?

97
00:04:45,770 --> 00:04:49,430
Не забравяйте, че ние създаваме копие
когато ние го предаде на функция

98
00:04:49,430 --> 00:04:51,160
освен ако не използваме указатели.

99
00:04:51,160 --> 00:04:55,380
И така, тази функция натиснете нужди
да приеме указател към стека

100
00:04:55,380 --> 00:04:59,160
така че ние всъщност се променя
стека ние възнамеряваме да се промени.

101
00:04:59,160 --> 00:05:03,060
>> Другото нещо, натискането вероятно иска да
приемам е елемент от данни от тип стойност.

102
00:05:03,060 --> 00:05:06,970
В този случай отново, цяло число, че
ние ще добавим към върха на стека.

103
00:05:06,970 --> 00:05:08,680
Така че ние имаме нашите два параметъра.

104
00:05:08,680 --> 00:05:11,310
Какво ще се
Сега правя вътре тласък?

105
00:05:11,310 --> 00:05:14,860
Ами, просто, ние просто ще добавите
този елемент на върха на купчината

106
00:05:14,860 --> 00:05:22,860
и след това се променя, когато горната част на
топчето е, че е точка, за върхова стойност.

107
00:05:22,860 --> 00:05:25,639
Така че това е, което е функция
декларация за бутане

108
00:05:25,639 --> 00:05:27,680
може да изглежда така в
гама-базирани изпълнение.

109
00:05:27,680 --> 00:05:30,967
>> Отново това не е трудно и бързо правило
че бихте могли да промените това и да има

110
00:05:30,967 --> 00:05:32,050
тя варира по различни начини.

111
00:05:32,050 --> 00:05:33,840
Може би и е обявен за световно.

112
00:05:33,840 --> 00:05:36,180
И така, вие дори не е необходимо
за да премине тя е като параметър.

113
00:05:36,180 --> 00:05:39,125
Това отново е просто
общ случай за натискане.

114
00:05:39,125 --> 00:05:41,000
И там са различни
начини за неговото прилагане.

115
00:05:41,000 --> 00:05:42,810
Но в този случай ни
тласък ще отнеме

116
00:05:42,810 --> 00:05:48,540
два аргумента, указател към стека и
един елемент от данни от тип стойност, число

117
00:05:48,540 --> 00:05:49,840
в такъв случай.

118
00:05:49,840 --> 00:05:52,100
>> Така че ние обявена ите, ние
каза s.top е равна на 0.

119
00:05:52,100 --> 00:05:55,969
Сега нека да буташ
номер 28 върху купчината.

120
00:05:55,969 --> 00:05:57,010
Ами какво означава това?

121
00:05:57,010 --> 00:05:59,600
Е момента
най-отгоре е 0.

122
00:05:59,600 --> 00:06:01,350
И така, това, което е в основата
щеше да се случи, е

123
00:06:01,350 --> 00:06:05,820
ние ще се придържаме броя
28 в масив място 0.

124
00:06:05,820 --> 00:06:09,540
Доста проста, нали, че
беше на върха и сега сме добре да тръгвам.

125
00:06:09,540 --> 00:06:12,910
И тогава ние трябва да променим това, което
горната част на стека ще бъде.

126
00:06:12,910 --> 00:06:15,130
Така че следващия път,
ние бутнете елемент в,

127
00:06:15,130 --> 00:06:18,017
отиваме да я съхранява в
масив място, най-вероятно няма 0.

128
00:06:18,017 --> 00:06:20,100
Ние не искаме да презапишете
това, което ние просто сложи там.

129
00:06:20,100 --> 00:06:23,510
И така, ние просто ще се премести на върха на 1.

130
00:06:23,510 --> 00:06:24,890
Това вероятно има смисъл.

131
00:06:24,890 --> 00:06:28,940
>> Сега, ако искаме да се сложи още един елемент
върху купчината, казват ние искаме да прокара 33,

132
00:06:28,940 --> 00:06:33,190
и сега ние просто ще отнеме 33
и го сложи под номер местоположение масив

133
00:06:33,190 --> 00:06:37,580
1, и след това да се промени в началото на нашата
стека да бъде масив място номер две.

134
00:06:37,580 --> 00:06:40,650
Така че, ако следващия път, ние искаме да
бутнете елемент към стека,

135
00:06:40,650 --> 00:06:43,087
тя ще бъде пусната в населено място масив 2.

136
00:06:43,087 --> 00:06:44,420
И нека да направим това още един път.

137
00:06:44,420 --> 00:06:45,753
Ще бутнете 19 на разстояние от купчините.

138
00:06:45,753 --> 00:06:48,940
Ние ще сложи 19 в населено място масив 2
и промяна на върха на нашия стак

139
00:06:48,940 --> 00:06:51,220
да бъде място масив 3
така че ако следващия път, когато

140
00:06:51,220 --> 00:06:54,780
Трябва да се направи лицеви сме добре да тръгвам.

141
00:06:54,780 --> 00:06:56,980
>> ОК, така че това е бутане в орехова черупка.

142
00:06:56,980 --> 00:06:57,830
Какво ще кажете за мак?

143
00:06:57,830 --> 00:07:00,240
Така че мак е нещо
колега да натискате.

144
00:07:00,240 --> 00:07:02,720
Това е начина, по който изтриете данни от комина.

145
00:07:02,720 --> 00:07:04,610
И в общи поп нужди
да направите следното.

146
00:07:04,610 --> 00:07:07,600
Тя трябва да приеме указател към
стека, отново в общия случай.

147
00:07:07,600 --> 00:07:10,480
В друг случай може да се
са декларирали стека в световен мащаб,

148
00:07:10,480 --> 00:07:13,910
като в този случай не е нужно да го давате
в защото вече има достъп до него

149
00:07:13,910 --> 00:07:15,541
като глобална променлива.

150
00:07:15,541 --> 00:07:17,040
Но тогава какво друго трябва да направим?

151
00:07:17,040 --> 00:07:21,000
Ами ние бяхме увеличаване
на върха на стека в бута,

152
00:07:21,000 --> 00:07:24,050
така че ние сме най-вероятно ще искате
да намалите върха на стека

153
00:07:24,050 --> 00:07:25,009
в поп, нали?

154
00:07:25,009 --> 00:07:26,800
И след това, разбира се,
ние също ще искате

155
00:07:26,800 --> 00:07:29,240
да върне стойност, която ние премахваме.

156
00:07:29,240 --> 00:07:32,125
Ако ние сме добавяне на елементи, ние искаме
за да получите елементи от по-късно,

157
00:07:32,125 --> 00:07:34,000
ние вероятно действително
Искам да ги съхранява, така че ние

158
00:07:34,000 --> 00:07:36,490
не просто да ги изтриете от
стека, а след това не се прави нищо с тях.

159
00:07:36,490 --> 00:07:38,500
По принцип, ако сме
бутане и пръкват тук

160
00:07:38,500 --> 00:07:41,250
ние искаме да съхранявате това
информация по смислен начин

161
00:07:41,250 --> 00:07:43,250
и така тя не прави
смисъл просто да го изхвърли.

162
00:07:43,250 --> 00:07:46,380
Така че тази функция трябва да
Вероятно връща стойност за нас.

163
00:07:46,380 --> 00:07:51,040
>> Така че това е, което декларация за поп
може да изглежда като там в горния ляв ъгъл.

164
00:07:51,040 --> 00:07:53,870
Тази функция връща
данни от тип стойност.

165
00:07:53,870 --> 00:07:56,320
Отново сме били използване на
числа в цялата сграда.

166
00:07:56,320 --> 00:08:01,916
И тя приема указател към пакетна
свое аргумент или едноличен параметър.

167
00:08:01,916 --> 00:08:03,040
И така, какво е поп смяташ да правиш?

168
00:08:03,040 --> 00:08:07,990
Да кажем, че искаме да сега
поп елемент на разстояние от с.

169
00:08:07,990 --> 00:08:14,000
Така че не забравяйте, аз казах, че стакове са последните
, първа изходяща, LIFO структури от данни.

170
00:08:14,000 --> 00:08:17,855
На кой елемент ще
се отделя от стека?

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

172
00:08:21,780 --> 00:08:24,150
Знаете ли, предполагам, 19?

173
00:08:24,150 --> 00:08:25,290
Защото ще бъдеш прав.

174
00:08:25,290 --> 00:08:28,836
19 е последният елемент ние добавихме към
стека, когато бяхме бутане елементи върху,

175
00:08:28,836 --> 00:08:31,210
и така тя ще отиде на първата
елемент, който се премахва.

176
00:08:31,210 --> 00:08:34,780
Това е като че казахме 28, и
След това ще се постави на 33 в началото на това,

177
00:08:34,780 --> 00:08:36,659
и ще се постави 19 отгоре на това.

178
00:08:36,659 --> 00:08:40,650
Единственият елемент можем да се свали е 19.

179
00:08:40,650 --> 00:08:45,019
>> Сега в диаграмата тук, което съм направил
е нещо като изтрит 19 от масива.

180
00:08:45,019 --> 00:08:46,810
Това не е реално
това, което ние ще направим.

181
00:08:46,810 --> 00:08:48,934
Ние просто ще натура
на преструвам, че не е там.

182
00:08:48,934 --> 00:08:51,441
Тя все още е там, в
че място в паметта,

183
00:08:51,441 --> 00:08:54,190
но ние просто ще го игнорират
чрез промяна на върха на купчина ни

184
00:08:54,190 --> 00:08:56,080
е от 3-2.

185
00:08:56,080 --> 00:08:58,720
Така че, ако ние бяхме досега бутнете
още един елемент към стека,

186
00:08:58,720 --> 00:09:00,720
тя ще напише над 19.

187
00:09:00,720 --> 00:09:03,990
>> Но нека не мине през неприятности
на изтриване 19 от комина.

188
00:09:03,990 --> 00:09:05,830
Ние можем просто да се преструваме, че не е там.

189
00:09:05,830 --> 00:09:11,107
За целите на стека го няма, ако
сменяме на върха да бъде 2, вместо 3.

190
00:09:11,107 --> 00:09:12,690
Добре, така че е доста много я.

191
00:09:12,690 --> 00:09:15,080
Това е всичко, което трябва да направим
да поп елемент на разстояние.

192
00:09:15,080 --> 00:09:16,090
Да го направим отново.

193
00:09:16,090 --> 00:09:18,610
Така че аз съм го маркира в червено тук, за да
посочва ние правим друг разговор.

194
00:09:18,610 --> 00:09:19,720
Отиваме да направи същото нещо.

195
00:09:19,720 --> 00:09:20,803
>> И така, какво ще се случи?

196
00:09:20,803 --> 00:09:23,670
Е, ние ще се съхранява
33 в х и отиваме

197
00:09:23,670 --> 00:09:26,217
за промяна на върха на купчината 1.

198
00:09:26,217 --> 00:09:29,050
Така, че ако бяхме сега, за да прокарат
елемент в стека, които сме

199
00:09:29,050 --> 00:09:31,610
ще направя точно сега,
какво ще се случи

200
00:09:31,610 --> 00:09:36,367
се отиваме презаписване
масив място номер 1.

201
00:09:36,367 --> 00:09:38,950
Така, че на 33, че е нещо като ляво
зад които ние просто се престори

202
00:09:38,950 --> 00:09:44,390
вече не съществува, ние просто ще
да го смажат и постави там, вместо 40.

203
00:09:44,390 --> 00:09:46,290
И тогава, разбира се,
тъй като ние направихме едно натискане,

204
00:09:46,290 --> 00:09:48,780
отиваме и прираста на
най-отгоре 1-2

205
00:09:48,780 --> 00:09:50,950
така че, ако ние сега се добавят
друг елемент, че ще

206
00:09:50,950 --> 00:09:54,700
отидат в масив място номер две.

207
00:09:54,700 --> 00:09:57,590
>> Сега свързани списъци са друг
начин за осъществяване на купчини.

208
00:09:57,590 --> 00:10:01,210
И ако това определение относно
екран тук изглежда познато за вас,

209
00:10:01,210 --> 00:10:04,260
това е, защото тя изглежда почти
точно същото, в действителност,

210
00:10:04,260 --> 00:10:07,790
тя почти е точно
същата като единично свързан списък,

211
00:10:07,790 --> 00:10:11,990
ако си спомняте от нашата дискусия за
поединично свързани списъци в друг видеоклип.

212
00:10:11,990 --> 00:10:15,510
Единственото ограничение тук
е за нас като програмисти,

213
00:10:15,510 --> 00:10:17,900
ние не ти е позволено да
вмъкнете или изтриете случайно

214
00:10:17,900 --> 00:10:20,620
от единично свързан списък
които бихме могли да направим по-рано.

215
00:10:20,620 --> 00:10:25,820
Само сега можем да вмъкнете и да изтрие от
предната или горната част на свързана

216
00:10:25,820 --> 00:10:26,320
списък.

217
00:10:26,320 --> 00:10:28,028
Това е наистина единствената
разлика все пак.

218
00:10:28,028 --> 00:10:29,700
Това е друг начин на единично свързан списък.

219
00:10:29,700 --> 00:10:32,060
Това е само ограничението
подмяна на себе си

220
00:10:32,060 --> 00:10:35,770
като програмисти, че
той се променя на купчина.

221
00:10:35,770 --> 00:10:39,280
>> Правилото тук е да се поддържа винаги
указател към главата на свързан списък.

222
00:10:39,280 --> 00:10:41,520
Това е, разбира се, а като цяло
важно правило първо.

223
00:10:41,520 --> 00:10:44,260
За единично свързан списък, така или иначе ви
Необходимо е само указател към главата

224
00:10:44,260 --> 00:10:46,160
за да има, че
веригата да може да отнесе

225
00:10:46,160 --> 00:10:48,596
на всеки друг елемент
на свързания списък.

226
00:10:48,596 --> 00:10:50,470
Но това е особено
важната със стак.

227
00:10:50,470 --> 00:10:52,386
И така, по принцип сте
Ще всъщност искат

228
00:10:52,386 --> 00:10:54,090
Този показалец е глобална променлива.

229
00:10:54,090 --> 00:10:56,574
Това е най-вероятно ще
да бъде още по-лесно по този начин.

230
00:10:56,574 --> 00:10:58,240
Така че какви са аналози на бута и поп?

231
00:10:58,240 --> 00:10:58,740
Право.

232
00:10:58,740 --> 00:11:01,812
Така бутане отново се добавяне
нов елемент към стека.

233
00:11:01,812 --> 00:11:03,770
В свързан списък, който
означава, че ние ще имаме

234
00:11:03,770 --> 00:11:07,770
за създаване на нова възлова точка, която сме
Ще добавим в списъка свързана,

235
00:11:07,770 --> 00:11:10,500
и след това следвайте стъпките внимателни
че сме посочили по-рано

236
00:11:10,500 --> 00:11:16,050
в поединично свързани списъци, за да го добавите към
веригата без да се скъса веригата

237
00:11:16,050 --> 00:11:18,900
и загуба или orphaning всеки
елементи от свързан списък.

238
00:11:18,900 --> 00:11:21,820
И това е в общи линии какво
малко петно ​​на текст има обобщава.

239
00:11:21,820 --> 00:11:23,740
И нека да разгледаме
на него като диаграма.

240
00:11:23,740 --> 00:11:24,823
>> Така че тук е нашата свързан списък.

241
00:11:24,823 --> 00:11:26,620
Тя едновременно съдържа четири елемента.

242
00:11:26,620 --> 00:11:30,420
И по-точно тук е нашата
стека, съдържащ четири елемента.

243
00:11:30,420 --> 00:11:36,030
И нека да кажем, сега искаме да
бутнете нов елемент в този стак.

244
00:11:36,030 --> 00:11:39,792
И ние искаме да прокара нов
артикул, чиято стойност е 12 данни.

245
00:11:39,792 --> 00:11:41,000
Ами какво ще правим?

246
00:11:41,000 --> 00:11:43,420
Ами първо отиваме да
изчистване пространство, динамично

247
00:11:43,420 --> 00:11:45,411
разпредели пространство за нов възел.

248
00:11:45,411 --> 00:11:48,160
И разбира се, веднага след
ние да осъществите повикване до изчистване ние винаги

249
00:11:48,160 --> 00:11:52,989
не забравяйте да проверите за нищожна,
защото ако имаме нулев назад

250
00:11:52,989 --> 00:11:54,280
Имаше някакъв проблем.

251
00:11:54,280 --> 00:11:57,570
Ние не искаме да сочен, че нулевата
указател или ще страдат неизправност в сек.

252
00:11:57,570 --> 00:11:58,510
Това не е добре.

253
00:11:58,510 --> 00:11:59,760
Така че ние сме malloced на възела.

254
00:11:59,760 --> 00:12:01,260
Ние ще приемем, че съм имал успех тук.

255
00:12:01,260 --> 00:12:06,090
Отиваме да сложи 12 в
полето за данни на този възел.

256
00:12:06,090 --> 00:12:11,570
Сега искаш да си припомним кои от нашите указатели
движи следващата така че ние не се прекъсне веригата?

257
00:12:11,570 --> 00:12:15,100
Имаме няколко опции, но тук
единственият, който ще бъде в безопасност

258
00:12:15,100 --> 00:12:19,330
е да се определят новини, указател към следващия
точка до най-стария началото на списъка

259
00:12:19,330 --> 00:12:21,360
или това, което скоро ще бъде най-
стар шеф на списъка.

260
00:12:21,360 --> 00:12:23,610
И сега, че цялата ни
елементи са оковани заедно,

261
00:12:23,610 --> 00:12:27,370
ние можем просто да се движат списък да посоча
на същото място, че нов прави.

262
00:12:27,370 --> 00:12:33,550
И ние сега ефективно натисна
нов елемент върху предната част на комина.

263
00:12:33,550 --> 00:12:36,420
>> За да можем поп просто искам да
изтриете, че първият елемент.

264
00:12:36,420 --> 00:12:38,150
И така, това, което в общи линии
ние трябва да направим тук,

265
00:12:38,150 --> 00:12:40,050
и ние трябва да намерим втория елемент.

266
00:12:40,050 --> 00:12:43,540
В крайна сметка, която ще се превърне в новия
глава, след като изтриете първия.

267
00:12:43,540 --> 00:12:47,300
Така че ние просто трябва да се започне от
началото, се движат една напред.

268
00:12:47,300 --> 00:12:50,340
След като ние имаме дял в една
напред от където сме в момента

269
00:12:50,340 --> 00:12:53,850
са можем да изтриете първия безопасно
и тогава ние можем просто да се движи главата

270
00:12:53,850 --> 00:12:57,150
да сочи към това, което беше
втори мандат и след това предприятието

271
00:12:57,150 --> 00:12:59,170
е първият след това
възел е била изтрита.

272
00:12:59,170 --> 00:13:01,160
>> Така че отново, като се погледнете
при това като диаграма ние

273
00:13:01,160 --> 00:13:05,022
Сега искам да се появи на
елемент на разстояние от този стак.

274
00:13:05,022 --> 00:13:05,730
И така, какво ще правим?

275
00:13:05,730 --> 00:13:08,188
Ами ние сме първи ще създадем
нова показалка, че ще ходи

276
00:13:08,188 --> 00:13:10,940
да сочат към едно и също място като ръководител.

277
00:13:10,940 --> 00:13:13,790
Отиваме да го премести с една позиция
напред, като казва TRAV равни

278
00:13:13,790 --> 00:13:17,510
TRAV следващата например, която
ще преминете този, на Trav показалка

279
00:13:17,510 --> 00:13:19,324
позиция напред.

280
00:13:19,324 --> 00:13:21,240
Сега, ние имаме
задръжте върху първия елемент

281
00:13:21,240 --> 00:13:24,573
през списъка с показалеца плати и на
втори елемент чрез указател, наречен

282
00:13:24,573 --> 00:13:28,692
Trav, можем спокойно да изтриете, че
първи елемент от стека

283
00:13:28,692 --> 00:13:30,650
без да се губи останалата
на веригата, защото

284
00:13:30,650 --> 00:13:32,358
има начин да се отнесе
на втория елемент

285
00:13:32,358 --> 00:13:34,780
предаде по пътя на
показалка нарича Trav.

286
00:13:34,780 --> 00:13:37,100
>> Така че сега можем да освободим този възел.

287
00:13:37,100 --> 00:13:38,404
Ние можем да освободим списък.

288
00:13:38,404 --> 00:13:41,320
И тогава всичко, което трябва да направя сега е
преместите списък с точка на същото място

289
00:13:41,320 --> 00:13:44,482
че Trav прави, и ние сме нещо като обратно
там, откъдето започнахме преди да избута 12

290
00:13:44,482 --> 00:13:45,690
на първо място, нали.

291
00:13:45,690 --> 00:13:46,940
Това е точно там, където бяхме.

292
00:13:46,940 --> 00:13:48,840
Имахме този елемент четири стека.

293
00:13:48,840 --> 00:13:49,690
Ние добавихме една пета.

294
00:13:49,690 --> 00:13:51,910
Ние бутна една пета
елемент на, и след това ние

295
00:13:51,910 --> 00:13:55,980
показа, че най-скоро
добавен елемент обратно на разстояние.

296
00:13:55,980 --> 00:13:58,816
>> Това е наистина доста много
всичко там е да се комбинира.

297
00:13:58,816 --> 00:14:00,190
Можете да ги въведе по масиви.

298
00:14:00,190 --> 00:14:01,815
Можете да ги приложи, свързани списъци.

299
00:14:01,815 --> 00:14:04,810
Има, разбира се, други
начини за тяхното прилагане, както и.

300
00:14:04,810 --> 00:14:09,060
Основно причината щяхме да използваме
стакове е да поддържа данни по такъв начин,

301
00:14:09,060 --> 00:14:12,090
че най-последно добавени
елемент е първото нещо, което сме

302
00:14:12,090 --> 00:14:14,980
ще искам да се върна.

303
00:14:14,980 --> 00:14:17,900
Аз съм Дъг Лойд, това е cs50.

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