→ חזרו אחורה

פרק 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 - החתימה הסטנדרטית

⁦C#⁩

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

    public bool IsEmpty() { ... }
    public void Push(T x) { ... }   // מוסיפה x לראש המחסנית
    public T Top() { ... }          // מחזירה את הערך שבראש, בלי להוריד אותו
    public T Pop() { ... }          // מורידה ומחזירה את הערך שבראש
}

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

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

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

⁦C#⁩

public static void PrintReversed(int[] arr) {
    Stack<int> stk = new Stack<int>();
    for (int i = 0; i < arr.Length; i++) {
        stk.Push(arr[i]);
    }
    while (!stk.IsEmpty()) {
        Console.WriteLine(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()?

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

⁦C#⁩ 
Stack<int> stk = new Stack<int>();
stk.Push(1);
stk.Push(2);
stk.Push(3);
stk.Pop();
Console.WriteLine(stk.Top());

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

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

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

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