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
LIFO, สุดท้ายในครั้งแรกออกมา

36
00:01:42,290 --> 00:01:45,635
>> ดังนั้นเนื่องจากข้อ จำกัด เกี่ยวกับเรื่องนี้
วิธีการที่ข้อมูลสามารถเพิ่ม

37
00:01:45,635 --> 00:01:49,080
และลบออกจากกองมีจริงๆ
เพียงสองสิ่งที่เราสามารถทำอะไรกับกอง

38
00:01:49,080 --> 00:01:52,010
เราสามารถผลักดันซึ่งเป็น
คำที่เราใช้สำหรับการเพิ่ม

39
00:01:52,010 --> 00:01:55,130
องค์ประกอบใหม่ในด้านบนของ
สแต็คหรือถ้ากองไม่ได้อยู่

40
00:01:55,130 --> 00:01:58,550
และเรากำลังสร้างมันจากรอยขีดข่วน
การสร้างสแต็คในสถานที่แรก

41
00:01:58,550 --> 00:02:00,110
จะผลักดัน

42
00:02:00,110 --> 00:02:04,990
และจากนั้นปรากฏว่าการจัดเรียงของซี
คำที่เราใช้ในการลบเมื่อเร็ว ๆ นี้

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
เราสามารถประกาศของสแต็คเช่นเดียวกับ
เราสามารถทำ int x, y ที่หรือถ่าน

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
สิ่งที่เกี่ยวกับ popping?

143
00:06:57,830 --> 00:07:00,240
ดังนั้น popping คือการจัดเรียงของ
คู่ที่จะผลักดัน

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
โดยทั่วไปถ้าเรา
ผลักดันและ popping ที่นี่

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
สมมติว่าเราต้องการตอนนี้
ปรากฏองค์ประกอบออกจาก s

169
00:08:07,990 --> 00:08:14,000
ดังนั้นจำผมบอกว่าที่ผ่านมาเป็นกอง
ในครั้งแรกออก LIFO โครงสร้างข้อมูล

170
00:08:14,000 --> 00:08:17,855
ซึ่งองค์ประกอบที่เป็นไปได้
ถูกลบออกจากกอง?

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

172
00:08:21,780 --> 00:08:24,150
คุณคิดว่า 19?

173
00:08:24,150 --> 00:08:25,290
เพราะคุณต้องการจะขวา

174
00:08:25,290 --> 00:08:28,836
19 เป็นองค์ประกอบสุดท้ายที่เราเพิ่มให้กับ
สแต็คเมื่อเราได้ผลักดันองค์ประกอบบน

175
00:08:28,836 --> 00:08:31,210
และมันจะเป็นครั้งแรก
องค์ประกอบที่ได้รับการถอดออก

176
00:08:31,210 --> 00:08:34,780
มันเหมือนกับว่าเรากล่าวว่าวันที่ 28 และ
แล้วเราใส่ 33 ด้านบนของมัน

177
00:08:34,780 --> 00:08:36,659
และเราใส่ 19 ด้านบนของที่

178
00:08:36,659 --> 00:08:40,650
องค์ประกอบเดียวที่เราสามารถนำออกคือ 19

179
00:08:40,650 --> 00:08:45,019
>> ตอนนี้ในแผนภาพที่นี่สิ่งที่ผมทำ
มีการเรียงลำดับของการลบ 19 จากอาร์เรย์

180
00:08:45,019 --> 00:08:46,810
ที่ไม่จริง
สิ่งที่เรากำลังจะทำ

181
00:08:46,810 --> 00:08:48,934
เรากำลังจะไปชนิด
ของแสร้งทำเป็นว่ามันไม่ได้มี

182
00:08:48,934 --> 00:08:51,441
ก็ยังคงมีใน
สถานที่ตั้งของหน่วยความจำที่

183
00:08:51,441 --> 00:08:54,190
แต่เรากำลังจะไม่สนใจมัน
โดยการเปลี่ยนแปลงด้านบนของสแต็คของเรา

184
00:08:54,190 --> 00:08:56,080
จากการเป็น 3-2

185
00:08:56,080 --> 00:08:58,720
ดังนั้นถ้าเราจะผลักดันในขณะนี้
องค์ประกอบอื่นบนกอง

186
00:08:58,720 --> 00:09:00,720
มันมากกว่าจะเขียน 19

187
00:09:00,720 --> 00:09:03,990
>> แต่ขอไม่ผ่านปัญหา
การลบ 19 จากกอง

188
00:09:03,990 --> 00:09:05,830
เราก็สามารถแสร้งทำเป็นว่ามันไม่ได้มี

189
00:09:05,830 --> 00:09:11,107
สำหรับวัตถุประสงค์ของกองมันหายไปถ้า
เราเปลี่ยนด้านบนจะเป็น 2 แทน 3

190
00:09:11,107 --> 00:09:12,690
สิทธิทั้งหมดเพื่อให้เป็นที่สวยมาก

191
00:09:12,690 --> 00:09:15,080
นั่นคือทั้งหมดที่เราต้องทำ
องค์ประกอบที่จะปรากฏออกมา

192
00:09:15,080 --> 00:09:16,090
มาทำกันอีกครั้งเถอะ.

193
00:09:16,090 --> 00:09:18,610
ดังนั้นผมจึงได้เน้นในสีแดงที่นี่เพื่อ
บ่งชี้ว่าเรากำลังทำสายอื่น

194
00:09:18,610 --> 00:09:19,720
เรากำลังจะทำสิ่งเดียวกัน

195
00:09:19,720 --> 00:09:20,803
>> ดังนั้นสิ่งที่จะเกิดขึ้น?

196
00:09:20,803 --> 00:09:23,670
ดีที่เรากำลังจะไปเก็บ
33 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
ดังนั้นสิ่งที่ analogs ของการผลักดันและป๊อปหรือไม่

231
00:10:58,240 --> 00:10:58,740
ขวา

232
00:10:58,740 --> 00:11:01,812
ดังนั้นการผลักดันอีกครั้งคือการเพิ่ม
องค์ประกอบใหม่ในกอง

233
00:11:01,812 --> 00:11:03,770
ในรายการที่เชื่อมโยงว่า
หมายความว่าเรากำลังจะมี

234
00:11:03,770 --> 00:11:07,770
เพื่อสร้างโหนดใหม่ที่เรากำลัง
จะเพิ่มลงในรายการที่เชื่อมโยง

235
00:11:07,770 --> 00:11:10,500
และจากนั้นทำตามขั้นตอนอย่างระมัดระวัง
ที่เราได้ระบุไว้ก่อนหน้านี้

236
00:11:10,500 --> 00:11:16,050
ในรายการที่เชื่อมโยงโดยลำพังเพื่อเพิ่มไปยัง
ห่วงโซ่โดยไม่ทำลายห่วงโซ่

237
00:11:16,050 --> 00:11:18,900
และการสูญเสียหรือ orphaning ใด ๆ
องค์ประกอบของรายการที่เชื่อมโยง

238
00:11:18,900 --> 00:11:21,820
และนั่นก็เป็นสิ่งที่ว่า
หยดเล็ก ๆ น้อย ๆ ของข้อความที่มีการสรุป

239
00:11:21,820 --> 00:11:23,740
และให้มาดู
ที่มันเป็นแผนภาพ

240
00:11:23,740 --> 00:11:24,823
>> ดังนั้นนี่คือรายการที่เชื่อมโยงของเรา

241
00:11:24,823 --> 00:11:26,620
มันพร้อมมีธาตุทั้งสี่

242
00:11:26,620 --> 00:11:30,420
และอื่น ๆ ที่ดีที่สุดที่นี่เป็นของเรา
สแต็คที่มีธาตุทั้งสี่

243
00:11:30,420 --> 00:11:36,030
และขอบอกว่าตอนนี้เราต้องการที่จะ
ผลักดันรายการใหม่บนสแต็คนี้

244
00:11:36,030 --> 00:11:39,792
และเราต้องการที่จะผลักดันใหม่
รายการข้อมูลที่มีค่าคือ 12

245
00:11:39,792 --> 00:11:41,000
ดีสิ่งที่เราจะทำอย่างไร

246
00:11:41,000 --> 00:11:43,420
อย่างแรกที่เรากำลังจะ
พื้นที่ 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
ให้แน่ใจว่าจะตรวจสอบโมฆะ
เพราะถ้าเราได้ null กลับ

250
00:11:52,989 --> 00:11:54,280
มีการเรียงลำดับของปัญหาบางอย่าง

251
00:11:54,280 --> 00:11:57,570
เราไม่ต้องการที่จะ dereference 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 ต่อไปเช่นที่
จะเลื่อนตัวชี้ Trav หนึ่ง

279
00:13:17,510 --> 00:13:19,324
ตำแหน่งที่ไปข้างหน้า

280
00:13:19,324 --> 00:13:21,240
ตอนนี้ที่เรามี
ยึดมั่นในองค์ประกอบแรก

281
00:13:21,240 --> 00:13:24,573
ผ่านตัวชี้ที่เรียกว่ารายการและ
องค์ประกอบที่สองผ่านตัวชี้ที่เรียกว่า

282
00:13:24,573 --> 00:13:28,692
Trav เราสามารถลบได้อย่างปลอดภัยว่า
องค์ประกอบแรกจากกอง

283
00:13:28,692 --> 00:13:30,650
โดยไม่สูญเสียส่วนที่เหลือ
ของห่วงโซ่เพราะเรา

284
00:13:30,650 --> 00:13:32,358
มีวิธีการดู
กับองค์ประกอบที่สอง

285
00:13:32,358 --> 00:13:34,780
ส่งต่อโดยวิธีการ
ตัวชี้ที่เรียกว่า Trav

286
00:13:34,780 --> 00:13:37,100
>> ดังนั้นตอนนี้เราสามารถฟรีโหนดที่

287
00:13:37,100 --> 00:13:38,404
เราสามารถฟรีรายการ

288
00:13:38,404 --> 00:13:41,320
และแล้วสิ่งที่เราต้องทำในขณะนี้คือ
ย้ายรายการที่ต้องชี้ไปที่สถานที่เดียวกัน

289
00:13:41,320 --> 00:13:44,482
Trav ที่ไม่และเราเรียงลำดับของการกลับมา
ที่เราเริ่มต้นก่อนที่เราจะผลักดัน 12

290
00:13:44,482 --> 00:13:45,690
ในสถานที่แรกขวา

291
00:13:45,690 --> 00:13:46,940
ตรงนี้เป็นสิ่งที่เราเป็น

292
00:13:46,940 --> 00:13:48,840
เรามีนี้สแต็คธาตุสี่

293
00:13:48,840 --> 00:13:49,690
เราได้เพิ่มห้า

294
00:13:49,690 --> 00:13:51,910
เราผลักห้า
องค์ประกอบในและจากนั้นเรา

295
00:13:51,910 --> 00:13:55,980
โผล่ว่าส่วนใหญ่เมื่อเร็ว ๆ นี้
เพิ่มองค์ประกอบกลับออก

296
00:13:55,980 --> 00:13:58,816
>> ที่จริงสวยมาก
ทั้งหมดที่มีให้กอง

297
00:13:58,816 --> 00:14:00,190
คุณสามารถใช้พวกเขาเป็นอาร์เรย์

298
00:14:00,190 --> 00:14:01,815
คุณสามารถใช้พวกเขาเป็นรายการที่เชื่อมโยง

299
00:14:01,815 --> 00:14:04,810
มีของหลักสูตรอื่น ๆ
วิธีการที่จะใช้พวกเขาเป็นอย่างดี

300
00:14:04,810 --> 00:14:09,060
โดยทั่วไปเหตุผลที่เราจะใช้
กองคือการรักษาข้อมูลในลักษณะ

301
00:14:09,060 --> 00:14:12,090
ที่เพิ่มเข้ามาเมื่อเร็ว ๆ นี้
องค์ประกอบที่เป็นสิ่งแรกที่เรา

302
00:14:12,090 --> 00:14:14,980
จะต้องการที่จะได้รับกลับมา

303
00:14:14,980 --> 00:14:17,900
ฉันลอยด์ดั๊กนี้เป็น CS50

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