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

2
00:00:05,204 --> 00:00:07,370
DOUG لويد: حتى إذا كنت قد
شاهد الفيديو على كومة،

3
00:00:07,370 --> 00:00:09,870
هذا هو على الارجح سوف تشعر
مثل قليلا من ديجافو.

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
الأسماء إدراج بقائمة الانتظار، والتي هي لإضافة
عنصر جديد إلى نهاية قائمة الانتظار،

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
وذلك مع إدراج بقائمة الانتظار، فإنه إضافة إلى
نهاية، وإزالة من الجبهة.

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
>> وبالتالي فإن العملية الأولى في وسعنا
أداء غير لإدراج بقائمة الانتظار شيء،

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
حسنا هذه الوظيفة إدراج بقائمة الانتظار الاحتياجات
لقبول مؤشر إلى قائمة الانتظار لدينا.

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
هذا العنصر نريد أن إدراج بقائمة الانتظار،
نريد أن نضيف إلى نهاية قائمة الانتظار.

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
لماذا إدراج بقائمة الانتظار قد تبدو.

102
00:05:13,980 --> 00:05:14,910
وها قد بدأنا.

103
00:05:14,910 --> 00:05:18,335
دعونا إدراج بقائمة الانتظار عدد
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
حتى الآن دعونا إدراج بقائمة الانتظار رقم آخر.

124
00:06:18,130 --> 00:06:20,250
دعونا إدراج بقائمة الانتظار 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
>> دعونا في إدراج بقائمة الانتظار أكثر واحد العنصر، 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
هذا بالإضافة إلى 0 2.

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
حتى إذا كنا، ونحن لن
إلى الآن، إدراج بقائمة الانتظار عنصر آخر،

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
إذا قلنا الباحث س يساوي & 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
وقال الآن أتذكر عندما كنا في وقت سابق I
تريد إضافة عناصر إلى قائمة الانتظار،

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
وهكذا، سوف تصبح س 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
الآن دعونا إدراج بقائمة الانتظار شيء، وأنا
نوع من أعطى هذا بعيدا قبل الثانية،

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-- يجوز لنا في نهاية المطاف
تحتاج إلى وزارة الدفاع حسب حجم القدرات

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
يمكننا أن وزارة الدفاع قبل 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
إذا كنا نريد أن إدراج بقائمة الانتظار، ونحن نريد
لإضافة عنصر جديد، حسنا

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
ما نحن فقط [؟ ملك؟] أو حيوي
تخصيص عقدة جديدة من أجل أنفسنا.

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
وهكذا إذا أردنا أن إدراج بقائمة الانتظار 10 إلى
قائمة الانتظار هذه، ونحن نريد لوضعها بعد 13.

261
00:13:17,030 --> 00:13:19,860
وحتى ونحن في طريقنا إلى حيوي
تخصيص مساحة لعقدة جديدة

262
00:13:19,860 --> 00:13:23,280
وتحقق لاغية للتأكد من
ليس لدينا فشل الذاكرة.

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 هو في الواقع
تشبه الى حد بعيد تفرقع

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-- شيء بالقول بالسفر
يساوي بالسفر السهم، على سبيل المثال،

292
00:15:02,290 --> 00:15:07,170
ستتحرك بالسفر هناك للإشارة إلى
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
والعنصر الثاني
عبر بالسفر المؤشر.

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
هذا هو CS 50.

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