מחסנית ותור - שני מבני הנתונים הקלאסיים
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*.
שאלות נפוצות
מה ההבדל בין LIFO ל-FIFO?
LIFO (Last In First Out) הוא עקרון המחסנית: האיבר שנכנס אחרון יוצא ראשון, כמו ערימת צלחות שמוסיפים ומורידים מלמעלה. FIFO (First In First Out) הוא עקרון התור: האיבר שנכנס ראשון יוצא ראשון, כמו תור בקופה. ההבדל הוא רק בקצה שממנו מוציאים, אבל הוא משנה לחלוטין את סדר העיבוד.
באילו אלגוריתמים משתמשים במחסנית?
מחסנית עומדת מאחורי כל רקורסיה דרך מחסנית הקריאות, וכן בחיפוש לעומק בגרפים, בבדיקת איזון סוגריים, בהמרת ביטויים לנוטציה פולנית והערכתם, במנגנוני ביטול פעולה בעורכים, ובניווט אחורה בדפדפן. כל בעיה שדורשת לזכור מצב ולחזור אליו בסדר הפוך היא מועמדת טבעית למחסנית.
איך מממשים תור ביעילות?
מימוש נאיבי מעל מערך, שבו הוצאה מהראש מחייבת הזזת כל האיברים, עולה O(n). הפתרונות הנפוצים הם תור מעגלי — מערך עם שני אינדקסים לראש ולזנב שמתגלגלים באמצעות מודולו — או רשימה מקושרת עם מצביע לראש ולזנב. שניהם משיגים O(1) גם להכנסה וגם להוצאה.