מחסנית (Stack)

מחסנית (באנגלית: Stack), הינו מבנה נתונים מופשט הפועל בצורה דומה למחסנית של רובה.

למה הכוונה “מבנה נתונים מופשט”?

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

Stack

 

על מנת להבין כיצד עובד המבנה נהוג לייצר מחסנית (לאורך כמובן) כמו בציור מצד שמאל. (ראשי תיבות: Last In First Out), ז”א שבדיוק כמו במחסנית, האיבר האחרון שנכנס הוא הראשון שיוצא (או הראשון שנכנס הוא האחרון לצאת).

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

 

הפעולות הבסיסיות:

דחיפה - הכנסת איבר חדש (לראש) המחסנית. קוד:

PUSH (S, x)
  top[S] <- top[S] + 1
  S[top[S]] <- x
  • S הוא שם המחסנית.
  • x הוא האיבר החדש שאותו אנו מכניסים למחסנית.
  • top הוא מצביע, המצביע על האיבר האחרון במחסנית.
  • נגדיל את top באחד (כדי שהמחסנית תכיל עוד תא).
  • נכניס את x ל top החדש.

 

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

POP (S)
if (EMPTY (S))
  then error "underflow"
else top[S] <- top[S] - 1
  return S[top[S] + 1]
  • S הוא שם המחסנית.
  • אם המחסנית ריקה, נחזיר הודעת שגיאה.
  • אחרת (ז”א שאינה ריקה), נזיז את top אחד אחורה (ז”א ש top יצביע על הערך שלפני האחרון. וכך בעצם הקטנו את המחסנית).
  • ונחזיר את top ועוד 1 (ז”א הערך שהוצאנו בסעיף למעלה מחוץ למחסנית).

 

בנוסף,נדגים את פעולות השינוי Pop ו Push:

Push & Pop Example

מימוש המחסנית S מתבצע באמצעות מערך. איברי המחסנית מופיעים רק במשבצות הבהירות. (i) המחסנית S מכילה 4 איברים; האיבר הנמצא בראשה הוא 9. (ii) המחסנית S אחרי הקריאות (PUSH(S,17 ו (PUSH(S,3. בשלב הבא, (iii), המחסנית S אחרי הקריאה (POP(S החזירה את האיבר 3, שהוא האיבר האחרון שהוכנס למחסנית. על אף שהאיבר 3 עדיין מופיע במערך, הוא אינו שייך עוד למחסנית; בראש המחסנית נמצא האיבר 17. (כל אחת מהפעולות האלו מתבצעת בזמן ריצה (O(1).

 

לפעמים (בעיקר בשביל הנוחות), מוגדרות על מחסנית פעולות נוספות: האם ריקה? - הפעולה מחזירה true או false אם המחסנית ריקה או לא (בהתאמה).
קוד:

EMPTY (S)
if (top[S] = 0)
  return True
else
  return False
  • S הוא שם המחסנית.
  • אם [top[S ריק (ז”א שווה 0), אז אין איברים במחסנית, ולכן מחזירים true.
  • אחרת נחזיר false.

 

הצצה - פעולה המחזירה את ערכו של האיבר בראש המחסנית (מבלי להוציאו מהמחסנית). [top[s משמש כאינדקס של האיבר האחרון שהוכנס.
קוד:

STACK-TOP (S)
if EMPTY(S)
  then error "underflow"
return S[top[S]]
  • S הוא שם המחסנית.
  • נבדוק האם המחסנית ריקה, במידה וריקה נחזיר הודעת שגיאה.
  • כל עוד המחסנית אינה ריקה, מחזירים את הערך במחסנית (/מערך) S במקום top.

 

לסיכום

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

בנוסף, יש לציין כי מצב בו מבוצעת פעולת שליפה על מחסנית ריקה מכונה חמיקה (Underflow) ונחזיר בו הודעת שגיאה, מנגד מצב בו [top[S גדול מ n מכונה גלישה (Overflow), ובפסאודו-קוד שלעיל לא טיפלנו במצבים אלה.