1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: ดังนั้นถ้าคุณได้
ดูวิดีโอบนกอง

3
00:00:07,370 --> 00:00:09,870
นี้อาจจะรู้สึกว่า
เช่นเล็กน้อยของ Deja Vu

4
00:00:09,870 --> 00:00:13,850
มันจะเป็นแนวคิดที่คล้ายกันมาก
เพียงกับบิดเล็กน้อยเกี่ยวกับมัน

5
00:00:13,850 --> 00:00:15,530
เรากำลังจะพูดคุยเกี่ยวกับการรอคิวในขณะนี้

6
00:00:15,530 --> 00:00:19,350
ดังนั้นคิวคล้ายกับสแต็ค,
เป็นชนิดของโครงสร้างข้อมูลอื่น

7
00:00:19,350 --> 00:00:22,412
ที่เราสามารถใช้ในการรักษา
ข้อมูลในทางที่จัด

8
00:00:22,412 --> 00:00:24,120
คล้ายกับสแต็ค,
จะสามารถดำเนินการ

9
00:00:24,120 --> 00:00:27,000
เป็นอาร์เรย์หรือรายการที่เชื่อมโยง

10
00:00:27,000 --> 00:00:30,320
ซึ่งแตกต่างจากกองกฎ
ที่เราใช้ในการตรวจสอบ

11
00:00:30,320 --> 00:00:34,210
เมื่อสิ่งที่ได้รับการเพิ่มและลบออกจาก
คิวมีความแตกต่างกันเล็กน้อย

12
00:00:34,210 --> 00:00:36,590
>> ซึ่งแตกต่างจากกองที่
เป็นโครงสร้าง LIFO ที่

13
00:00:36,590 --> 00:00:45,610
สุดท้ายในออกครั้งแรกคิวเป็นแบบ FIFO
โครงสร้าง FIFO ครั้งแรกในครั้งแรกออกมา

14
00:00:45,610 --> 00:00:49,320
ตอนนี้คิวคุณอาจ
มีเปรียบเทียบกับคิว

15
00:00:49,320 --> 00:00:52,820
หากคุณเคยอยู่ในสายที่
สวนสนุกหรือธนาคาร

16
00:00:52,820 --> 00:00:56,430
มีการเรียงลำดับของความเป็นธรรม
โครงสร้างการดำเนินการ

17
00:00:56,430 --> 00:00:59,160
คนแรกในสายที่
ธนาคารเป็นคนแรก

18
00:00:59,160 --> 00:01:00,760
ผู้ที่ได้รับเพื่อพูดคุยกับหมอดู

19
00:01:00,760 --> 00:01:03,522
>> มันจะเรียงลำดับของการแข่งขัน
ไปที่ด้านล่างถ้าวิธีเดียวที่

20
00:01:03,522 --> 00:01:06,730
คุณได้พูดคุยกับพนักงานที่ได้
ธนาคารจะเป็นคนสุดท้ายที่อยู่ในแนวเดียวกัน

21
00:01:06,730 --> 00:01:09,146
ทุกคนมักจะต้องการ
จะเป็นคนสุดท้ายที่อยู่ในแถว

22
00:01:09,146 --> 00:01:12,580
และคนที่อยู่ที่นั่นเป็นครั้งแรก
ที่ได้รับการรอในขณะที่

23
00:01:12,580 --> 00:01:14,715
อาจจะมีเวลาหลายชั่วโมง
และชั่วโมงและชั่วโมง

24
00:01:14,715 --> 00:01:17,590
ก่อนที่พวกเขามีโอกาสที่จะเป็นจริง
เบิกเงินใด ๆ ที่ธนาคาร

25
00:01:17,590 --> 00:01:22,510
และการรอคิวเพื่อให้มีการจัดเรียงของ
ความเป็นธรรมโครงสร้างการดำเนินการ

26
00:01:22,510 --> 00:01:25,780
แต่นั่นไม่ได้หมายความว่า
ที่กองเป็นสิ่งที่ไม่ดีเพียง

27
00:01:25,780 --> 00:01:28,160
ที่รอคิวเป็นวิธีที่จะทำมันอีก

28
00:01:28,160 --> 00:01:32,420
ดังนั้นอีกครั้งคิวเป็นครั้งแรกในครั้งแรก
ออกเมื่อเทียบกับสแต็คที่สุดท้ายในการ

29
00:01:32,420 --> 00:01:34,440
ก่อนออก

30
00:01:34,440 --> 00:01:36,190
คล้ายกับสแต็ค,
เรามีสองการดำเนินงาน

31
00:01:36,190 --> 00:01:38,470
ที่เราจะได้ดำเนินการเกี่ยวกับการรอคิว

32
00:01:38,470 --> 00:01:43,910
ชื่อเป็น Enqueue ซึ่งก็คือการเพิ่ม
องค์ประกอบใหม่ที่ส่วนท้ายของคิว

33
00:01:43,910 --> 00:01:47,330
และ dequeue ซึ่งเป็น
การลบที่เก่าแก่ที่สุด

34
00:01:47,330 --> 00:01:49,670
องค์ประกอบจากด้านหน้าของคิว

35
00:01:49,670 --> 00:01:53,600
ดังนั้นเรากำลังจะเพิ่มองค์ประกอบ
เข้าสู่ท้ายของคิว

36
00:01:53,600 --> 00:01:57,220
และเรากำลังจะลบองค์ประกอบ
จากด้านหน้าของคิว

37
00:01:57,220 --> 00:02:00,790
อีกครั้งกับสแต็คเราได้เพิ่ม
องค์ประกอบที่ด้านบนสุดของสแต็ค

38
00:02:00,790 --> 00:02:03,380
และลบองค์ประกอบ
จากด้านบนของสแต็ค

39
00:02:03,380 --> 00:02:07,570
ดังนั้นด้วย Enqueue ก็เพิ่มให้
ท้ายที่สุดออกจากด้านหน้า

40
00:02:07,570 --> 00:02:10,639
ดังนั้นสิ่งที่เก่าแก่ที่สุดในการมี
มักจะเป็นสิ่งต่อไปที่

41
00:02:10,639 --> 00:02:13,620
ที่จะออกมาถ้าเราพยายาม
และบางสิ่งบางอย่าง dequeue

42
00:02:13,620 --> 00:02:18,330
>> ดังนั้นอีกครั้งกับคิวที่เราสามารถทำได้
การใช้งานอาร์เรย์ตาม

43
00:02:18,330 --> 00:02:20,110
และการใช้งานที่เชื่อมโยงตามรายการ

44
00:02:20,110 --> 00:02:24,620
เราจะเริ่มต้นอีกครั้งกับ
การใช้งานอาร์เรย์ตาม

45
00:02:24,620 --> 00:02:27,070
ความหมายโครงสร้าง
มีลักษณะคล้ายสวย

46
00:02:27,070 --> 00:02:30,720
เรามีอาร์เรย์อื่น
มีข้อมูลค่าชนิด

47
00:02:30,720 --> 00:02:32,690
เพื่อที่จะสามารถถือชนิดข้อมูลโดยพลการ

48
00:02:32,690 --> 00:02:35,570
เรากำลังอีกครั้งจะใช้
จำนวนเต็มในตัวอย่างนี้

49
00:02:35,570 --> 00:02:39,830
>> และเช่นเดียวกับเรา
การดำเนินการสแต็คอาร์เรย์ตาม

50
00:02:39,830 --> 00:02:42,340
เพราะเรากำลังใช้
อาร์เรย์เราจำเป็นต้อง

51
00:02:42,340 --> 00:02:46,850
มีข้อ จำกัด ว่าชนิด C
บังคับใช้ของเราซึ่งก็คือเรา

52
00:02:46,850 --> 00:02:51,670
ไม่ได้มีชีวิตชีวาในของเรา
ความสามารถในการเติบโตและหดอาร์เรย์

53
00:02:51,670 --> 00:02:55,710
เราต้องตัดสินใจที่จุดเริ่มต้น
สิ่งที่เป็นจำนวนสูงสุดของสิ่งที่

54
00:02:55,710 --> 00:02:59,300
ที่เราสามารถใส่ลงไปในนี้
คิวและในกรณีนี้

55
00:02:59,300 --> 00:03:02,070
กำลังการผลิตจะเป็นปอนด์บาง
ที่กำหนดไว้คงที่ในรหัสของเรา

56
00:03:02,070 --> 00:03:05,430
และเพื่อวัตถุประสงค์นี้
วิดีโอกำลังการผลิตเป็นไปได้ 10

57
00:03:05,430 --> 00:03:07,690
>> เราจำเป็นต้องติดตาม
ด้านหน้าของคิว

58
00:03:07,690 --> 00:03:11,160
ดังนั้นเราจึงได้รู้ว่าที่องค์ประกอบ
เราต้องการที่จะ dequeue,

59
00:03:11,160 --> 00:03:15,070
และเรายังต้องติดตาม
บางสิ่งบางอย่าง else-- จำนวนขององค์ประกอบ

60
00:03:15,070 --> 00:03:16,690
ที่เรามีอยู่ในคิวของเรา

61
00:03:16,690 --> 00:03:19,360
ขอให้สังเกตเราไม่ได้ติดตาม
ของการสิ้นสุดของคิวเพียง

62
00:03:19,360 --> 00:03:21,150
ขนาดของคิว

63
00:03:21,150 --> 00:03:24,310
และเหตุผลที่จะหวังว่า
เป็นบิตที่ชัดเจนในช่วงเวลาที่

64
00:03:24,310 --> 00:03:26,143
เมื่อเราได้เสร็จสิ้น
การกำหนดประเภทนี้

65
00:03:26,143 --> 00:03:29,080
เรามีชนิดข้อมูลใหม่
ที่เรียกว่าคิวที่เราสามารถทำได้ในขณะนี้

66
00:03:29,080 --> 00:03:30,630
ประกาศตัวแปรของชนิดข้อมูลที่

67
00:03:30,630 --> 00:03:35,350
และค่อนข้างพลุกพล่านฉันได้ตัดสินใจ
ที่จะเรียกคิวคิวนี้ตัวอักษร

68
00:03:35,350 --> 00:03:38,090
คิวแทนชนิดข้อมูลคิว

69
00:03:38,090 --> 00:03:39,600
>> ดังนั้นนี่คือคิวของเรา

70
00:03:39,600 --> 00:03:40,700
มันเป็นโครงสร้าง

71
00:03:40,700 --> 00:03:45,730
มันมีสมาชิกสามคนหรือสาม
เขตข้อมูลอาร์เรย์ของความจุขนาด

72
00:03:45,730 --> 00:03:47,340
ในกรณีนี้กำลังการผลิตอยู่ที่ 10

73
00:03:47,340 --> 00:03:49,580
และอาเรย์นี้
ไปถือจำนวนเต็ม

74
00:03:49,580 --> 00:03:55,240
สีเขียวเป็นด้านหน้าของคิวของเราที่
องค์ประกอบถัดไปจะถูกลบออกและสีแดง

75
00:03:55,240 --> 00:03:58,610
จะเป็นขนาดของคิว
วิธีการหลายองค์ประกอบที่มีอยู่ในปัจจุบัน

76
00:03:58,610 --> 00:04:01,190
ที่มีอยู่ในคิว

77
00:04:01,190 --> 00:04:05,300
ดังนั้นถ้าเราพูด q.front เท่ากับ
0 และขนาด q.size เท่ากับ 0--

78
00:04:05,300 --> 00:04:07,120
เรากำลังวาง 0s ลงในเขตข้อมูลเหล่านั้น

79
00:04:07,120 --> 00:04:11,070
และที่จุดนี้เราสวยมาก
พร้อมที่จะเริ่มทำงานกับคิวของเรา

80
00:04:11,070 --> 00:04:14,140
>> ดังนั้นการดำเนินการครั้งแรกที่เราสามารถทำได้
ดำเนินการคือการ enqueue บางสิ่งบางอย่าง

81
00:04:14,140 --> 00:04:16,860
เพื่อเพิ่มองค์ประกอบใหม่ใน
ในตอนท้ายของคิว

82
00:04:16,860 --> 00:04:19,089
ดีทำในสิ่งที่เราจำเป็นต้อง
ทำอย่างไรในกรณีทั่วไป?

83
00:04:19,089 --> 00:04:23,690
ดีฟังก์ชั่นนี้ enqueue ความต้องการ
ที่จะยอมรับตัวชี้ไปยังคิวของเรา

84
00:04:23,690 --> 00:04:26,370
อีกครั้งถ้าเราได้ประกาศ
คิวของเราทั่วโลก

85
00:04:26,370 --> 00:04:29,490
เราจะไม่ต้องทำเช่นนี้
จำเป็นต้อง แต่โดยทั่วไปเรา

86
00:04:29,490 --> 00:04:32,330
ต้องยอมรับคำแนะนำ
โครงสร้างข้อมูล

87
00:04:32,330 --> 00:04:35,040
เช่นนี้เพราะมิฉะนั้น,
เรากำลังผ่าน value-- เรา

88
00:04:35,040 --> 00:04:38,140
ผ่านในสำเนาของคิว
และเพื่อให้เราไม่ได้มีการเปลี่ยนแปลงจริง

89
00:04:38,140 --> 00:04:41,050
คิวที่เราตั้งใจที่จะเปลี่ยน

90
00:04:41,050 --> 00:04:44,860
>> สิ่งอื่น ๆ ที่จะต้องทำคือการยอมรับ
องค์ประกอบของข้อมูลประเภทที่เหมาะสม

91
00:04:44,860 --> 00:04:46,818
อีกครั้งในกรณีนี้ก็
จะเป็นจำนวนเต็ม

92
00:04:46,818 --> 00:04:49,330
แต่คุณสามารถทำได้โดยพลการ
ประกาศชนิดข้อมูลเป็นค่า

93
00:04:49,330 --> 00:04:51,160
และการใช้งานนี้มากขึ้นโดยทั่วไป

94
00:04:51,160 --> 00:04:56,030
นั่นเป็นองค์ประกอบที่เราต้องการ enqueue,
เราต้องการที่จะเพิ่มถึงจุดสิ้นสุดของคิว

95
00:04:56,030 --> 00:04:58,573
แล้วเราจริงต้องการ
วางข้อมูลที่อยู่ในคิว

96
00:04:58,573 --> 00:05:01,490
ในกรณีนี้วางไว้ใน
ตำแหน่งที่ถูกต้องของอาร์เรย์ของเรา

97
00:05:01,490 --> 00:05:05,040
แล้วเราต้องการที่จะเปลี่ยนขนาด
ของคิวกี่องค์ประกอบเรา

98
00:05:05,040 --> 00:05:07,050
ในขณะนี้มี

99
00:05:07,050 --> 00:05:07,990
>> ดังนั้นขอเริ่มต้น

100
00:05:07,990 --> 00:05:10,890
นี่คืออีกครั้งที่ทั่วไป
รูปแบบการประกาศฟังก์ชัน

101
00:05:10,890 --> 00:05:13,980
สำหรับสิ่งที่ Enqueue อาจมีลักษณะเช่น

102
00:05:13,980 --> 00:05:14,910
และที่นี่เราไป

103
00:05:14,910 --> 00:05:18,335
ลอง enqueue จำนวน
28 เข้าไปในคิว

104
00:05:18,335 --> 00:05:19,460
ดังนั้นสิ่งที่เราจะทำอย่างไร

105
00:05:19,460 --> 00:05:23,390
ดีด้านหน้าของคิวของเราเป็น
ที่ 0 และขนาดของคิวของเรา

106
00:05:23,390 --> 00:05:29,680
อยู่ที่ 0 และเพื่อให้เราอาจจะต้องการที่จะนำ
หมายเลข 28 ในหลายองค์ประกอบอาร์เรย์

107
00:05:29,680 --> 00:05:31,124
0 ใช่มั้ย?

108
00:05:31,124 --> 00:05:32,540
ดังนั้นเราจึงได้วางไว้ในขณะนี้ว่าในการมี

109
00:05:32,540 --> 00:05:34,820
ดังนั้นตอนนี้สิ่งที่เราจำเป็นต้องเปลี่ยน?

110
00:05:34,820 --> 00:05:37,090
เราไม่ต้องการที่จะเปลี่ยน
ด้านหน้าของคิว

111
00:05:37,090 --> 00:05:40,850
เพราะเราต้องการที่จะรู้ว่าสิ่งที่องค์ประกอบ
เราอาจจะต้อง dequeue ภายหลัง

112
00:05:40,850 --> 00:05:44,020
ดังนั้นเหตุผลที่เรามีหน้ามี
คือการจัดเรียงของตัวบ่งชี้ของสิ่งที่เป็น

113
00:05:44,020 --> 00:05:46,439
สิ่งที่เก่าแก่ที่สุดในอาร์เรย์

114
00:05:46,439 --> 00:05:49,730
ดีสิ่งที่เก่าแก่ที่สุดใน array-- ใน
ความเป็นจริงมีเพียงสิ่งเดียวในอาร์เรย์ที่เหมาะสม

115
00:05:49,730 --> 00:05:53,540
now-- เป็น 28 ซึ่งเป็น
ในสถานที่อาร์เรย์ 0

116
00:05:53,540 --> 00:05:56,160
ดังนั้นเราจึงไม่ต้องการที่จะ
เปลี่ยนที่หมายเลขสีเขียว

117
00:05:56,160 --> 00:05:57,910
เนื่องจากว่าเป็นองค์ประกอบที่เก่าแก่ที่สุด

118
00:05:57,910 --> 00:06:00,510
แต่เราต้องการที่จะเปลี่ยนขนาด

119
00:06:00,510 --> 00:06:04,110
ดังนั้นในกรณีนี้เราจะ
ขนาดที่เพิ่มขึ้นถึง 1

120
00:06:04,110 --> 00:06:08,430
>> ตอนนี้เป็นประเภททั่วไปของความคิดในการที่
องค์ประกอบถัดไปจะไปในคิว

121
00:06:08,430 --> 00:06:12,310
คือการเพิ่มตัวเลขทั้งสอง
ร่วมกันด้านหน้าและขนาด

122
00:06:12,310 --> 00:06:16,390
และที่จะบอกคุณที่ต่อไป
องค์ประกอบในคิวจะไป

123
00:06:16,390 --> 00:06:18,130
ดังนั้นตอนนี้ขอ enqueue หมายเลขอื่น

124
00:06:18,130 --> 00:06:20,250
ลอง enqueue 33

125
00:06:20,250 --> 00:06:24,480
ดังนั้น 33 จะไปลงใน
สถานที่ตั้งของอาร์เรย์ 0 บวก 1

126
00:06:24,480 --> 00:06:26,840
ดังนั้นในกรณีนี้ก็จะ
ที่จะเข้าไปในสถานที่อาร์เรย์ 1,

127
00:06:26,840 --> 00:06:29,500
และตอนนี้ขนาดของคิวของเราคือ 2

128
00:06:29,500 --> 00:06:31,840
>> อีกครั้งที่เราไม่ได้เปลี่ยน
ด้านหน้าของคิวของเรา

129
00:06:31,840 --> 00:06:34,730
เพราะวันที่ 28 ยังคงเป็น
องค์ประกอบที่เก่าแก่ที่สุดและเรา

130
00:06:34,730 --> 00:06:38,220
ต้องการ to-- เมื่อเราได้รับในที่สุด
เพื่อ dequeuing ลบองค์ประกอบ

131
00:06:38,220 --> 00:06:43,300
จากคิวนี้เราต้องการที่จะรู้
องค์ประกอบที่เก่าแก่ที่สุดคือ

132
00:06:43,300 --> 00:06:48,620
และเพื่อให้เรามักจะต้องรักษา
ตัวบ่งชี้ที่บางส่วนของที่เป็น

133
00:06:48,620 --> 00:06:50,410
ดังนั้นสิ่งที่ 0 จะมีสำหรับ

134
00:06:50,410 --> 00:06:52,910
นั่นคือสิ่งที่ด้านหน้าจะมีสำหรับ

135
00:06:52,910 --> 00:06:55,022
>> ลองในองค์ประกอบของ Enqueue อีกหนึ่ง 19

136
00:06:55,022 --> 00:06:56,980
ฉันแน่ใจว่าคุณสามารถคาดเดา
19 ที่จะไป

137
00:06:56,980 --> 00:06:59,860
มันจะไปลง
สถานที่ตั้งจำนวน 2 อาร์เรย์

138
00:06:59,860 --> 00:07:01,570
นั่นเป็นบวก 2 0

139
00:07:01,570 --> 00:07:03,199
และตอนนี้ขนาดของคิวของเราคือ 3

140
00:07:03,199 --> 00:07:04,240
เรามี 3 องค์ประกอบในนั้น

141
00:07:04,240 --> 00:07:08,490
ดังนั้นถ้าเราจะและเราจะไม่
ไปทางขวาตอนนี้ enqueue องค์ประกอบอื่น

142
00:07:08,490 --> 00:07:11,370
มันจะไปในสถานที่อาร์เรย์
3 จำนวนและขนาดของคิวของเรา

143
00:07:11,370 --> 00:07:13,160
จะเป็น 4

144
00:07:13,160 --> 00:07:15,279
ดังนั้นเราจึงได้ enqueued หลายองค์ประกอบในขณะนี้

145
00:07:15,279 --> 00:07:16,570
ตอนนี้ขอเริ่มต้นที่จะลบออก

146
00:07:16,570 --> 00:07:19,450
ลอง dequeue พวกเขาจากคิว

147
00:07:19,450 --> 00:07:23,340
>> ดังนั้นคล้ายกับป๊อปอัพซึ่งเป็นประเภท
อนาล็อกนี้สำหรับกอง

148
00:07:23,340 --> 00:07:26,180
dequeue ต้องการที่จะยอมรับ
ตัวชี้ไปยัง queue-- อีกครั้ง

149
00:07:26,180 --> 00:07:28,140
เว้นแต่จะประกาศทั่วโลก

150
00:07:28,140 --> 00:07:31,610
ตอนนี้เราต้องการที่จะเปลี่ยนสถานที่
ด้านหน้าของคิว

151
00:07:31,610 --> 00:07:35,050
ซึ่งเป็นที่ที่จัดเรียงของมันมา
ลงเล่นที่ตัวแปรด้านหน้า

152
00:07:35,050 --> 00:07:37,310
เพราะเมื่อเราลบ
องค์ประกอบที่เราต้องการ

153
00:07:37,310 --> 00:07:40,720
ที่จะย้ายไปยังองค์ประกอบที่เก่าแก่ที่สุดต่อไป

154
00:07:40,720 --> 00:07:44,180
>> จากนั้นเราก็ต้องการที่จะลดลง
ขนาดของคิว

155
00:07:44,180 --> 00:07:47,130
แล้วเราต้องการที่จะส่งกลับค่า
ที่ถูกเอาออกจากคิว

156
00:07:47,130 --> 00:07:48,921
อีกครั้งที่เราไม่ได้ต้องการเพียงแค่ทิ้งมัน

157
00:07:48,921 --> 00:07:51,170
เราน่าจะมีการสกัด
ได้จาก queue-- ที่เรากำลัง

158
00:07:51,170 --> 00:07:54,170
dequeuing เพราะเราดูแลเกี่ยวกับเรื่องนี้

159
00:07:54,170 --> 00:08:01,080
ดังนั้นเราจึงต้องการฟังก์ชั่นนี้เพื่อกลับ
องค์ประกอบข้อมูลค่าชนิด

160
00:08:01,080 --> 00:08:04,360
อีกครั้งในกรณีนี้ค่าเป็นจำนวนเต็ม

161
00:08:04,360 --> 00:08:05,670
>> ดังนั้นตอนนี้ขอ dequeue บางสิ่งบางอย่าง

162
00:08:05,670 --> 00:08:09,310
ลองลบองค์ประกอบจากคิวที่

163
00:08:09,310 --> 00:08:15,970
ถ้าเราบอก int x เท่ากับ & Q, เครื่องหมาย q--
อีกครั้งที่ชี้ไปยังข้อมูลคิวนี้

164
00:08:15,970 --> 00:08:20,177
structure-- สิ่งที่องค์ประกอบ
เป็นไปได้ dequeued?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
ในกรณีนี้เพราะมันเป็นครั้งแรก
ในครั้งแรกจากโครงสร้างข้อมูลแบบ FIFO,

167
00:08:29,480 --> 00:08:33,690
สิ่งแรกที่เราใส่ลงไปในนี้
คิว 28 และอื่น ๆ ในกรณีนี้

168
00:08:33,690 --> 00:08:37,245
เรากำลังจะใช้เวลา 28 ออกจาก
คิวไม่ได้ 19 ซึ่งเป็นสิ่งที่

169
00:08:37,245 --> 00:08:38,870
เราจะได้ทำถ้านี่เป็นกอง

170
00:08:38,870 --> 00:08:42,220
เรากำลังจะไปใช้เวลา 28 ออกจากคิว

171
00:08:42,220 --> 00:08:44,960
>> คล้ายกับสิ่งที่เราทำกับ
กองเราไม่จริง

172
00:08:44,960 --> 00:08:47,345
จะลบ 28
จากคิวของตัวเอง

173
00:08:47,345 --> 00:08:49,470
เราเพียงแค่จะไปชนิด
ของแสร้งทำเป็นว่ามันไม่ได้มี

174
00:08:49,470 --> 00:08:51,678
ดังนั้นก็จะอยู่ที่นั่น
ในหน่วยความจำ แต่เราเพียงแค่

175
00:08:51,678 --> 00:08:57,820
ไปชนิดไม่สนใจมันโดยการย้าย
อีกสองด้านของข้อมูลคิวของเรา

176
00:08:57,820 --> 00:08:58,830
โครงสร้าง

177
00:08:58,830 --> 00:09:00,230
เรากำลังจะเปลี่ยนหน้า

178
00:09:00,230 --> 00:09:04,290
Q.front คือตอนนี้ไป
เป็น 1 เพราะที่อยู่ในขณะนี้

179
00:09:04,290 --> 00:09:07,740
องค์ประกอบที่เก่าแก่ที่สุดที่เรามีในของเรา
คิวเพราะเราได้ลบแล้ว 28

180
00:09:07,740 --> 00:09:10,460
ซึ่งเป็นองค์ประกอบที่เก่าแก่ที่สุดในอดีต

181
00:09:10,460 --> 00:09:13,540
>> และตอนนี้เราต้องการที่จะเปลี่ยน
ขนาดของคิว

182
00:09:13,540 --> 00:09:15,780
สององค์ประกอบแทนสาม

183
00:09:15,780 --> 00:09:20,450
จำได้ว่าก่อนหน้านี้ตอนนี้ผมบอกว่าเมื่อเรา
ต้องการเพิ่มองค์ประกอบคิว

184
00:09:20,450 --> 00:09:26,000
เราใส่ไว้ในตำแหน่งอาร์เรย์
ซึ่งเป็นผลรวมของด้านหน้าและขนาด

185
00:09:26,000 --> 00:09:29,050
ดังนั้นในกรณีนี้เราก็ยังคงวาง
มันองค์ประกอบถัดไปในคิว

186
00:09:29,050 --> 00:09:33,360
ในสถานที่อาร์เรย์ 3 และ
เราจะเห็นว่าในครั้งที่สอง

187
00:09:33,360 --> 00:09:35,730
>> ดังนั้นเราจึงได้ตอนนี้ dequeued ของเรา
องค์ประกอบแรกจากคิว

188
00:09:35,730 --> 00:09:36,480
มาทำกันอีกครั้งเถอะ.

189
00:09:36,480 --> 00:09:38,696
ลองเอาอีก
องค์ประกอบจากคิว

190
00:09:38,696 --> 00:09:42,400
ในกรณีที่เก่าแก่ที่สุดในปัจจุบัน
องค์ประกอบที่เป็นที่ตั้งอาร์เรย์ 1

191
00:09:42,400 --> 00:09:44,220
นั่นคือสิ่งที่บอกเรา q.front

192
00:09:44,220 --> 00:09:46,980
ที่กล่องสีเขียวบอกเราว่า
นั่นคือองค์ประกอบที่เก่าแก่ที่สุด

193
00:09:46,980 --> 00:09:49,310
ดังนั้น x จะกลายเป็น 33

194
00:09:49,310 --> 00:09:52,130
เราจะเพียงแค่ชนิดของลืม
33 ที่มีอยู่ในอาร์เรย์

195
00:09:52,130 --> 00:09:55,100
และเราจะบอกว่าตอนนี้
องค์ประกอบที่เก่าแก่ที่สุดใหม่ในคิว

196
00:09:55,100 --> 00:09:58,900
เป็นที่ตั้งของอาร์เรย์ที่ 2 และขนาด
ของคิวจำนวนขององค์ประกอบ

197
00:09:58,900 --> 00:10:02,152
ที่เรามีในคิว 1

198
00:10:02,152 --> 00:10:05,110
ตอนนี้ขอ enqueue บางสิ่งบางอย่างและฉัน
การจัดเรียงของให้นี้ไปที่สองที่ผ่านมา

199
00:10:05,110 --> 00:10:10,340
แต่ถ้าเราต้องการที่จะนำเข้ามาใน 40
คิวที่ 40 ที่จะไป?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
ดีที่เราได้รับการวางไว้
ใน q.front ขนาดบวกคิว

202
00:10:17,730 --> 00:10:20,850
และดังนั้นจึงทำให้ความรู้สึกที่
จริงที่จะนำ 40 ที่นี่

203
00:10:20,850 --> 00:10:22,840
ตอนนี้สังเกตเห็นว่าที่
บางจุดที่เรากำลังจะ

204
00:10:22,840 --> 00:10:27,980
ที่จะได้รับในตอนท้ายของ
อาร์เรย์ของเราภายในของคิว

205
00:10:27,980 --> 00:10:32,010
แต่ที่จางหายไป 28 และ 33--
พวกเขากำลังจริงในทางเทคนิค

206
00:10:32,010 --> 00:10:33,300
เปิดช่องว่างใช่มั้ย?

207
00:10:33,300 --> 00:10:36,040
ดังนั้นเราอาจ eventually--
ว่ากฎของการเพิ่ม

208
00:10:36,040 --> 00:10:40,390
ทั้งสอง together-- ในที่สุดเราก็อาจจะ
ต้อง mod ตามขนาดของความจุ

209
00:10:40,390 --> 00:10:41,410
เพื่อให้เราสามารถห่อรอบ

210
00:10:41,410 --> 00:10:43,620
>> ดังนั้นถ้าเราได้รับไปยังองค์ประกอบ
เลขที่ 10 ถ้าเรา

211
00:10:43,620 --> 00:10:48,790
แทนที่มันในองค์ประกอบจำนวน 10 เราต้องการ
จริงใส่ไว้ในตำแหน่งอาร์เรย์ 0

212
00:10:48,790 --> 00:10:50,997
และถ้าเรากำลังจะไป
อาร์เรย์ location-- ขอโทษนะ

213
00:10:50,997 --> 00:10:53,080
ถ้าเราเพิ่มพวกเขาขึ้นมาด้วยกัน
และเราได้ไปที่หมายเลข

214
00:10:53,080 --> 00:10:56,330
11 จะเป็นที่ที่เราจะต้องใส่
มันซึ่งไม่อยู่ใน array-- นี้

215
00:10:56,330 --> 00:10:58,200
มันจะออกไปจากตัว

216
00:10:58,200 --> 00:11:03,367
เราสามารถ mod 10 และวาง
ไว้ในตำแหน่งอาร์เรย์ 1

217
00:11:03,367 --> 00:11:04,450
เพื่อให้เป็นวิธีการทำงานของคิว

218
00:11:04,450 --> 00:11:08,540
พวกเขากำลังเสมอไปที่จะไปจากทางด้านซ้าย
ไปทางขวาและอาจจะห่อรอบ

219
00:11:08,540 --> 00:11:11,280
และคุณรู้ว่าพวกเขากำลัง
เต็มถ้าขนาดกล่องสีแดง

220
00:11:11,280 --> 00:11:13,710
กลายเป็นเท่ากับกำลังการผลิต

221
00:11:13,710 --> 00:11:16,720
ดังนั้นหลังจากที่เราได้เพิ่ม 40 ไปยัง
คิวดีทำในสิ่งที่เราต้องทำอย่างไร

222
00:11:16,720 --> 00:11:19,890
ดีองค์ประกอบที่เก่าแก่ที่สุด
ในคิวยังคงที่ 19

223
00:11:19,890 --> 00:11:21,990
ดังนั้นเราจึงไม่ต้องการที่จะเปลี่ยน
ด้านหน้าของคิว

224
00:11:21,990 --> 00:11:23,820
แต่ตอนนี้เรามีสอง
องค์ประกอบในคิว

225
00:11:23,820 --> 00:11:28,710
และเพื่อให้เราต้องการที่จะเพิ่ม
ขนาดของเรา 1-2

226
00:11:28,710 --> 00:11:31,820
>> ที่สวยมากด้วย
การทำงานร่วมกับคิวอาเรย์ที่ใช้

227
00:11:31,820 --> 00:11:33,630
และคล้ายกับกอง
นอกจากนี้ยังมีวิธีการที่

228
00:11:33,630 --> 00:11:36,450
ที่จะใช้คิวเป็นรายการที่เชื่อมโยง

229
00:11:36,450 --> 00:11:40,150
ตอนนี้ถ้าโครงสร้างข้อมูลประเภทนี้
มีลักษณะที่คุ้นเคยกับคุณมันเป็น

230
00:11:40,150 --> 00:11:43,780
มันไม่ได้เป็นรายการที่เชื่อมโยงโดยลำพัง
มันเป็นรายการที่เชื่อมโยงเป็นทวีคูณ

231
00:11:43,780 --> 00:11:46,790
และตอนนี้เป็นกันก็คือ
จริงที่เป็นไปได้ในการดำเนินการ

232
00:11:46,790 --> 00:11:50,160
คิวเป็นรายการที่เชื่อมโยงโดยลำพัง แต่
ผมคิดว่าในแง่ของการสร้างภาพ

233
00:11:50,160 --> 00:11:53,350
จริง ๆ แล้วมันอาจจะช่วยในการดู
นี้เป็นรายการที่เชื่อมโยงเป็นทวีคูณ

234
00:11:53,350 --> 00:11:56,850
แต่มันก็เป็นไปได้ที่จะแน่นอน
ทำเช่นนี้เป็นรายการที่เชื่อมโยงโดยลำพัง

235
00:11:56,850 --> 00:12:00,110
>> ดังนั้นเรามาดูได้ที่
สิ่งนี้อาจจะมีลักษณะ

236
00:12:00,110 --> 00:12:02,750
ถ้าเราต้องการที่จะ enquue--
ดังนั้นตอนนี้เราอีกครั้ง

237
00:12:02,750 --> 00:12:05,360
เปลี่ยนเป็นรายการที่เชื่อมโยง
รูปแบบตามที่นี่

238
00:12:05,360 --> 00:12:08,420
ถ้าเราต้องการที่จะ enqueue เราต้องการ
เพื่อเพิ่มองค์ประกอบใหม่ที่ดี

239
00:12:08,420 --> 00:12:09,730
ทำในสิ่งที่เราต้องทำอย่างไร

240
00:12:09,730 --> 00:12:12,770
ดีแรกของทั้งหมดเพราะ
เรากำลังเพิ่มไปยังจุดสิ้นสุด

241
00:12:12,770 --> 00:12:15,520
และลบจาก
จุดเริ่มต้นที่เราอาจ

242
00:12:15,520 --> 00:12:20,050
ต้องการที่จะรักษาตัวชี้ไปยังทั้งสอง
หัวและหางของรายการที่เชื่อมโยงหรือไม่

243
00:12:20,050 --> 00:12:22,660
หางเป็นระยะอีก
ในตอนท้ายของรายการที่เชื่อมโยง

244
00:12:22,660 --> 00:12:24,496
องค์ประกอบสุดท้ายในรายการที่เชื่อมโยง

245
00:12:24,496 --> 00:12:26,620
และสิ่งเหล่านี้อาจจะ
อีกครั้งจะเป็นประโยชน์กับเรา

246
00:12:26,620 --> 00:12:28,477
หากพวกเขาเป็นตัวแปรทั่วโลก

247
00:12:28,477 --> 00:12:31,060
แต่ตอนนี้ถ้าเราต้องการที่จะเพิ่มใหม่
องค์ประกอบสิ่งที่เราจะต้องทำอย่างไร

248
00:12:31,060 --> 00:12:35,262
สิ่งที่เราเพียง [? Malak?] หรือแบบไดนามิก
จัดสรรโหนดใหม่ของเราเพื่อตัวเราเอง

249
00:12:35,262 --> 00:12:38,220
และจากนั้นก็เช่นเดียวกับเมื่อเราเพิ่มใด ๆ
องค์ประกอบเรารายการที่เชื่อมโยงทวีคูณ

250
00:12:38,220 --> 00:12:40,410
เพียงแค่มีการจัดเรียง of--
ผู้ที่ผ่านขั้นตอนที่สามที่นี่

251
00:12:40,410 --> 00:12:43,330
เป็นเพียงข้อมูลเกี่ยวกับการเคลื่อนย้าย
คำแนะนำในทางที่ถูกต้อง

252
00:12:43,330 --> 00:12:46,710
เพื่อให้องค์ประกอบที่จะได้รับเพิ่ม
ห่วงโซ่โดยไม่ทำลายห่วงโซ่

253
00:12:46,710 --> 00:12:49,580
หรือการเรียงลำดับของความผิดพลาดบางอย่าง
หรือมีการเรียงลำดับของการเกิดอุบัติเหตุบางอย่าง

254
00:12:49,580 --> 00:12:54,505
เกิดขึ้นโดยที่เราไม่ได้ตั้งใจ
เด็กกำพร้าองค์ประกอบบางอย่างของคิวของเรา

255
00:12:54,505 --> 00:12:55,880
นี่คือสิ่งที่อาจมีลักษณะเหมือน

256
00:12:55,880 --> 00:13:00,980
เราต้องการที่จะเพิ่มองค์ประกอบ
10 ที่ส่วนท้ายของคิวนี้

257
00:13:00,980 --> 00:13:03,380
ดังนั้นองค์ประกอบที่เก่าแก่ที่สุดที่นี่
เป็นตัวแทนจากหัว

258
00:13:03,380 --> 00:13:06,800
นั่นเป็นสิ่งแรกที่เราใส่
ในนี้คิวสมมุติที่นี่

259
00:13:06,800 --> 00:13:10,430
และหาง, 13, เป็นส่วนใหญ่
องค์ประกอบที่เพิ่งเพิ่ม

260
00:13:10,430 --> 00:13:17,030
ดังนั้นถ้าเราต้องการที่จะเข้ามาใน enqueue 10
คิวนี้เราต้องการที่จะนำมันหลังจาก 13

261
00:13:17,030 --> 00:13:19,860
และเพื่อให้เรากำลังจะไปแบบไดนามิก
จัดสรรพื้นที่สำหรับโหนดใหม่

262
00:13:19,860 --> 00:13:23,280
และตรวจสอบ null เพื่อให้แน่ใจว่า
เราไม่ได้มีความล้มเหลวของหน่วยความจำ

263
00:13:23,280 --> 00:13:27,040
แล้วเรากำลังจะไป
วางลงใน 10 โหนดนั้น

264
00:13:27,040 --> 00:13:30,030
และตอนนี้เราจะต้องระมัดระวัง
เกี่ยวกับวิธีการที่เราจัดระเบียบตัวชี้

265
00:13:30,030 --> 00:13:32,180
ดังนั้นเราจึงไม่ทำลายห่วงโซ่

266
00:13:32,180 --> 00:13:38,910
>> เราสามารถตั้งค่าฟิลด์ก่อนหน้า 10
ที่จะชี้กลับไปที่หางเก่า

267
00:13:38,910 --> 00:13:41,620
และตั้งแต่ '10 จะเป็น
หางใหม่ในบางจุด

268
00:13:41,620 --> 00:13:44,459
ตามเวลาทั้งหมดของเหล่านี้
เครือข่ายมีการเชื่อมต่อ

269
00:13:44,459 --> 00:13:46,250
ไม่มีอะไรที่จะมา
หลังจากวันที่ 10 ในขณะนี้

270
00:13:46,250 --> 00:13:49,880
และอื่น ๆ 10 ตัวชี้ต่อไป
จะชี้ให้เป็นโมฆะ,

271
00:13:49,880 --> 00:13:53,580
และหลังจากนั้นเราทำเช่นนี้หลังจากที่เราได้
การเชื่อมต่อ 10 ข้างหลังเพื่อโซ่

272
00:13:53,580 --> 00:13:57,780
เราสามารถใช้หัวเก่าหรือข้ออ้าง
ผมหางเก่าคิว

273
00:13:57,780 --> 00:14:02,980
ปลายเก่าคิว
13 และทำให้มันชี้ไปที่ 10

274
00:14:02,980 --> 00:14:08,220
และตอนนี้ที่จุดนี้เรามี
enqueued จำนวน 10 เข้าไปในคิวนี้

275
00:14:08,220 --> 00:14:14,740
ทั้งหมดที่เราต้องทำตอนนี้เป็นเพียงการย้าย
หางจะชี้ไปที่ 10 แทน 13

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing เป็นจริง
คล้ายกันมากกับ popping

277
00:14:17,630 --> 00:14:21,710
จากสแต็คที่เป็น
นำมาใช้เป็นรายการที่เชื่อมโยง

278
00:14:21,710 --> 00:14:24,040
ถ้าคุณเคยเห็นวิดีโอกอง

279
00:14:24,040 --> 00:14:27,280
ทั้งหมดที่เราต้องทำคือการเริ่มต้นที่
เริ่มต้นพบว่าองค์ประกอบที่สอง

280
00:14:27,280 --> 00:14:30,480
ฟรีองค์ประกอบแรก
และจากนั้นย้ายหัว

281
00:14:30,480 --> 00:14:32,930
ให้ชี้ไปที่องค์ประกอบที่สอง

282
00:14:32,930 --> 00:14:37,920
อาจจะดีกว่าที่จะเห็นภาพมัน
เพียงเพื่อจะเพิ่มความชัดเจนเกี่ยวกับเรื่องนี้

283
00:14:37,920 --> 00:14:39,230
ดังนั้นนี่คือคิวของเราอีกครั้ง

284
00:14:39,230 --> 00:14:42,600
12 เป็นธาตุที่เก่าแก่ที่สุด
ในคิวของเราหัว

285
00:14:42,600 --> 00:14:46,210
10 เป็นองค์ประกอบใหม่ล่าสุด
ในคิวของเราหางของเรา

286
00:14:46,210 --> 00:14:49,310
>> ดังนั้นเมื่อเราต้องการ
เพื่อ dequeue องค์ประกอบ

287
00:14:49,310 --> 00:14:52,202
เราต้องการที่จะเอาองค์ประกอบที่เก่าแก่ที่สุด

288
00:14:52,202 --> 00:14:52,910
ดังนั้นสิ่งที่เราจะทำ?

289
00:14:52,910 --> 00:14:55,243
ดีที่เรากำหนดตัวชี้สำรวจเส้นทาง
ที่เริ่มต้นที่หัว

290
00:14:55,243 --> 00:14:57,840
และเราย้ายมันเพื่อให้มัน
ชี้ไปที่องค์ประกอบที่สอง

291
00:14:57,840 --> 00:15:02,290
นี้ queue-- บางสิ่งบางอย่างด้วยการพูดว่า Trav
เท่ากับลูกศร Trav ต่อไปตัวอย่างเช่น

292
00:15:02,290 --> 00:15:07,170
จะย้าย Trav มีให้ชี้ไปที่
15 ซึ่งหลังจากที่เรา dequeue 12

293
00:15:07,170 --> 00:15:13,030
หรือหลังจากที่เราเอา 12 จะ
กลายเป็นองค์ประกอบแล้วที่เก่าแก่ที่สุด

294
00:15:13,030 --> 00:15:16,360
>> ตอนนี้เราได้มีไว้ในครั้งแรก
องค์ประกอบผ่านหัวตัวชี้

295
00:15:16,360 --> 00:15:19,440
และองค์ประกอบที่สอง
ผ่านตัวชี้ Trav

296
00:15:19,440 --> 00:15:25,170
เราสามารถหัวฟรีในขณะนี้และจากนั้นเราสามารถ
บอกว่าไม่มีอะไรมาก่อนวันที่ 15 อีกต่อไป

297
00:15:25,170 --> 00:15:29,990
ดังนั้นเราจึงสามารถเปลี่ยน 15 ก่อนหน้านี้
ตัวชี้จะชี้ให้เป็นโมฆะ,

298
00:15:29,990 --> 00:15:31,874
และเราก็ย้ายหัวมากกว่า

299
00:15:31,874 --> 00:15:32,540
และมีที่เราจะไป

300
00:15:32,540 --> 00:15:35,840
ตอนนี้เรามีประสบความสำเร็จ
dequeued 12 และตอนนี้เรา

301
00:15:35,840 --> 00:15:39,180
มีคิว 4 องค์ประกอบอื่น

302
00:15:39,180 --> 00:15:41,700
ที่สวยมากทั้งหมด
ที่มีให้คิว

303
00:15:41,700 --> 00:15:45,810
ทั้งอาร์เรย์ที่ใช้และรายชื่อที่เชื่อมโยงตาม

304
00:15:45,810 --> 00:15:46,860
ฉันลอยด์ดั๊ก

305
00:15:46,860 --> 00:15:49,100
นี่คือซี 50

306
00:15:49,100 --> 00:15:50,763