ברוכים הבאים ליחידת הלימוד "מחסנית ותור" בקורס "מבוא למדעי המחשב ושפת Java" (20441). יחידה זו עוסקת בשני מבני נתונים לינאריים יסודיים וחשובים ביותר במדעי המחשב: המחסנית (Stack) והתור (Queue). נלמד להכיר את העקרונות העומדים בבסיסם, את הפעולות המוגדרות עליהם, דרכי מימוש נפוצות ואת היישומים הרבים שלהם באלגוריתמים ובמערכות תוכנה. הבנה מעמיקה של מבנים אלו חיונית להצלחה בקורס ובתחומים מתקדמים יותר.
מבוא למבני נתונים לינאריים
מבני נתונים הם דרכים לארגן נתונים בזיכרון המחשב באופן המאפשר גישה יעילה וביצוע פעולות שונות עליהם. מבני נתונים לינאריים הם כאלה שבהם האלמנטים מסודרים ברצף, אחד אחרי השני. מחסנית ותור הם דוגמאות למבני נתונים לינאריים מופשטים (Abstract Data Types - ADT) המגבילים את הגישה לאלמנטים, מה שמקנה להם תכונות ייחודיות ושימושיות.
מחסנית (Stack)
מחסנית היא מבנה נתונים לינארי הפועל על פי העיקרון LIFO (Last-In, First-Out) – האחרון שנכנס הוא הראשון שיוצא. דמיינו ערימת צלחות: כדי להגיע לצלחת התחתונה, יש להסיר קודם את כל הצלחות שמעליה.
פעולות בסיסיות במחסנית:
- push(item): מוסיף איבר לראש המחסנית.
- pop(): מסיר ומחזיר את האיבר שבראש המחסנית. אם המחסנית ריקה, בדרך כלל נזרקת חריגה (לדוגמה,
EmptyStackException). - peek() / top(): מחזיר את האיבר שבראש המחסנית מבלי להסירו. אם המחסנית ריקה, נזרקת חריגה.
- isEmpty(): בודק האם המחסנית ריקה.
- size(): מחזיר את מספר האיברים במחסנית.
מימוש נפוץ למחסנית הוא באמצעות מערך (array) או רשימה מקושרת (linked list). בשני המקרים, פעולות ה-push וה-pop מתבצעות בסיבוכיות זמן של O(1).
תור (Queue)
תור הוא מבנה נתונים לינארי הפועל על פי העיקרון FIFO (First-In, First-Out) – הראשון שנכנס הוא הראשון שיוצא. דמיינו תור לקופה בסופר: הראשון שהגיע הוא הראשון שמקבל שירות.
פעולות בסיסיות בתור:
- enqueue(item): מוסיף איבר לסוף התור.
- dequeue(): מסיר ומחזיר את האיבר שבראש התור. אם התור ריק, נזרקת חריגה.
- peek() / front(): מחזיר את האיבר שבראש התור מבלי להסירו. אם התור ריק, נזרקת חריגה.
- isEmpty(): בודק האם התור ריק.
- size(): מחזיר את מספר האיברים בתור.
מימוש נפוץ לתור הוא באמצעות רשימה מקושרת. מימוש באמצעות מערך דורש שימוש במערך מעגלי (circular array) כדי למנוע תזוזת איברים מיותרת ולשמור על יעילות של O(1) לפעולות ה-enqueue וה-dequeue.
השוואה ושיקולי מימוש
מחסניות ותורים הם מבני נתונים בסיסיים אך שונים במהותם וביישומיהם. הבנת ההבדלים ביניהם חיונית לבחירה נכונה של מבנה הנתונים המתאים לבעיה נתונה.
מחסנית (Stack)
עיקרון: LIFO (Last-In, First-Out).
נקודות גישה: ראש המחסנית בלבד.
יישומים נפוצים: מחסנית קריאות (רקורסיה), מנגנוני ביטול (Undo/Redo), בדיקת איזון סוגריים, הערכת ביטויים.
מימוש: קל יחסית עם מערך או רשימה מקושרת. פעולות ב-O(1).
תור (Queue)
עיקרון: FIFO (First-In, First-Out).
נקודות גישה: ראש התור (הוצאה) וסוף התור (הכנסה).
יישומים נפוצים: תזמון משימות (מערכות הפעלה), סימולציות, אלגוריתם חיפוש לרוחב (BFS), טיפול בבקשות (שרתים).
מימוש: רשימה מקושרת יעילה. מערך דורש מערך מעגלי לשמירה על יעילות O(1).
שיקולי מימוש:
- מערך: יתרון בגישה מהירה לאיברים (cache locality), אך גודל קבוע. דורש טיפול בהגדלה מחדש (resizing) או שימוש במערך מעגלי לתור.
- רשימה מקושרת: גודל דינמי, קל להוספה והסרה, אך דורש יותר זיכרון עבור מצביעים ופחות יעיל בגישה אקראית.
שאלות לדיון
- מתי תעדיפו להשתמש במחסנית על פני תור, ומתי בתור על פני מחסנית? ספקו דוגמאות קונקרטיות.
- הסבירו כיצד רקורסיה ממומשת באמצעות מחסנית. מהן ההשלכות של רקורסיה עמוקה מדי?
- תארו את האתגרים והיתרונות במימוש תור באמצעות מערך בגודל קבוע. כיצד מערך מעגלי פותר חלק מהאתגרים הללו?
- כיצד ניתן לממש מחסנית באמצעות שני תורים? (זוהי שאלת ראיונות ובחינות קלאסית).
- הסבירו את הקשר בין אלגוריתם חיפוש לרוחב (BFS) לבין תור, ובין אלגוריתם חיפוש לעומק (DFS) לבין מחסנית (או רקורסיה).
נקודות לתשובת מודל
- הבנה ברורה של עקרונות LIFO ו-FIFO וההבדלים ביניהם.
- היכרות עם הפעולות הבסיסיות של מחסנית ותור (push/pop, enqueue/dequeue, peek, isEmpty).
- יכולת לדון בשיקולי מימוש (מערך מול רשימה מקושרת, מערך מעגלי לתור) וההשלכות שלהם על יעילות ושימוש בזיכרון.
- הבנה של יישומים נפוצים של מחסניות (מחסנית קריאות, Undo/Redo) ותורים (תזמון משימות, BFS).
- יכולת לנתח סיבוכיות זמן של פעולות בסיסיות (לרוב O(1) עבור מחסנית ותור ממומשים היטב).
- הסבר מפורט על הקשר בין רקורסיה למחסנית הקריאות.