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

2
00:00:04,074 --> 00:00:05,990
DOUG 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
名稱，命名變量，等
等等和功能框架，我們也

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 char或其他一些數據

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 x或字符年。

69
00:03:20,970 --> 00:03:22,990
而當我們說堆棧
S，以及會發生什麼

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
也許s的全局聲明。

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，我們
說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
>> OK，所以這是推動概括地說。

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 x和我們要去

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
那麼什麼是push和pop的類似物？

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
那麼首先我們要
malloc的空間，動態

247
00:11:43,420 --> 00:11:45,411
分配空間用於新的節點。

248
00:11:45,411 --> 00:11:48,160
當然，緊接著又
我們打電話到我們的malloc始終

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指針1

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