מחסנית ותור - שני מבני הנתונים הקלאסיים
LIFO לעומת FIFO - איך להבדיל ביניהם, איך לממש ובאילו אלגוריתמים הם שימושיים.
מחסנית (Stack) ותור (Queue) הם מבני נתונים מופשטים שמגדירים סדר גישה לאלמנטים. שניהם פשוטים, אך עומדים בבסיסם של אלגוריתמים רבים.
מחסנית - LIFO (Last In, First Out)
מחסנית פועלת כמו ערימת צלחות: האחרון שנכנס הוא הראשון שיוצא. הפעולות העיקריות הן push (הוספה לראש) ו-pop (הוצאה מהראש), שתיהן O(1).
const stack = [];
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.pop(); // returns 3, stack: [1, 2]
stack[stack.length - 1]; // peek: 2יישומים נפוצים של מחסנית
- מחסנית קריאות (Call Stack) של רקורסיה
- ביטול פעולות (Undo) בעורכי טקסט
- בדיקת איזון סוגריים בקלט
- מימוש DFS איטרטיבי
- המרת ביטויים בין infix ל-postfix
תור - FIFO (First In, First Out)
תור פועל כמו תור בקופה: הראשון שנכנס הוא הראשון שיוצא. הפעולות העיקריות הן enqueue (הוספה לסוף) ו-dequeue (הוצאה מההתחלה), שתיהן O(1) במימוש יעיל.
אם מממשים תור עם מערך פשוט ו-shift() להוצאה - כל dequeue יהיה O(n)! השתמשו ב-deque, ברשימה מקושרת או בתור מעגלי.
יישומים נפוצים של תור
- מימוש BFS על גרפים ועצים
- תורי הדפסה ותורי משימות
- תזמון תהליכים במערכת הפעלה (Round Robin)
- מנגנוני buffering בזרמי נתונים
תור עדיפויות (Priority Queue)
וריאציה חשובה: תור עדיפויות מחזיר תמיד את האלמנט עם העדיפות הגבוהה (או הנמוכה) ביותר. ממומש לרוב עם ערמה בינארית עם O(log n) להוספה והוצאה. זהו מבנה הנתונים בלב Dijkstra ו-A*.