ملخص Queue للمقابلات البرمجية
مقدمة
الـQueue هو مجموعة خطية من العناصر تُحفظ في تسلسل ويمكن تعديلها بإضافة عناصر عند أحد طرفي التسلسل (عملية الإلحاق enqueue) وإزالة عناصر من الطرف الآخر (عملية السحب dequeue). وعادةً ما يُسمى طرف التسلسل الذي تُضاف عنده العناصر بالمؤخرة أو الذيل، ويُسمى الطرف الذي تُزال منه العناصر بالرأس أو المقدمة. وبوصفه نوع بيانات مجرداً، يمكن تنفيذ الـQueue باستخدام الـArrays أو الـLinked Lists الأحادية.
يُعرف هذا السلوك عادةً باسم FIFO (أول ما يدخل هو أول ما يخرج). وجاء اسم «الـQueue» لهذا النوع من البنى من تشبيهه بوقوف الناس في صف في الحياة الواقعية لانتظار سلعة أو خدمة.
يُنفَّذ BFS عادةً باستخدام الـQueues.
مصادر التعلم
- قراءات
- To Queue Or Not To Queue، basecs
- فيديوهات
- Queues، جامعة كاليفورنيا في سان دييغو
التطبيقات الجاهزة
| اللغة | API |
|---|---|
| C++ | std::queue |
| Java | java.util.Queue. استخدم java.util.ArrayDeque |
| Python | deque |
| JavaScript | N/A |
الـtime complexity
| العملية | Big-O |
|---|---|
| الإلحاق | O(1) |
| السحب | O(1) |
| المقدمة | O(1) |
| المؤخرة | O(1) |
| فحص الفراغ | O(1) |
أمور يجب الانتباه لها أثناء المقابلات
معظم اللغات لا تحتوي على صنف Queue مدمج يمكن استخدامه، وكثيراً ما يستخدم المرشحون الـArrays (في JavaScript) أو القوائم (في Python) بوصفها Queue. لكن لاحظ أن عملية السحب (بافتراض أن مقدمة الـQueue على اليسار) في مثل هذا السيناريو ستكون بزمن O(n) لأنها تتطلب إزاحة جميع العناصر الأخرى إلى اليسار بمقدار واحد. في مثل هذه الحالات، يمكنك تنبيه المُقابِل إلى ذلك وذكر أنك تفترض وجود بنية بيانات Queue يمكن استخدامها وتتمتع بعملية سحب كفؤة.
الحالات الحدّية
- Queue فارغ
- Queue فيه عنصر واحد
- Queue فيه عنصران
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.