מחסנית (מבנה נתונים)

מחסנית היא מבנה נתונים מופשט. היא פועלת כמו מחסנית רובה: האיבר שנכנס אחרון יוצא ראשון (LIFO - נכנס אחרון יוצא ראשון).


הפעולות הבסיסיות הן הוספה (push), הסרה (pop) ו־הצצה לראש (top).

לעיתים מגדירים גם אתחול (init) ובדיקה אם ריקה (isEmpty).

ניתן להגדיר את הפעולות כפונקציות שמחזירות מחסנית חדשה. הן מקיימות כמה תנאים חשובים:
- ראש המחסנית אחרי הוספה של i הוא i. כלומר top(push(i,S)) = i.
- אם מוסיפים איבר ואז מסירים אותו מקבלים את המחסנית המקורית: pop(push(i,S)) = S.
- אתחול יוצר מחסנית ריקה: isEmpty(init()) = true.
- אם הוספת איבר למחסנית היא כבר לא ריקה: isEmpty(push(i,S)) = false.

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

דוגמה לא־טריוויאלית: אפשר לראות את המספרים הטבעיים כמחסנית שבה init מחזירה 0, push מוסיף 1 ו־pop מפחית 1. באופן זה מחסנית יכולה לייצג את המספרים הטבעיים ולהיפך.

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

יש מספר דרכים לממש מחסנית. מימושים שונים עלולים לאפשר מצבים לא תקינים אם לא מטפלים בקפידה.

מחסנית היא דרך לארגן פריטים. היא דומה למחסנית רובה.
מה שנכנס אחרון יוצא ראשון. זה נקרא LIFO (נכנס אחרון יוצא ראשון).


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

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

כללים פשוטים חשובים:
- אחרי שמוסיפים פריט, הראש הוא הוא הפריט הזה.
- אם מוסיפים ואז מסירים את אותו פריט, המחסנית חוזרת למה שהיתה.
- אתחול יוצר מחסנית ריקה.
- אם הוספת פריט, היא כבר לא ריקה.

אפשר להגדיר הסרת פריט ממחסנית ריקה כהחזרת שגיאה, או כפעולה שלא משנה דבר.

במחשבים משתמשים במחסנית לשמור כתובת לחזרה אחרי קריאה ולשמור משתנים מקומיים.
מחסנית עוזרת גם לעבור על עצים, למשל באמצעות שיטה שנקראת חיפוש לעומק (DFS).

ניתן לממש מחסנית בדרכים שונות. יש לשים לב שלא יווצרו מצבים לא תקינים.