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

הצגה פשוטה של מחסנית

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

פעולות על המחסנית

שתי הפעולות הבסיסיות המגדירות מחסנית הן:

• דחיפה (Push) - הכנסת איבר חדש לראש המחסנית.
• שליפה (Pop) - פעולה המוציאה את האיבר העליון מהמחסנית ומחזירה את ערכו (ניתן להגדיר ללא החזרת הערך, אם מוסיפים את פעולת ההצצה, ראו להלן).

לעתים, מוגדרות במחסנית גם פעולות נוספות:

• הצצה (Peek/Top) - פעולה המחזירה את ערכו של האיבר העליון במחסנית מבלי להוציא אותו מהמחסנית.
• האם_המחסנית_ריקה? (IsEmpty) - פעולה הקובעת האם מחסנית נתונה ריקה.
• שכפול (Dup) - פעולה המשכפלת את האיבר העליון במחסנית.
• החלפה (Swap) - פעולה המחליפה בין שני התאים העליונים ביותר במחסנית. (ניתן להגדיר גם פונקציות ההופכות את סדרם של מספר גדול יותר של איברים)

יישומי המחסנית

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

מימוש מחסנית

ישנם מספר דרכים לממש מחסנית:

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

מימושים שונים עלולים לאפשר מצבים לא תקינים:

• מכיוון שגודל המחסנית לעתים מוגבל, דחיפה עלולה לגרום לגלישה (Overflow) מהמחסנית כאשר לא נותר בה מקום לאיבר החדש.
• מצב של שליפת איבר ממחסנית ריקה מכונה מצב "חמיקה" (Underflow).