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