أمثلة مفصلة مع الصور والنصوص لتنفيذ قوائم الانتظار في JavaScript

التوصيات ذات الصلة: برنامج تعليمي لجافا سكريبت

1. بنية بيانات قائمة الانتظار

• قائمة الانتظار هي نوع من بنية البيانات "الوارد أولاً يخرج أولاً" (FIFO). أول عنصر تم وضعه في قائمة الانتظار (الإدخال) هو أول عنصر تم وضعه في قائمة الانتظار (الإخراج).
• تحتوي قائمة الانتظار على مؤشرين: الرأس والذيل. أقدم عنصر في قائمة الانتظار موجود في الرأس، وأحدث عنصر في قائمة الانتظار موجود في الذيل.
• إن قائمة الانتظار تشبه الانتظار في مترو الأنفاق. الركاب بالقرب من الباب هم في مقدمة قائمة الانتظار، والركاب الذين دخلوا للتو في قائمة الانتظار هم في الجزء الخلفي من قائمة الانتظار.

من منظور عالي المستوى، قائمة الانتظار هي بنية بيانات تسمح لنا بمعالجة كل عنصر من البيانات بالترتيب الذي تم تخزينه به في قاعدة البيانات.

2. العمليات على قائمة الانتظار

تدعم قائمة الانتظار عمليتين رئيسيتين: قائمة الانتظار وإلغاء قائمة الانتظار. بالإضافة إلى ذلك، قد تجد أنه من المفيد إجراء عمليات النظرة الخاطفة والطول في قائمة الانتظار.

• عملية Enqueue <br/>عملية Enqueue هي إدراج عنصر في نهاية قائمة الانتظار، ويصبح العنصر المدرج في نهاية قائمة الانتظار.

تؤدي عملية وضع قائمة الانتظار في الشكل أعلاه إلى إدراج العنصر 8 في النهاية، ويصبح العنصر 8 هو نهاية قائمة الانتظار.

queue.enqueue(8);

• عملية Dequeue <br/> عملية Dequeue هي استخراج العنصر في بداية قائمة الانتظار، ويصبح العنصر التالي في قائمة الانتظار هو العنصر الرئيسي.

في الصورة أعلاه، تعود عملية dequeue وتزيل العنصر 7 من قائمة الانتظار، بعد أن يصبح العنصر 2 هو العنصر الرئيسي الجديد.

queue.dequeue(); // => 7

• عملية فحص <br/> تقرأ عملية الفحص بداية قائمة الانتظار دون تغيير قائمة الانتظار.

العنصر 7 هو بداية قائمة الانتظار في الصورة أعلاه، وتقوم عملية الفحص بإرجاع الرأس (العنصر) 7 فقط دون تعديل قائمة الانتظار.

queue.peek(); // => 7

• طول قائمة الانتظار تحسب عملية الطول عدد العناصر التي تحتوي عليها قائمة الانتظار.

يوجد 4 عناصر في قائمة الانتظار في الصورة: 4 و6 و2 و7. ونتيجة لذلك، يكون طول قائمة الانتظار 4.

queue.length; // => 4

• التعقيد الزمني لعملية قائمة الانتظار الشيء المهم لجميع عمليات قائمة الانتظار (قائمة الانتظار، وإلغاء قائمة الانتظار، والعرض، والطول) هو أن جميع هذه العمليات يجب تنفيذها في وقت محدد O(1).

الوقت الثابت O(1) يعني أنه بغض النظر عن حجم قائمة الانتظار (يمكن أن تحتوي على 10 أو 1 مليون عنصر): يجب تنفيذ عمليات قائمة الانتظار، وإلغاء قائمة الانتظار، والنظرة الخاطفة، والطول في وقت واحد.

3. تنفيذ قوائم الانتظار في JavaScript

دعونا نلقي نظرة على التنفيذ المحتمل لبنية بيانات قائمة الانتظار مع الحفاظ على متطلبات تنفيذ جميع العمليات في وقت ثابت O(1).

قائمة انتظار الفئة {
  منشئ () {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  سرد (العنصر) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  قائمة الانتظار () {
    عنصر ثابت = this.items[this.headIndex];
    احذف this.items[this.headIndex];
    this.headIndex++;
    البند العودة؛
  }

  نظرة خاطفة () {
    إرجاع this.items[this.headIndex];
  }

  الحصول على الطول () {
    إرجاع this.tailIndex - this.headIndex؛
  }
}

قائمة انتظار const = قائمة انتظار جديدة ()؛

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek(); // => 2

queue. length; // => 3

const queue = new Queue() هي كيفية إنشاء مثيل لقائمة الانتظار.

قم باستدعاء الأسلوب queue.enqueue(7) لوضع العنصر 7 في قائمة الانتظار.

يقوم queue.dequeue() بإزالة عنصر الرأس من قائمة الانتظار، بينما يقوم queue.peek() فقط بإلقاء نظرة خاطفة من البداية.

وأخيرًا، يُظهر queue.length عدد العناصر المتبقية في قائمة الانتظار.

فيما يتعلق بالتنفيذ: داخل فئة قائمة الانتظار، يحتفظ الكائن العادي this.items بالعناصر الموجودة في قائمة الانتظار من خلال فهرس رقمي. يتم تعقب فهرس العنصر الرئيسي بواسطة this.headIndex، ويتم تعقب فهرس العنصر الخلفي بواسطة this.tailIndex.

• تعقيد أساليب قائمة الانتظار

تستخدم أساليب queue() وdequeue() وpeek() و length() الخاصة بقائمة انتظار الفئة فقط:

الوصول إلى السمات (مثل this.items[this.headIndex])،

أو إجراء عمليات حسابية (مثل this.headIndex++)

لذلك، فإن التعقيد الزمني لهذه الطرق هو وقت ثابت O(1).

4. ملخص

بنية بيانات قائمة الانتظار هي نوع من "الوارد أولاً، يخرج أولاً" (FIFO): العنصر الأقدم الذي يتم إدراجه في قائمة الانتظار هو العنصر الأقدم الذي يتم إدراجه في قائمة الانتظار.

تحتوي قوائم الانتظار على عمليتين رئيسيتين: قائمة الانتظار وقائمة الانتظار. بالإضافة إلى ذلك، يمكن أن تحتوي قوائم الانتظار على عمليات مساعدة مثل العرض والطول.

يجب أن تنفذ كافة عمليات قائمة الانتظار O(1) في وقت ثابت.

التوصيات ذات الصلة: البرنامج التعليمي لتعلم JavaScript

ما ورد أعلاه هو شرح مفصل لتنفيذ قوائم الانتظار في JavaScript مع الأمثلة والصور لمزيد من المعلومات، يرجى الانتباه إلى المقالات الأخرى ذات الصلة على موقع PHP الصيني!