DOUG لويد: حتى إذا كنت قد شاهد الفيديو على كومة،
هذا هو على الارجح سوف تشعر مثل قليلا من ديجافو.
انه سيكون لمفهوم مماثل للغاية، فقط مع تطور طفيف على ذلك.
ونحن في طريقنا للحديث الآن عن قوائم الانتظار.
لذلك الانتظار، على غرار كومة، هو نوع آخر من بنية البيانات
التي يمكننا استخدامها للحفاظ على البيانات بطريقة منظمة.
تشبه إلى كومة، فإنه يمكن تنفيذها
كما صفيف أو قائمة مرتبطة.
على عكس كدسة، والقواعد التي نستخدمها لتحديد
عندما الحصول على إضافة أشياء وإزالتها من طابور مختلفة قليلا.
>> على عكس المكدس، الذي هو بنية LIFO،
تستمر في، انتهت الأولى، طابور هو FIFO هيكل، FIFO، أولا في، انتهت الأولى.
قوائم الانتظار الآن، وربما كنت لها قياسا على قوائم الانتظار.
إذا كنت قد أي وقت مضى في خط متنزه أو في أحد البنوك،
هناك نوع من الإنصاف تنفيذ الهيكل.
أول شخص في خط البنك هو أول شخص
الذي يحصل على التحدث إلى الصراف.
>> سيكون من نوع من السباق إلى أسفل إذا كانت الطريقة الوحيدة
كنت حصلت على التحدث إلى الموظف في وكان البنك أن يكون آخر شخص في الخط.
ان الجميع يريدون دائما ليكون آخر شخص في الخط،
والشخص الذي كان هناك أولا الذي ينتظر لفترة من الوقت،
يمكن أن يكون هناك لساعات، وساعات، وساعات
قبل أن تتاح لهم فرصة لفي الواقع سحب أي أموال في البنك.
وهكذا قوائم الانتظار نوع من الإنصاف تنفيذ الهيكل.
ولكن هذا لا يعني بالضرورة أن الأكوام شيئا سيئا، فقط
أن قوائم الانتظار طريقة أخرى للقيام بذلك.
ذلك مرة أخرى طابور الأول في، أولا بها، مقابل كومة التي تستمر في،
لأول مرة.
تشبه إلى كومة، لدينا اثنين من العمليات
أننا يمكن أن تؤدي على قوائم الانتظار.
الأسماء إدراج بقائمة الانتظار، والتي هي لإضافة عنصر جديد إلى نهاية قائمة الانتظار،
وdequeue، وهو لإزالة أقدم
عنصر من الجبهة من قائمة الانتظار.
لذلك نحن ذاهبون لإضافة عناصر إلى نهاية قائمة الانتظار،
ونحن في طريقنا لإزالة العناصر من الجزء الأمامي من الطابور.
مرة أخرى، مع مكدس، كنا مضيفا عناصر إلى أعلى المكدس
وإزالة العناصر من أعلى المكدس.
وذلك مع إدراج بقائمة الانتظار، فإنه إضافة إلى نهاية، وإزالة من الجبهة.
لذلك أقدم شيء في هناك هو دائما الشيء التالي
للخروج إذا حاولنا وdequeue شيء.
>> ذلك مرة أخرى، مع طوابير، يمكننا تطبيقات المستندة إلى صفيف
ويرتبط-قائمة التطبيقات القائمة.
سنبدأ من جديد مع تطبيقات المستندة إلى صفيف.
تعريف الهيكل تبدو مشابهة جدا.
لدينا مجموعة أخرى هناك من قيمة نوع البيانات،
لذلك يمكن أن تعقد أنواع البيانات التعسفية.
نحن مرة أخرى تنوي استخدام الأعداد الصحيحة في هذا المثال.
>> ومثلما لدينا تنفيذ كومة المستندة إلى صفيف،
لأننا باستخدام مجموعة، فإننا بالضرورة
يكون هذا القيد أن نوع C من يفرض علينا، وهو أننا
لم يكن لديك أي دينامية في موقعنا القدرة على النمو وتقليص مجموعة.
يتعين علينا أن نقرر في البداية ما هو الحد الأقصى لعدد الأشياء
أننا يمكن أن تضع في هذا طابور، وفي هذه الحالة،
ان طاقة تكون بعض جنيه تعريف ثابت في نظامنا.
ولأغراض هذا الفيديو، والقدرة سيكون 10.
>> نحن بحاجة إلى تتبع الجزء الأمامي من الطابور
حتى نعرف أي عنصر نريد أن dequeue،
وعلينا أيضا أن تتبع شيء else-- عدد العناصر
أن لدينا في قائمة الانتظار لدينا.
لاحظ أننا لا تتبع من نهاية الطابور، فقط
حجم قائمة الانتظار.
والسبب في ذلك سوف نأمل تصبح أكثر وضوحا قليلا في لحظة.
بعد أن نكون قد أكملت هذا التعريف نوع،
لدينا نوع البيانات الجديد دعا الانتظار، والتي يمكننا الآن
بتعريف المتغيرات من هذا النوع البيانات.
ومربك بعض الشيء، لقد قررت أن نطلق على هذا الطابور س، والرسالة
س بدلا من نوع البيانات ف.
>> حتى هنا هو طابور لدينا.
وهو هيكل.
أنه يحتوي على ثلاثة أعضاء أو ثلاثة الحقول، ومجموعة من القدرات الحجم.
في هذه الحالة، والقدرات هي 10.
وهذه المجموعة هي الذهاب لعقد صحيحة.
باللون الأخضر هو الجزء الأمامي من طابور لدينا، و العنصر التالي لإزالتها، وباللون الأحمر
سيكون حجم قائمة الانتظار، كم عدد العناصر حاليا
القائمة في قائمة الانتظار.
حتى لو قلنا متساوين q.front 0، وحجم q.size يساوي 0--
نحن نضع 0S في تلك المجالات.
وعند هذه النقطة، نحن الى حد كبير استعداد لبدء العمل مع طابور لدينا.
>> وبالتالي فإن العملية الأولى في وسعنا أداء غير لإدراج بقائمة الانتظار شيء،
لإضافة عنصر جديد ل نهاية قائمة الانتظار.
حسنا ماذا نحن بحاجة إلى القيام به في الحالة العامة؟
حسنا هذه الوظيفة إدراج بقائمة الانتظار الاحتياجات لقبول مؤشر إلى قائمة الانتظار لدينا.
مرة أخرى، إذا كنا قد أعلنت طابور على الصعيد العالمي،
ونحن لن تحتاج إلى القيام بذلك بالضرورة، ولكن بشكل عام، ونحن
بحاجة إلى قبول مؤشرات لهياكل البيانات
مثل هذا، لأن خلاف ذلك، نحن مرورا value-- نحن
يمر في نسخ من قائمة الانتظار، وهكذا نحن لا تغير الواقع
قائمة الانتظار التي نعتزم تغيير.
>> الشيء الآخر أنه يحتاج إلى القيام به هو قبول عنصر البيانات من النوع المناسب.
مرة أخرى، في هذه الحالة، فمن ستكون الأعداد الصحيحة،
ولكن هل يمكن تعسفا أعلن نوع البيانات كقيمة
واستخدام هذا بشكل عام.
هذا العنصر نريد أن إدراج بقائمة الانتظار، نريد أن نضيف إلى نهاية قائمة الانتظار.
ثم نريد فعلا ل وضع البيانات في قائمة الانتظار.
في هذه الحالة، ووضعها في الموقع الصحيح من مجموعة لدينا،
ثم نريد لتغيير حجم من قائمة الانتظار، وكم العناصر نحن
لديها حاليا.
>> لذلك دعونا نبدأ.
هنا، مرة أخرى، أن عام وظيفة شكل إعلان
لماذا إدراج بقائمة الانتظار قد تبدو.
وها قد بدأنا.
دعونا إدراج بقائمة الانتظار عدد 28 في قائمة الانتظار.
فما نحن فاعلون؟
حسنا، الجزء الأمامي من طابور لدينا في 0، وحجم قائمة الانتظار لدينا
هو في 0، ولذا فإننا ربما تريد أن تضع عدد 28 في مجموعة رقم عنصر
0، أليس كذلك؟
لذلك نحن قد وضعت الآن أن في هناك.
حتى الآن ماذا نحن بحاجة إلى تغيير؟
نحن لا نريد تغيير الجزء الأمامي من الطابور،
لأننا نريد أن نعرف ما العنصر أننا قد نحتاج إلى dequeue في وقت لاحق.
لذلك السبب لدينا الجبهة هناك هو نوع من مؤشر على ما هو
أقدم شيء في المصفوفة.
كذلك أقدم شيء في array-- في الواقع، الشيء الوحيد في مجموعة الحق
now-- هو 28، وهو في مجموعة 0 موقع.
لذلك نحن لا نريد أن تغيير هذا الرقم الأخضر،
لأن هذا هو أقدم عنصر.
بدلا من ذلك، نحن نريد لتغيير الحجم.
حتى في هذه الحالة، وسوف نقوم زيادة حجم إلى 1.
>> الآن نوعا العام للفكرة من حيث العنصر التالي ستذهب في طابور
وإضافة هذين الرقمين معا، أمام والحجم،
والتي سوف أقول لكم أين المقبل عنصر في قائمة الانتظار ستذهب.
حتى الآن دعونا إدراج بقائمة الانتظار رقم آخر.
دعونا إدراج بقائمة الانتظار 33.
حتى 33 ستذهب إلى مجموعة 0 موقع زائد 1.
حتى في هذه الحالة، فإنه يجري للذهاب الى مجموعة موقع 1،
والآن حجم قائمة الانتظار لدينا هو 2.
>> مرة أخرى، نحن لا تغيير الجزء الأمامي من طابور لدينا،
لأن 28 لا يزال أقدم عنصر، ونحن
تريد to-- عندما نصل في نهاية المطاف لdequeuing، وإزالة العناصر
من قائمة الانتظار هذه، نريد أن نعرف حيث أقدم العنصر.
وهكذا نحن دائما في حاجة للحفاظ على بعض المؤشرات من حيث هذا هو.
وهذا ما هو هناك 0 ل.
هذا ما هو الجبهة هناك.
>> دعونا في إدراج بقائمة الانتظار أكثر واحد العنصر، 19.
أنا متأكد من أنك يمكن تخمين حيث 19 هو ذاهب للذهاب.
انها سوف تذهب الى مجموعة موقع رقم 2.
هذا بالإضافة إلى 0 2.
والآن حجم قائمة الانتظار لدينا هو 3.
لدينا 3 عناصر في ذلك.
حتى إذا كنا، ونحن لن إلى الآن، إدراج بقائمة الانتظار عنصر آخر،
انها ستمضي في موقع مجموعة عدد 3، وحجم قائمة الانتظار لدينا
سيكون 4.
لذلك قمنا enqueued عدة عناصر الآن.
الآن دعونا نبدأ لإزالتها.
دعونا dequeue لهم من قائمة الانتظار.
>> على غرار ذلك لموسيقى البوب، وهو نوع من التناظرية من هذا لالمداخن،
dequeue يحتاج إلى قبول المؤشر إلى queue-- مرة أخرى،
إلا إذا كان أعلن على الصعيد العالمي عليه.
الآن نريد أن تغيير موقع للجزء الأمامي من الطابور.
هذا هو المكان الذي يأتي نوع من في اللعب، هذا المتغير الأمامي،
لأنه بمجرد أزلنا عنصر، ونحن نريد
لنقلها إلى أقدم العنصر التالي.
>> ثم نريد أن ينخفض حجم قائمة الانتظار،
ثم نريد لإرجاع القيمة التي تم إزالتها من قائمة الانتظار.
مرة أخرى، نحن لا نريد أن مجرد تجاهل ذلك.
نحن يفترض تستخرج فإنه من queue-- نحن
dequeuing ذلك لأننا نهتم حول هذا الموضوع.
لذلك نحن نريد هذه الوظيفة للعودة عنصر بيانات القيمة النوع.
مرة أخرى، في هذه الحالة، القيمة هي عدد صحيح.
>> حتى الآن دعونا dequeue شيء.
دعونا إزالة عنصر من قائمة الانتظار.
إذا قلنا الباحث س يساوي & Q، العطف q-- مرة أخرى وهذا مؤشر إلى هذه البيانات ف
structure-- ما العنصر سوف يتم dequeued؟
في هذه الحالة، لأنه لأول مرة في، أولا خارج بنية البيانات، FIFO،
أول شيء وضعنا في هذا كان الانتظار 28 عاما، وحتى في هذه الحالة،
ونحن في طريقنا إلى اتخاذ 28 من أصل قائمة الانتظار، وليس 19، وهو ما
كنا سنفعله إذا كان هذا كومة.
ونحن في طريقنا إلى اتخاذ 28 من قائمة الانتظار.
>> على غرار ما فعلنا مع كومة، نحن لسنا في الواقع
الذهاب إلى حذف 28 من قائمة الانتظار نفسها،
نحن ذاهبون لمجرد نوع من يدعي أنه ليس هناك.
حتى انها تنوي البقاء هناك في الذاكرة، ولكن نحن فقط
الذهاب إلى نوع من تجاهله عن طريق تحريك الحقلين أخرى من البيانات ف لدينا
بناء.
ونحن في طريقنا إلى تغيير الجبهة.
Q.front يجري الآن ل 1 أن يكون، لأن هذا هو الآن
أقدم عنصر لدينا في طابور، لأننا بالفعل بإزالة 28،
التي كانت العنصر أقدم السابق.
>> والآن، نريد تغيير حجم قائمة الانتظار
إلى عنصرين بدلا من ثلاثة.
وقال الآن أتذكر عندما كنا في وقت سابق I تريد إضافة عناصر إلى قائمة الانتظار،
نضعه في موقع مجموعة وهو مبلغ من الجبهة والحجم.
حتى في هذه الحالة، نحن لا نزال وضع ذلك، فإن العنصر التالي في قائمة الانتظار،
في مجموعة موقع 3، و سنرى ذلك في الثانية.
>> لذلك قمنا dequeued الآن لدينا العنصر الأول من قائمة الانتظار.
دعونا نفعل ذلك مرة أخرى.
دعونا إزالة آخر عنصر من قائمة الانتظار.
في القضية، التيار أقدم العنصر مجموعة موقع 1.
هذا ما q.front يخبرنا.
هذا المربع الأخضر يخبرنا أن هذا هو أقدم عنصر.
وهكذا، سوف تصبح س 33.
سنقوم مجرد نوع من ننسى أن 33 موجود في مجموعة،
وسوف نقول ذلك الآن، و أقدم عنصر جديد في قائمة الانتظار
هو في موقع مجموعة 2، وحجم من قائمة الانتظار، وعدد من العناصر
لدينا في قائمة الانتظار، هو 1.
الآن دعونا إدراج بقائمة الانتظار شيء، وأنا نوع من أعطى هذا بعيدا قبل الثانية،
ولكن إذا كنا نريد أن نضع 40 في طابور، حيث 40 سيذهب؟
حسنا لقد تم وضعه في q.front بالإضافة إلى طابور الحجم،
ولذا فمن المنطقي ل في الواقع لوضع 40 هنا.
نلاحظ الآن أنه في مرحلة ما، ونحن في طريقنا
للوصول الى نهاية مجموعة لدينا داخل ف،
ولكن ذلك تلاشى 28 و 33-- انهم في الواقع، من الناحية الفنية
المساحات المفتوحة، أليس كذلك؟
وهكذا، ونحن قد eventually-- تلك القاعدة إضافة
هذين together-- يجوز لنا في نهاية المطاف تحتاج إلى وزارة الدفاع حسب حجم القدرات
حتى نتمكن من التفاف حولها.
>> لذلك إذا أردنا الحصول على عنصر عدد 10، إذا نحن
الاستعاضة عنها في العنصر رقم 10، لكنا وضع فعلا في مجموعة 0 موقع.
وإذا نحن ذاهبون ل مجموعة location-- إسمح لي،
إذا أضفنا لهم معا، وصلنا إلى رقم
11 سيكون حيث سيكون لدينا لوضع ، والذي لا وجود له في هذا array--
سيكون من الذهاب خارج الحدود.
يمكننا أن وزارة الدفاع قبل 10 ووضع في مجموعة موقع 1.
لذلك هذه هي الطريقة التي تعمل قوائم الانتظار.
انهم دائما ما تذهب من اليسار إلى اليمين، وربما التفاف حولها.
وأنت تعرف أنهم إذا كان حجم كامل، أن مربع أحمر،
يصبح يساوي القدرات.
وذلك بعد أن قمت بإضافة 40 ل طابور، حسنا ماذا علينا أن نفعل؟
حسنا، أقدم عنصر في قائمة الانتظار لا يزال 19،
لذلك نحن لا نريد تغيير الجزء الأمامي من الطابور،
ولكن الآن لدينا اثنين العناصر في قائمة الانتظار،
وهكذا نريد لزيادة حجمنا 1-2.
>> هذا هو الكثير جدا مع العمل مع طوابير مجموعة مقرها،
وعلى غرار كومة، هناك أيضا وسيلة
لتنفيذ طابور كقائمة المرتبطة.
الآن إذا كان هذا النوع بنية البيانات تبدو مألوفة بالنسبة لك، هو عليه.
انها ليست قائمة مرتبطة منفردة، انها قائمة مرتبطة على نحو مضاعف.
والآن، بوصفها جانبا، فمن في الواقع ممكن لتنفيذ
طابور كقائمة مرتبطة منفردة، ولكن أعتقد من حيث التصور،
في الواقع قد تساعد على عرض هذا كقائمة مرتبطة على نحو مضاعف.
ولكن من الممكن بالتأكيد ل القيام بذلك في قائمة مرتبطة منفردة.
>> لذلك دعونا ننظر لها في ما هذا قد تبدو.
إذا كنا نريد أن enquue-- وحتى الآن، ومرة ​​أخرى نحن
التحول إلى-قائمة مرتبطة نموذج يستند هنا.
إذا كنا نريد أن إدراج بقائمة الانتظار، ونحن نريد لإضافة عنصر جديد، حسنا
ماذا علينا أن نفعل؟
حسنا، أولا وقبل كل شيء، ل نحن مضيفا إلى نهاية
وإزالة من بداية، نحن على الأرجح
يريدون الحفاظ على مؤشرات إلى كل من الرأس والذيل من قائمة مرتبطة؟
ذيل يجري تعبير آخر عن نهاية القائمة المرتبطة،
العنصر الأخير في القائمة المرتبطة.
وهذه سوف ربما، مرة أخرى، أن تكون مفيدة لنا
إذا كانت المتغيرات العالمية.
ولكن الآن إذا أردنا أن نضيف جديد العنصر ماذا علينا أن نفعل؟
ما نحن فقط [؟ ملك؟] أو حيوي تخصيص عقدة جديدة من أجل أنفسنا.
وبعد ذلك، تماما مثل عندما نضيف أي عنصر إلى قائمة نحن مرتبطة على نحو مضاعف،
فقط لفرز of-- هذه الخطوات الثلاث الماضية هنا
ليست سوى كل شيء عن تحريك مؤشرات في الطريق الصحيح
بحيث يحصل على إضافة عنصر إلى سلسلة دون كسر سلسلة
أو جعل نوعا من الخطأ أو وجود بعض نوع من الحوادث
يحدث حيث اننا بطريق الخطأ اليتيم بعض عناصر قائمة الانتظار لدينا.
وهنا ما هذا قد تبدو.
نحن نريد لإضافة عنصر 10 إلى نهاية قائمة الانتظار هذه.
لذلك أقدم عنصر هنا يمثله الرأس.
وهذا هو أول شيء وضعنا في قائمة الانتظار هذه افتراضية هنا.
والذيل، 13 عاما، هو الأكثر وأضاف في الآونة الأخيرة عنصر.
وهكذا إذا أردنا أن إدراج بقائمة الانتظار 10 إلى قائمة الانتظار هذه، ونحن نريد لوضعها بعد 13.
وحتى ونحن في طريقنا إلى حيوي تخصيص مساحة لعقدة جديدة
وتحقق لاغية للتأكد من ليس لدينا فشل الذاكرة.
ثم نحن في طريقنا لل وضع 10 في تلك العقدة،
والآن نحن بحاجة إلى توخي الحذر حول كيفية ننظم مؤشرات
لذلك نحن لا كسر السلسلة.
>> فإننا يمكن أن يحدد الحقل السابق 10 ل أن نشير إلى ذيل القديم،
ومنذ '10 سيكون الذيل الجديد في مرحلة ما
بحلول الوقت كل هذه وترتبط السلاسل،
لا شيء سوف يأتي بعد 10 الآن.
وذلك مؤشر المقبل 10 ل سوف نشير إلى فارغة،
ثم بعد أن تفعل ذلك، وبعد أن قمت توصيل 10 إلى الوراء إلى السلسلة،
ويمكن أن نأخذ الرأس القديم، أو عذر لي، والذيل القديم من قائمة الانتظار.
نهاية القديمة من قائمة الانتظار، 13، وجعلها نقطة إلى 10.
والآن، في هذه المرحلة، لدينا enqueued الرقم 10 في قائمة الانتظار هذه.
كل ما عليك القيام به الآن هو مجرد نقل ذيل للإشارة إلى 10 بدلا من 13.
>> Dequeuing هو في الواقع تشبه الى حد بعيد تفرقع
من كومة التي هي تنفيذها في قائمة مرتبطة
إذا كنت قد رأيت الفيديو المداخن.
كل ما عليك القيام به هو البدء في بداية، العثور على العنصر الثاني،
تحرير العنصر الأول، ثم حرك رأسه
للإشارة إلى العنصر الثاني.
ربما من الأفضل أن تصور ذلك مجرد أن تكون واضحة اضافية حول هذا الموضوع.
حتى هنا طابور من جديد.
12 هو أقدم عنصر في قائمة الانتظار لدينا، الرأس.
10 هو أحدث عنصر في قائمة الانتظار لدينا، وذيل لدينا.
>> وحتى عندما نريد لdequeue عنصر،
نحن نريد لإزالة أقدم عنصر.
فماذا نفعل؟
كذلك وضعنا مؤشر اجتياز الذي يبدأ في الرأس،
ونحن تحريكه بحيث يشير إلى العنصر الثاني
هذا queue-- شيء بالقول بالسفر يساوي بالسفر السهم، على سبيل المثال،
ستتحرك بالسفر هناك للإشارة إلى 15، والتي، بعد أن dequeue 12،
أو بعد أن إزالة 12، سوف تصبح آنذاك أقدم عنصر.
>> ونحن الآن قد حصلت على عقد أول العنصر عبر رئيس مؤشر
والعنصر الثاني عبر بالسفر المؤشر.
نستطيع رئيس الآن حرة، ومن ثم نستطيع أقول لا شيء يأتي قبل 15 بعد الآن.
حتى نتمكن من تغيير سابقة 15 ل المؤشر إلى نقطة فارغة،
ونحن مجرد تحريك الرأس قد انتهت.
وهناك نذهب.
الآن لدينا بنجاح dequeued 12، والآن نحن
لدينا طابور آخر من 4 عناصر.
هذا الى حد كبير عن هناك إلى قوائم الانتظار،
على حد سواء على أساس مجموعة وربطها-قائمة على أساس.
أنا دوغ ويد.
هذا هو CS 50.