ملخص Stack للمقابلات البرمجية
مقدمة
الـStack هو نوع بيانات مجرد يدعم عمليتي الإدخال (push)، أي إدراج عنصر جديد في قمة الـStack، والإخراج (pop)، أي إزالة وإرجاع آخر عنصر أُضيف مؤخراً، وهو العنصر الموجود في قمة الـStack. وبوصفه نوع بيانات مجرداً، يمكن تنفيذ الـStack باستخدام الـArrays أو الـLinked Lists الأحادية.
يُعرف هذا السلوك عادةً باسم LIFO (آخر ما يدخل هو أول ما يخرج). وجاء اسم «الـStack» لهذا النوع من البنى من تشبيهه بمجموعة من الأغراض المادية المكدّسة فوق بعضها.
تُعد الـStacks وسيلة مهمة لدعم استدعاءات الدوال المتداخلة أو التعاودية، وتُستخدم لتنفيذ DFS. ويمكن تنفيذ DFS باستخدام التعاود أو Stack يدوي.
مصادر التعلم
- قراءات
- Stacks and Overflows، basecs
- فيديوهات
- Stacks، جامعة كاليفورنيا في سان دييغو
التطبيقات الجاهزة
| اللغة | API |
|---|---|
| C++ | std::stack |
| Java | java.util.Stack |
| Python | يُحاكى باستخدام List |
| JavaScript | يُحاكى باستخدام Array |
الـtime complexity
| العملية | Big-O |
|---|---|
| الاطلاع على القمة | O(1) |
| الإدخال | O(1) |
| الإخراج | O(1) |
| فحص الفراغ | O(1) |
| البحث | O(n) |
الحالات الحدّية
- Stack فارغ. الإخراج من Stack فارغ
- Stack فيه عنصر واحد
- Stack فيه عنصران
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.