פרק 12 - מחסנית (Stack)

⏱ 12 דקות קריאה

בפרק על רקורסיה פגשנו את מחסנית הקריאות - איך המחשב זוכר איפה כל קריאה צריכה "לחזור אליה". Stack הוא בדיוק אותו רעיון, ארוז כמבנה נתונים שאפשר להשתמש בו בעצמנו.

1. עקרון ה-LIFO

Stack עובד לפי עיקרון LIFO - Last In, First Out: האיבר האחרון שנכנס הוא הראשון שיוצא. אפשר לגשת רק לאיבר שנמצא "למעלה" (הראש) - אי אפשר לדלג עליו ולהגיע למישהו מתחתיו.

אנלוגיה: ערימת צלחות. מניחים צלחת חדשה תמיד למעלה, ולוקחים צלחת גם תמיד מלמעלה - אי אפשר למשוך צלחת מהאמצע בלי להוריד קודם את כל מה שמעליה.

Stack מול Queue (הפרק הבא) - השוואה מהירה:

Stack - LIFO: האחרון שנכנס הוא הראשון שיוצא, כמו ערימת צלחות. הפעולות: push/pop/top.

Queue - FIFO: הראשון שנכנס הוא הראשון שיוצא, כמו תור לקופה. הפעולות: insert/remove/head.

2. מחלקת Stack - החתימה הסטנדרטית

Java


public class Stack<T> {
    public Stack() { ... }

    public boolean isEmpty() { ... }
    public void push(T x) { ... }   // מוסיפה x לראש המחסנית
    public T top() { ... }          // מחזירה את הערך שבראש, בלי להוריד אותו
    public T pop() { ... }          // מורידה ומחזירה את הערך שבראש
}

שימו לב לשלושה שמות שקל לבלבל: top() רק מציצה בראש בלי לשנות כלום, ואילו pop() גם מסירה ומחזירה אותו. תמיד לבדוק isEmpty() לפני קריאה ל-pop() או ל-top() - קריאה למחסנית ריקה היא שגיאת ריצה.

3. דוגמה - היפוך סדר בעזרת מחסנית

מחסנית היא הדרך הטבעית להפוך סדר של רצף: מכניסים הכל בסדר המקורי, ומוציאים - כל מה שיצא ראשון הוא בעצם מה שהוכנס אחרון.

Java


public static void printReversed(int[] arr) {
    Stack<Integer> stk = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        stk.push(arr[i]);
    }
    while (!stk.isEmpty()) {
        System.out.println(stk.pop());
    }
}

עבור [1, 2, 3]: הלולאה הראשונה דוחפת 1 ואז 2 ואז 3 - כך ש-3 נמצא עכשיו בראש. הלולאה השנייה מוציאה 3, 2, 1 - בדיוק בסדר הפוך למקור.

4. טעויות נפוצות

קריאה למחסנית ריקה: pop() או top() בלי לבדוק isEmpty() קודם עלולים לגרום לשגיאת ריצה.

בלבול בין top ל-pop: top() לא מוציאה כלום מהמחסנית - קריאה חוזרת עליה תמיד תחזיר את אותו ערך, עד שקוראים ל-pop().

ציפייה לסדר המקורי: מחסנית הופכת סדר מטבעה - אם רוצים לשמר את הסדר המקורי, Stack הוא לא המבנה הנכון (זה בדיוק ההבדל מ-Queue, בפרק הבא).

🎓 זווית הבגרות

איך זה מופיע בבגרות: Stack מופיע בחלק א' של שאלון 899271 כשאלה עצמאית (25 נק') - לרוב מתבקשים לממש מתודה שמעבדת מחסנית נתונה או בודקת עליה תכונה מסוימת.

סוג שאלה טיפוסי: מתודה שמקבלת Stack ומבצעת עליו פעולה (למשל היפוך סדר, בדיקת סימטריה) תוך שימוש נכון ב-push/pop/top/isEmpty בלבד - בלי לגעת בפנים של המחלקה.

טעות נפוצה: לקרוא ל-pop() או ל-top() בלי לבדוק isEmpty() קודם, או לבלבל בין top (רק מציץ) ל-pop (גם מוציא).

מה לזכור למבחן: כל עיבוד של מחסנית שלמה נכתב עם while (!stk.isEmpty()) - ואם צריך לשמר את הנתונים המקוריים, יש להחזיר אותם למחסנית נוספת תוך כדי העיבוד.

5. תרגול

דוחפים שלושה איברים למחסנית לפי הסדר הבא: "א", "ב", "ג". איזה איבר יצא ראשון בקריאה ל-pop()?

מה יודפס למסך על ידי הקוד הבא?

Java

Stack<Integer> stk = new Stack<>();
stk.push(1);
stk.push(2);
stk.push(3);
stk.pop();
System.out.println(stk.top());

כתבו את שורת הקוד שמכניסה את הערך x למחסנית בשם stk.

כתבו את תנאי הלולאה שממשיכה כל עוד המחסנית stk אינה ריקה.

כתבו את שורת הקוד שמוציאה ערך מראש המחסנית stk ושומרת אותו במשתנה x מטיפוס int.

→פרק 11 - צמתים מקושרים פרק 13 - תור (Queue)←