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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Tất cả các quyền,
vậy bởi thời điểm này bạn

3
00:00:05,990 --> 00:00:09,020
có lẽ khá quen thuộc
với mảng và danh sách liên kết

4
00:00:09,020 --> 00:00:10,950
đó là hai chính
cấu trúc dữ liệu, chúng tôi đã

5
00:00:10,950 --> 00:00:16,810
nói về việc giữ cho bộ
dữ liệu của các kiểu dữ liệu tương tự tổ chức.

6
00:00:16,810 --> 00:00:19,080
>> Bây giờ chúng ta sẽ nói chuyện
về một vài biến thể

7
00:00:19,080 --> 00:00:20,330
về mảng và danh sách liên kết.

8
00:00:20,330 --> 00:00:22,362
Trong video này, chúng ta sẽ
để nói về ngăn xếp.

9
00:00:22,362 --> 00:00:25,320
Cụ thể chúng ta sẽ nói chuyện
về một cấu trúc dữ liệu gọi là stack.

10
00:00:25,320 --> 00:00:28,510
Nhớ lại từ các cuộc thảo luận trước đó
về con trỏ và bộ nhớ,

11
00:00:28,510 --> 00:00:32,060
rằng ngăn xếp cũng là
đặt tên cho một đoạn bộ nhớ

12
00:00:32,060 --> 00:00:34,980
nơi khai báo tĩnh
bộ nhớ memory-- bạn

13
00:00:34,980 --> 00:00:38,730
tên, biến mà bạn đặt tên, et
cetera và chức năng khung hình mà chúng tôi cũng

14
00:00:38,730 --> 00:00:41,000
khung stack gọi tồn tại.

15
00:00:41,000 --> 00:00:45,421
Vì vậy, đây là một cấu trúc ngăn xếp dữ liệu
không phải là một đoạn ngăn xếp bộ nhớ.

16
00:00:45,421 --> 00:00:45,920
ĐƯỢC.

17
00:00:45,920 --> 00:00:46,890
>> Nhưng một chồng là gì?

18
00:00:46,890 --> 00:00:49,220
Vì vậy, nó là khá nhiều chỉ là một
loại đặc biệt của cấu trúc

19
00:00:49,220 --> 00:00:51,190
duy trì dữ liệu trong một cách có tổ chức.

20
00:00:51,190 --> 00:00:53,760
Và có hai rất
cách phổ biến để thực hiện

21
00:00:53,760 --> 00:00:57,380
ngăn xếp bằng cách sử dụng hai cấu trúc dữ liệu
mà chúng ta đã quen thuộc với,

22
00:00:57,380 --> 00:01:00,340
mảng và danh sách liên kết.

23
00:01:00,340 --> 00:01:04,430
Điều gì làm cho một chồng đặc biệt là các
cách thức mà chúng tôi đưa thông tin

24
00:01:04,430 --> 00:01:08,200
thành đống, và cách chúng ta
loại bỏ các thông tin từ các stack.

25
00:01:08,200 --> 00:01:11,600
Đặc biệt với ngăn xếp
các quy tắc chỉ là nhất

26
00:01:11,600 --> 00:01:15,830
Gần đây yếu tố bổ sung có thể được gỡ bỏ.

27
00:01:15,830 --> 00:01:17,660
>> Vì vậy, suy nghĩ về nó như thể nó là một chồng.

28
00:01:17,660 --> 00:01:21,170
Chúng tôi đang chất đống thông tin
trên bản thân nó,

29
00:01:21,170 --> 00:01:24,271
và chỉ có điều ở đầu
của cọc có thể được gỡ bỏ.

30
00:01:24,271 --> 00:01:27,020
Chúng ta không thể loại bỏ các điều bên dưới
bởi vì tất cả mọi thứ khác sẽ

31
00:01:27,020 --> 00:01:28,020
sụp đổ và rơi trên.

32
00:01:28,020 --> 00:01:32,580
Vì vậy, chúng tôi thực sự đang xây dựng một chồng mà
sau đó chúng ta phải loại bỏ từng mảnh.

33
00:01:32,580 --> 00:01:36,590
Bởi vì điều này chúng ta thường gọi
để một chồng như một cấu trúc LIFO,

34
00:01:36,590 --> 00:01:38,940
kéo vào, ra đầu tiên.

35
00:01:38,940 --> 00:01:42,290
LIFO, kéo vào, đầu ra.

36
00:01:42,290 --> 00:01:45,635
>> Vì vậy, do sự hạn chế này trên
làm thế nào thông tin có thể được thêm vào

37
00:01:45,635 --> 00:01:49,080
và lấy ra từ một chồng, có thực sự
chỉ có hai điều chúng ta có thể làm với một chồng.

38
00:01:49,080 --> 00:01:52,010
Chúng tôi có thể thúc đẩy, đó là
hạn, chúng tôi sử dụng cho việc thêm

39
00:01:52,010 --> 00:01:55,130
một nguyên tố mới cho phần trên của
ngăn xếp, hoặc nếu chồng không tồn tại

40
00:01:55,130 --> 00:01:58,550
và chúng tôi đang tạo ra nó từ đầu,
tạo ra các ngăn xếp ở vị trí đầu tiên

41
00:01:58,550 --> 00:02:00,110
sẽ đẩy.

42
00:02:00,110 --> 00:02:04,990
Và sau đó bật, đó là loại của CS
hạn chúng tôi sử dụng để loại bỏ gần đây nhất

43
00:02:04,990 --> 00:02:08,330
thêm phần tử từ đỉnh của ngăn xếp.

44
00:02:08,330 --> 00:02:11,130
>> Vì vậy, chúng ta sẽ xem xét ở cả hai
triển khai thực hiện, cả hai mảng dựa

45
00:02:11,130 --> 00:02:13,120
và danh sách liên kết dựa.

46
00:02:13,120 --> 00:02:14,870
Và chúng ta sẽ
bắt đầu với mảng dựa.

47
00:02:14,870 --> 00:02:19,990
Vì vậy, đây là ý tưởng cơ bản của những gì
mảng dựa trên cấu trúc ngăn xếp dữ liệu

48
00:02:19,990 --> 00:02:21,140
sẽ như thế nào.

49
00:02:21,140 --> 00:02:23,740
Chúng tôi có một định nghĩa gõ ở đây.

50
00:02:23,740 --> 00:02:27,790
Bên trong của chúng ta có hai thành viên
hoặc các lĩnh vực của cấu trúc.

51
00:02:27,790 --> 00:02:29,880
Chúng tôi có một mảng.

52
00:02:29,880 --> 00:02:32,400
Và một lần nữa tôi đang sử dụng
giá trị kiểu dữ liệu tùy ý.

53
00:02:32,400 --> 00:02:35,180
>> Vì vậy, đây có thể là bất kỳ kiểu dữ liệu,
int char hoặc một số dữ liệu khác

54
00:02:35,180 --> 00:02:37,080
gõ mà bạn đã tạo trước đó.

55
00:02:37,080 --> 00:02:39,861
Vì vậy, chúng tôi có một loạt các khả năng kích thước.

56
00:02:39,861 --> 00:02:44,010
Công suất được định nghĩa một bảng liên tục,
có lẽ ở một nơi khác trong tập tin của chúng tôi.

57
00:02:44,010 --> 00:02:47,550
Vì vậy, nhận thấy đã có đặc biệt này
thực hiện chúng tôi đang bounding

58
00:02:47,550 --> 00:02:49,800
mình là là thường
trường hợp với mảng,

59
00:02:49,800 --> 00:02:53,170
mà chúng ta có thể không tự động thay đổi kích thước,
nơi có một số lượng nhất định

60
00:02:53,170 --> 00:02:55,450
các yếu tố tối đa mà
chúng ta có thể đặt trong ngăn xếp của chúng tôi.

61
00:02:55,450 --> 00:02:57,930
Trong trường hợp này nó là yếu tố năng lực.

62
00:02:57,930 --> 00:03:00,310
>> Chúng tôi cũng theo dõi
đỉnh của stack.

63
00:03:00,310 --> 00:03:04,350
Yếu tố gì là nhất
gần đây đã thêm vào stack?

64
00:03:04,350 --> 00:03:07,470
Và vì vậy chúng tôi theo dõi mà
trong một biến gọi là hàng đầu.

65
00:03:07,470 --> 00:03:11,692
Và tất cả những điều này được bao bọc với nhau
thành một kiểu dữ liệu mới gọi là một chồng.

66
00:03:11,692 --> 00:03:13,400
Và một khi chúng ta được tạo
kiểu dữ liệu mới này

67
00:03:13,400 --> 00:03:15,410
chúng ta có thể đối xử với nó như
bất kỳ loại dữ liệu khác.

68
00:03:15,410 --> 00:03:20,970
Chúng tôi có thể tuyên bố chồng s, giống như
chúng ta có thể làm int x, y hoặc char.

69
00:03:20,970 --> 00:03:22,990
Và khi chúng ta nói rằng chồng
s, cũng những gì xảy ra

70
00:03:22,990 --> 00:03:26,420
là chúng ta có được một bộ
bộ nhớ dành cho chúng ta.

71
00:03:26,420 --> 00:03:28,770
>> Trong trường hợp này công suất
Tôi đã quyết định rõ ràng

72
00:03:28,770 --> 00:03:33,470
là 10, vì tôi đã có một
biến đơn kiểu ngăn xếp

73
00:03:33,470 --> 00:03:35,320
trong đó có hai trường nhớ lại.

74
00:03:35,320 --> 00:03:38,330
Một mảng, trong trường hợp này là
là một mảng các số nguyên

75
00:03:38,330 --> 00:03:40,440
như trường hợp ở hầu hết các ví dụ của tôi.

76
00:03:40,440 --> 00:03:43,996
Và biến số nguyên khác
khả năng lưu trữ hàng đầu,

77
00:03:43,996 --> 00:03:45,870
gần đây nhất được bổ sung
yếu tố để các stack.

78
00:03:45,870 --> 00:03:50,290
Vì vậy, một trong những đơn ngăn xếp của những gì chúng ta
chỉ định trông như thế này.

79
00:03:50,290 --> 00:03:53,190
Đó là một hộp chứa
một mảng của 10 gì

80
00:03:53,190 --> 00:03:57,280
sẽ là các số nguyên trong trường hợp này và
một biến số nguyên có màu xanh lá cây

81
00:03:57,280 --> 00:04:00,010
để chỉ ra các đỉnh của ngăn xếp.

82
00:04:00,010 --> 00:04:02,600
>> Để thiết lập đỉnh
ngăn xếp, chúng tôi chỉ nói s.top.

83
00:04:02,600 --> 00:04:04,890
Đó là cách chúng ta truy cập một
lĩnh vực thu hồi cấu trúc.

84
00:04:04,890 --> 00:04:10,460
s.top bằng 0 có hiệu quả
thực hiện điều này để ngăn xếp của chúng tôi.

85
00:04:10,460 --> 00:04:12,960
Vì vậy, một lần nữa chúng tôi có hai hoạt động
rằng chúng ta có thể thực hiện ngay bây giờ.

86
00:04:12,960 --> 00:04:14,270
Chúng tôi có thể đẩy và chúng tôi có thể bật.

87
00:04:14,270 --> 00:04:15,635
Hãy bắt đầu với push.

88
00:04:15,635 --> 00:04:18,260
Một lần nữa, đẩy được thêm mới
yếu tố để các đỉnh của ngăn xếp.

89
00:04:18,260 --> 00:04:21,460
>> Vì vậy, những gì chúng ta cần phải làm gì trong
mảng này thực hiện dựa?

90
00:04:21,460 --> 00:04:23,210
Vâng trong chung
đẩy chức năng sẽ

91
00:04:23,210 --> 00:04:26,160
cần phải chấp nhận một
con trỏ vào stack.

92
00:04:26,160 --> 00:04:28,610
Bây giờ lấy một giây và suy nghĩ về nó.

93
00:04:28,610 --> 00:04:32,840
Tại sao chúng tôi muốn chấp nhận
một con trỏ tới ngăn xếp?

94
00:04:32,840 --> 00:04:36,830
Nhớ lại từ video trước đó trên
phạm vi biến và con trỏ,

95
00:04:36,830 --> 00:04:42,350
điều gì sẽ xảy ra nếu chúng tôi vừa gửi
ngăn xếp, s thay như một tham số?

96
00:04:42,350 --> 00:04:45,770
Điều gì thực sự sẽ được thông qua trong đó?

97
00:04:45,770 --> 00:04:49,430
Hãy nhớ rằng chúng tôi đang tạo ra một bản sao
khi chúng ta vượt qua nó để một chức năng

98
00:04:49,430 --> 00:04:51,160
trừ khi chúng ta sử dụng con trỏ.

99
00:04:51,160 --> 00:04:55,380
Và chức năng này đẩy nhu cầu
để chấp nhận một con trỏ vào stack

100
00:04:55,380 --> 00:04:59,160
để chúng tôi đang thực sự thay đổi
stack chúng tôi có ý định thay đổi.

101
00:04:59,160 --> 00:05:03,060
>> Điều push khác có lẽ cũng muốn đến
chấp nhận là một thành phần dữ liệu của loại giá trị.

102
00:05:03,060 --> 00:05:06,970
Trong trường hợp này, một lần nữa, một số nguyên
chúng ta sẽ thêm vào phía trên cùng của ngăn xếp.

103
00:05:06,970 --> 00:05:08,680
Vì vậy, chúng tôi đã có hai thông số của chúng tôi.

104
00:05:08,680 --> 00:05:11,310
Chúng ta sẽ đến
bây giờ làm bên trong đẩy?

105
00:05:11,310 --> 00:05:14,860
Vâng, chỉ đơn giản, chúng ta chỉ cần đi thêm
rằng yếu tố để các đỉnh của stack

106
00:05:14,860 --> 00:05:22,860
và sau đó thay đổi nơi đầu
stack là, đó là chấm giá trị hàng đầu.

107
00:05:22,860 --> 00:05:25,639
Vì vậy, đây là những gì một chức năng
kê khai push

108
00:05:25,639 --> 00:05:27,680
có thể trông giống như trong một
mảng dựa trên việc thực hiện.

109
00:05:27,680 --> 00:05:30,967
>> Một lần nữa đây không phải là một quy tắc cứng và nhanh chóng
mà bạn có thể thay đổi điều này và có

110
00:05:30,967 --> 00:05:32,050
nó thay đổi theo những cách khác nhau.

111
00:05:32,050 --> 00:05:33,840
Có lẽ s được tuyên bố trên toàn cầu.

112
00:05:33,840 --> 00:05:36,180
Và do đó, bạn thậm chí không cần
để vượt qua nó như một tham số.

113
00:05:36,180 --> 00:05:39,125
Đây lại là chỉ một
trường hợp tổng quát cho push.

114
00:05:39,125 --> 00:05:41,000
Và có khác nhau
cách để thực hiện nó.

115
00:05:41,000 --> 00:05:42,810
Nhưng trong trường hợp này chúng tôi
push là sẽ mất

116
00:05:42,810 --> 00:05:48,540
hai tham số, một con trỏ đến một chồng và
một phần tử dữ liệu của loại giá trị, số nguyên

117
00:05:48,540 --> 00:05:49,840
trong trường hợp này.

118
00:05:49,840 --> 00:05:52,100
>> Vì vậy, chúng tôi tuyên bố của chúng tôi
nói s.top bằng 0.

119
00:05:52,100 --> 00:05:55,969
Bây giờ chúng ta hãy đẩy
số 28 vào ngăn xếp.

120
00:05:55,969 --> 00:05:57,010
Cũng có nghĩa là gì?

121
00:05:57,010 --> 00:05:59,600
Vâng hiện nay
đỉnh của ngăn xếp là 0.

122
00:05:59,600 --> 00:06:01,350
Và vì vậy những gì là cơ bản
sẽ xảy ra là

123
00:06:01,350 --> 00:06:05,820
chúng ta sẽ dính vào các số
28 thành mảng vị trí 0.

124
00:06:05,820 --> 00:06:09,540
Khá dễ dàng, đúng, đó
là hàng đầu và bây giờ chúng tôi đang tốt để đi.

125
00:06:09,540 --> 00:06:12,910
Và sau đó chúng ta cần phải thay đổi những gì
đỉnh của ngăn xếp sẽ được.

126
00:06:12,910 --> 00:06:15,130
Vì vậy mà trong thời gian tới
chúng ta đẩy một phần tử trong,

127
00:06:15,130 --> 00:06:18,017
chúng ta sẽ lưu nó trong
vị trí mảng, có lẽ không phải là 0.

128
00:06:18,017 --> 00:06:20,100
Chúng tôi không muốn ghi đè lên
những gì chúng ta chỉ cần đặt ở đó.

129
00:06:20,100 --> 00:06:23,510
Và vì vậy chúng tôi sẽ chỉ di chuyển trên xuống 1.

130
00:06:23,510 --> 00:06:24,890
Điều đó có thể làm cho tinh thần.

131
00:06:24,890 --> 00:06:28,940
>> Bây giờ nếu chúng ta muốn đặt một yếu tố khác
vào ngăn xếp, nói chúng tôi muốn đẩy 33,

132
00:06:28,940 --> 00:06:33,190
cũng bây giờ chúng tôi chỉ cần đi để lấy 33
và đặt nó ở vị trí số mảng

133
00:06:33,190 --> 00:06:37,580
1, và sau đó thay đổi các đầu của chúng tôi
ngăn xếp được mảng vị trí số hai.

134
00:06:37,580 --> 00:06:40,650
Vì vậy, nếu thời gian tới, chúng tôi muốn
đẩy một phần tử vào stack,

135
00:06:40,650 --> 00:06:43,087
nó sẽ được đặt ở vị trí 2 mảng.

136
00:06:43,087 --> 00:06:44,420
Và chúng ta hãy làm điều đó một lần nữa.

137
00:06:44,420 --> 00:06:45,753
Chúng tôi sẽ đẩy 19 off của ngăn xếp.

138
00:06:45,753 --> 00:06:48,940
Chúng tôi sẽ đưa 19 trong mảng vị trí 2
và thay đổi trên của ngăn xếp của chúng tôi

139
00:06:48,940 --> 00:06:51,220
là mảng vị trí 3
vì vậy nếu thời gian chúng tôi bên cạnh

140
00:06:51,220 --> 00:06:54,780
cần phải thực hiện một sự thúc đẩy chúng tôi đang tốt để đi.

141
00:06:54,780 --> 00:06:56,980
>> OK, vì vậy đó là đẩy một cách ngắn gọn.

142
00:06:56,980 --> 00:06:57,830
Những gì về popping?

143
00:06:57,830 --> 00:07:00,240
Vì vậy, popping là loại
đối ứng để đẩy.

144
00:07:00,240 --> 00:07:02,720
Đó là cách chúng tôi loại bỏ dữ liệu từ stack.

145
00:07:02,720 --> 00:07:04,610
Và trong nhu cầu pop nói chung
làm như sau.

146
00:07:04,610 --> 00:07:07,600
Nó cần phải chấp nhận một con trỏ đến
ngăn xếp, một lần nữa trong trường hợp tổng quát.

147
00:07:07,600 --> 00:07:10,480
Trong một số trường hợp khác có lẽ bạn
đã tuyên bố stack trên toàn cầu,

148
00:07:10,480 --> 00:07:13,910
trong trường hợp này bạn không cần phải vượt qua nó
tại vì nó đã có quyền truy cập vào nó

149
00:07:13,910 --> 00:07:15,541
như là một biến toàn cầu.

150
00:07:15,541 --> 00:07:17,040
Nhưng sau đó những gì mà chúng ta cần phải làm gì?

151
00:07:17,040 --> 00:07:21,000
Vâng, chúng tôi đã được incrementing
trên cùng của ngăn xếp trong push,

152
00:07:21,000 --> 00:07:24,050
vì vậy chúng ta có lẽ sẽ muốn
để giảm các đỉnh của stack

153
00:07:24,050 --> 00:07:25,009
trong pop, phải không?

154
00:07:25,009 --> 00:07:26,800
Và sau đó tất nhiên
chúng tôi cũng sẽ muốn

155
00:07:26,800 --> 00:07:29,240
để trở về giá trị mà chúng ta loại bỏ.

156
00:07:29,240 --> 00:07:32,125
Nếu chúng ta thêm các yếu tố, chúng ta muốn
để có được các yếu tố ra sau này,

157
00:07:32,125 --> 00:07:34,000
chúng ta có thể thực sự
muốn lưu trữ chúng để chúng tôi

158
00:07:34,000 --> 00:07:36,490
không chỉ cần xóa chúng khỏi
chồng và sau đó không làm gì với họ.

159
00:07:36,490 --> 00:07:38,500
Nói chung nếu chúng tôi
đẩy và popping ở đây

160
00:07:38,500 --> 00:07:41,250
chúng tôi muốn lưu trữ này
thông tin trong một cách có ý nghĩa

161
00:07:41,250 --> 00:07:43,250
và do đó, nó không làm cho
ý nghĩa để chỉ loại bỏ nó.

162
00:07:43,250 --> 00:07:46,380
Vì vậy, chức năng này nên
có thể trả về một giá trị cho chúng tôi.

163
00:07:46,380 --> 00:07:51,040
>> Vì vậy, đây là những gì một tuyên bố cho pop
có thể trông giống như có ở trên cùng bên trái.

164
00:07:51,040 --> 00:07:53,870
Hàm này trả về
dữ liệu của loại giá trị.

165
00:07:53,870 --> 00:07:56,320
Một lần nữa, chúng tôi đã sử dụng
số nguyên trong suốt.

166
00:07:56,320 --> 00:08:01,916
Và nó chấp nhận một con trỏ đến một ngăn xếp như
diện duy nhất của mình hoặc tham số duy nhất.

167
00:08:01,916 --> 00:08:03,040
Vì vậy, những gì được pop sẽ làm gì?

168
00:08:03,040 --> 00:08:07,990
Hãy nói rằng chúng tôi muốn bây giờ
bật một yếu tố tắt của s.

169
00:08:07,990 --> 00:08:14,000
Vì vậy, hãy nhớ tôi đã nói rằng ngăn xếp là cuối cùng
, ra trước, LIFO cấu trúc dữ liệu.

170
00:08:14,000 --> 00:08:17,855
Những phần tử được sắp
được loại bỏ khỏi stack?

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

172
00:08:21,780 --> 00:08:24,150
Bạn có đoán 19?

173
00:08:24,150 --> 00:08:25,290
Bởi vì bạn muốn được quyền.

174
00:08:25,290 --> 00:08:28,836
19 là yếu tố cuối cùng chúng tôi đã thêm vào
ngăn xếp khi chúng tôi đã đẩy các yếu tố trên,

175
00:08:28,836 --> 00:08:31,210
và do đó, nó sẽ là người đầu tiên
yếu tố đó được gỡ bỏ.

176
00:08:31,210 --> 00:08:34,780
Đó là nếu chúng ta nói 28, và
sau đó chúng tôi đặt 33 trên đầu trang của nó,

177
00:08:34,780 --> 00:08:36,659
và chúng tôi đặt 19 trên đó.

178
00:08:36,659 --> 00:08:40,650
Yếu tố duy nhất chúng ta có thể cất cánh là 19.

179
00:08:40,650 --> 00:08:45,019
>> Bây giờ trong sơ đồ ở đây những gì tôi đã thực hiện
là loại xóa 19 từ mảng.

180
00:08:45,019 --> 00:08:46,810
Đó không phải là thực sự
những gì chúng ta sẽ làm.

181
00:08:46,810 --> 00:08:48,934
Chúng tôi chỉ cần đi để loại
của giả vờ đó là không có.

182
00:08:48,934 --> 00:08:51,441
Nó vẫn còn đó trong
mà vị trí bộ nhớ,

183
00:08:51,441 --> 00:08:54,190
nhưng chúng tôi chỉ cần đi để bỏ qua nó
bằng cách thay đổi các đầu của ngăn xếp của chúng tôi

184
00:08:54,190 --> 00:08:56,080
từ là 3-2.

185
00:08:56,080 --> 00:08:58,720
Vì vậy, nếu chúng ta bây giờ đẩy
một yếu tố vào ngăn xếp,

186
00:08:58,720 --> 00:09:00,720
nó sẽ qua viết 19.

187
00:09:00,720 --> 00:09:03,990
>> Nhưng chúng ta không đi qua những rắc rối
xóa 19 từ stack.

188
00:09:03,990 --> 00:09:05,830
Chúng tôi chỉ có thể giả vờ đó là không có.

189
00:09:05,830 --> 00:09:11,107
Đối với mục đích của chồng nó đi nếu
chúng ta thay đổi trên để được 2 thay vì 3.

190
00:09:11,107 --> 00:09:12,690
Tất cả các quyền, vì vậy đó là khá nhiều đó.

191
00:09:12,690 --> 00:09:15,080
Đó là tất cả chúng ta cần phải làm
để bật một yếu tố hết.

192
00:09:15,080 --> 00:09:16,090
Hãy làm điều đó một lần nữa.

193
00:09:16,090 --> 00:09:18,610
Vì vậy, tôi đã nêu bật nó trong màu đỏ ở đây để
cho thấy chúng ta đang thực hiện một cuộc gọi khác.

194
00:09:18,610 --> 00:09:19,720
Chúng ta sẽ làm điều tương tự.

195
00:09:19,720 --> 00:09:20,803
>> Vì vậy, những gì sẽ xảy ra?

196
00:09:20,803 --> 00:09:23,670
Vâng, chúng ta sẽ lưu
33 trong x và chúng ta sẽ

197
00:09:23,670 --> 00:09:26,217
thay đổi trên cùng của ngăn xếp để 1.

198
00:09:26,217 --> 00:09:29,050
Vì vậy, nếu chúng tôi ngay bây giờ để đẩy một
phần tử vào stack mà chúng tôi

199
00:09:29,050 --> 00:09:31,610
sẽ làm ngay bây giờ,
những gì sẽ xảy ra

200
00:09:31,610 --> 00:09:36,367
là chúng ta sẽ ghi đè lên
mảng vị trí số 1.

201
00:09:36,367 --> 00:09:38,950
Vì vậy mà 33 đã được loại bỏ
đằng sau đó chúng tôi chỉ giả vờ

202
00:09:38,950 --> 00:09:44,390
là không còn ở đó nữa, chúng ta chỉ cần đi
để clobber nó và đặt 40 có thay thế.

203
00:09:44,390 --> 00:09:46,290
Và dĩ nhiên,
kể từ khi chúng tôi thực hiện một sự thúc đẩy,

204
00:09:46,290 --> 00:09:48,780
chúng tôi đang đi để tăng
đỉnh của stack 1-2

205
00:09:48,780 --> 00:09:50,950
nên nếu chúng ta bây giờ thêm
yếu tố khác nó sẽ thấy

206
00:09:50,950 --> 00:09:54,700
đi vào mảng vị trí số hai.

207
00:09:54,700 --> 00:09:57,590
>> Bây giờ là danh sách liên kết khác
cách để thực hiện ngăn xếp.

208
00:09:57,590 --> 00:10:01,210
Và nếu định nghĩa này trên
màn hình ở đây có vẻ quen thuộc với bạn,

209
00:10:01,210 --> 00:10:04,260
đó là vì nó trông gần
chính xác như nhau, trên thực tế,

210
00:10:04,260 --> 00:10:07,790
nó khá nhiều là chính xác
giống như một danh sách đơn lẻ liên kết,

211
00:10:07,790 --> 00:10:11,990
nếu bạn nhớ lại từ cuộc thảo luận của chúng ta về
danh sách liên kết đơn lẻ trong một video khác.

212
00:10:11,990 --> 00:10:15,510
Hạn chế duy nhất ở đây
là đối với chúng tôi là lập trình viên,

213
00:10:15,510 --> 00:10:17,900
chúng tôi không được phép
chèn hoặc xóa ngẫu nhiên

214
00:10:17,900 --> 00:10:20,620
từ danh sách liên kết đơn lẻ
mà chúng ta có thể làm được trước đây.

215
00:10:20,620 --> 00:10:25,820
Chỉ bây giờ chúng ta có thể chèn và xóa từ
phía trước hoặc phía trên của liên kết

216
00:10:25,820 --> 00:10:26,320
danh sách.

217
00:10:26,320 --> 00:10:28,028
Đó thực sự là chỉ
sự khác biệt.

218
00:10:28,028 --> 00:10:29,700
Đây là trường hợp một danh sách đơn lẻ liên kết.

219
00:10:29,700 --> 00:10:32,060
Nó chỉ có các hạn chế
thay vào bản thân mình

220
00:10:32,060 --> 00:10:35,770
như lập trình viên
thay đổi nó thành một chồng.

221
00:10:35,770 --> 00:10:39,280
>> Các quy tắc ở đây là phải luôn luôn duy trì một
con trỏ đến đầu của một danh sách liên kết.

222
00:10:39,280 --> 00:10:41,520
Đây là khóa học một thường
Nguyên tắc quan trọng đầu tiên.

223
00:10:41,520 --> 00:10:44,260
Đối với danh sách liên kết đơn lẻ anyway bạn
chỉ cần một con trỏ đến đầu

224
00:10:44,260 --> 00:10:46,160
để có được điều đó
chuỗi có thể tham khảo

225
00:10:46,160 --> 00:10:48,596
để mọi phần tử khác
trong danh sách liên kết.

226
00:10:48,596 --> 00:10:50,470
Nhưng nó đặc biệt
quan trọng với một chồng.

227
00:10:50,470 --> 00:10:52,386
Và nói chung bạn đang
sẽ thực sự muốn

228
00:10:52,386 --> 00:10:54,090
con trỏ này là một biến toàn cầu.

229
00:10:54,090 --> 00:10:56,574
Nó có lẽ sẽ
được dễ dàng hơn theo cách đó.

230
00:10:56,574 --> 00:10:58,240
Vì vậy, các chất tương tự của push và pop là gì?

231
00:10:58,240 --> 00:10:58,740
Bên phải.

232
00:10:58,740 --> 00:11:01,812
Vì vậy, một lần nữa đẩy được thêm
một nguyên tố mới vào stack.

233
00:11:01,812 --> 00:11:03,770
Trong một danh sách liên kết đó
có nghĩa là chúng ta sẽ có

234
00:11:03,770 --> 00:11:07,770
để tạo ra một nút mới chúng tôi
sẽ thêm vào danh sách liên kết,

235
00:11:07,770 --> 00:11:10,500
và sau đó làm theo các bước sau cẩn thận
rằng chúng tôi đã vạch ra trước đó

236
00:11:10,500 --> 00:11:16,050
trong danh sách liên kết đơn lẻ để thêm nó vào
các chuỗi mà không phá vỡ dây chuyền

237
00:11:16,050 --> 00:11:18,900
và mất hoặc orphaning bất kỳ
các yếu tố của danh sách liên kết.

238
00:11:18,900 --> 00:11:21,820
Và đó là cơ bản những gì mà
ít blob của văn bản có tóm tắt.

239
00:11:21,820 --> 00:11:23,740
Và chúng ta hãy có một cái nhìn
vào nó như là một sơ đồ.

240
00:11:23,740 --> 00:11:24,823
>> Vì vậy, đây là danh sách liên kết của chúng tôi.

241
00:11:24,823 --> 00:11:26,620
Nó đồng thời có bốn yếu tố.

242
00:11:26,620 --> 00:11:30,420
Và hoàn hảo hơn ở đây là của chúng tôi
ngăn xếp chứa bốn yếu tố.

243
00:11:30,420 --> 00:11:36,030
Và hãy nói rằng bây giờ chúng tôi muốn
đẩy một mục mới vào stack này.

244
00:11:36,030 --> 00:11:39,792
Và chúng tôi muốn đẩy một mới
mục dữ liệu mà giá trị là 12.

245
00:11:39,792 --> 00:11:41,000
Vâng những gì chúng ta sẽ làm gì?

246
00:11:41,000 --> 00:11:43,420
Cũng lần đầu tiên chúng ta sẽ
không gian malloc, năng động

247
00:11:43,420 --> 00:11:45,411
phân bổ không gian cho một nút mới.

248
00:11:45,411 --> 00:11:48,160
Và tất nhiên ngay lập tức sau khi
chúng tôi thực hiện một cuộc gọi đến malloc chúng tôi luôn

249
00:11:48,160 --> 00:11:52,989
hãy chắc chắn để kiểm tra null,
bởi vì nếu chúng ta có vô lại

250
00:11:52,989 --> 00:11:54,280
đã có một số loại vấn đề.

251
00:11:54,280 --> 00:11:57,570
Chúng tôi không muốn tới đích không cho rằng
con trỏ hoặc bạn sẽ phải chịu một lỗi seg.

252
00:11:57,570 --> 00:11:58,510
Đó không phải là tốt.

253
00:11:58,510 --> 00:11:59,760
Vì vậy, chúng tôi đã malloced của nút.

254
00:11:59,760 --> 00:12:01,260
Chúng tôi sẽ giả sử chúng ta đã thành công ở đây.

255
00:12:01,260 --> 00:12:06,090
Chúng ta sẽ đặt 12 vào
các trường dữ liệu của nút đó.

256
00:12:06,090 --> 00:12:11,570
Bây giờ ông có nhớ mà con trỏ của chúng tôi
di chuyển tiếp theo nên chúng tôi không phá vỡ dây chuyền?

257
00:12:11,570 --> 00:12:15,100
Chúng tôi có một vài tùy chọn ở đây nhưng
chỉ có một mà sẽ là an toàn

258
00:12:15,100 --> 00:12:19,330
là để thiết lập tức con trỏ bên cạnh
Điểm đến đầu cũ của danh sách

259
00:12:19,330 --> 00:12:21,360
hoặc những gì sẽ sớm được
đầu cũ của danh sách.

260
00:12:21,360 --> 00:12:23,610
Và bây giờ mà tất cả chúng tôi
yếu tố được xích lại với nhau,

261
00:12:23,610 --> 00:12:27,370
chúng ta chỉ có thể di chuyển danh sách đến điểm
đến cùng một nơi mà mới làm.

262
00:12:27,370 --> 00:12:33,550
Và bây giờ chúng tôi đã đẩy một cách hiệu quả
yếu tố mới vào phía trước của stack.

263
00:12:33,550 --> 00:12:36,420
>> Để bật, chúng tôi chỉ muốn
xóa mà yếu tố đầu tiên.

264
00:12:36,420 --> 00:12:38,150
Và do đó, về cơ bản những gì
chúng ta phải làm ở đây,

265
00:12:38,150 --> 00:12:40,050
cũng chúng ta phải tìm các yếu tố thứ hai.

266
00:12:40,050 --> 00:12:43,540
Cuối cùng sẽ trở thành mới
đầu sau khi chúng ta xóa một đầu.

267
00:12:43,540 --> 00:12:47,300
Vì vậy, chúng ta chỉ cần bắt đầu từ
Ban đầu, di chuyển một về phía trước.

268
00:12:47,300 --> 00:12:50,340
Một khi chúng ta đã có một tổ chức trên một
phía trước của nơi mà chúng ta hiện

269
00:12:50,340 --> 00:12:53,850
là chúng ta có thể xóa một cách an toàn đầu tiên
và sau đó chúng ta chỉ có thể di chuyển đầu

270
00:12:53,850 --> 00:12:57,150
để trỏ đến những gì là
kỳ thứ hai và sau đó bây giờ

271
00:12:57,150 --> 00:12:59,170
là lần đầu tiên sau đó
nút đã bị xóa.

272
00:12:59,170 --> 00:13:01,160
>> Vì vậy, một lần nữa, dùng một cái nhìn
vào nó như là một sơ đồ chúng tôi

273
00:13:01,160 --> 00:13:05,022
muốn bây giờ bật một
yếu tố ra khỏi stack.

274
00:13:05,022 --> 00:13:05,730
vậy chúng ta làm gì?

275
00:13:05,730 --> 00:13:08,188
Vâng, chúng tôi đang đầu tiên sẽ tạo ra
một con trỏ mới đó là đi

276
00:13:08,188 --> 00:13:10,940
để trỏ đến cùng một chỗ như người đứng đầu.

277
00:13:10,940 --> 00:13:13,790
Chúng ta sẽ di chuyển nó một vị trí
về phía trước bằng cách nói trav equals

278
00:13:13,790 --> 00:13:17,510
TRAV tiếp theo ví dụ,
hơn sẽ thúc đẩy một con trỏ trav

279
00:13:17,510 --> 00:13:19,324
vị trí phía trước.

280
00:13:19,324 --> 00:13:21,240
Bây giờ chúng ta đã có một
giữ trên các yếu tố đầu tiên

281
00:13:21,240 --> 00:13:24,573
thông qua con trỏ được gọi là danh sách, và các
Yếu tố thứ hai thông qua một con trỏ được gọi là

282
00:13:24,573 --> 00:13:28,692
trav, chúng ta có thể an toàn xóa mà
Yếu tố đầu tiên từ stack

283
00:13:28,692 --> 00:13:30,650
mà không mất phần còn lại
của chuỗi bởi vì chúng tôi

284
00:13:30,650 --> 00:13:32,358
có một cách để tham khảo
đến phần tử thứ hai

285
00:13:32,358 --> 00:13:34,780
chuyển tiếp bằng cách của
con trỏ được gọi là trav.

286
00:13:34,780 --> 00:13:37,100
>> Vì vậy, bây giờ chúng tôi có thể giải phóng nút đó.

287
00:13:37,100 --> 00:13:38,404
Chúng tôi có thể miễn phí danh sách.

288
00:13:38,404 --> 00:13:41,320
Và sau đó tất cả chúng ta cần làm bây giờ là
di chuyển danh sách đến thời điểm đến cùng một nơi

289
00:13:41,320 --> 00:13:44,482
trav nào, và chúng tôi sắp xếp lại
nơi chúng tôi bắt đầu trước khi chúng tôi đã đẩy 12

290
00:13:44,482 --> 00:13:45,690
trên ở nơi đầu tiên, phải.

291
00:13:45,690 --> 00:13:46,940
Đây chính là nơi mà chúng tôi đã.

292
00:13:46,940 --> 00:13:48,840
Chúng tôi đã có bốn yếu tố này stack.

293
00:13:48,840 --> 00:13:49,690
Chúng tôi thêm một phần năm.

294
00:13:49,690 --> 00:13:51,910
Chúng tôi đã đẩy một phần năm
yếu tố trên, và sau đó chúng tôi

295
00:13:51,910 --> 00:13:55,980
popped mà gần đây nhất
thêm vào yếu tố quay trở lại.

296
00:13:55,980 --> 00:13:58,816
>> Đó là thực sự khá nhiều
tất cả để có ngăn xếp.

297
00:13:58,816 --> 00:14:00,190
Bạn có thể thực hiện chúng như mảng.

298
00:14:00,190 --> 00:14:01,815
Bạn có thể thực hiện chúng như danh sách liên kết.

299
00:14:01,815 --> 00:14:04,810
Có, tất nhiên, khác
cách để thực hiện chúng là tốt.

300
00:14:04,810 --> 00:14:09,060
Về cơ bản là lý do chúng ta sẽ sử dụng
ngăn xếp là để duy trì dữ liệu trong một cách như vậy

301
00:14:09,060 --> 00:14:12,090
mà gần đây nhất được bổ sung
phần tử là điều đầu tiên chúng tôi

302
00:14:12,090 --> 00:14:14,980
sẽ muốn quay trở lại.

303
00:14:14,980 --> 00:14:17,900
Tôi Doug Lloyd, đây là CS50.

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