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
имя, переменные, которые вы называете, и др
Cetera и функциональные кадры, которые мы также

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
ЛИФО, последний пришел, первым ушел.

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
>> Таким образом, это может быть любой тип данных,
INT символ или некоторые другие данные

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
Мы можем объявить стека S, так же, как
мы могли бы сделать Int х, или сЬаг у.

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
что произойдет, если мы только что отправил
стек, S, а в качестве параметра?

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
а затем изменить где верх
стек, что S точка верхнее значение.

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
Так что помните, я сказал, что стеки в прошлом
в, первые из ЛИФО, структур данных.

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
и потери или сиротами любой
элементы связанного списка.

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
Мы не хотим, чтобы разыменования NULL этом
указатель или вы будете страдать неисправность SEG.

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 рядом, например, что
будет продвигать указатель Трав один

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
Трав, мы можем безопасно удалить, что
Первый элемент из стека

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