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

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

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

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

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

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

• אתחול (init) - יצירה של מחסנית חדשה.
• דחיפה (push) - הכנסת איבר חדש לראש המחסנית.
• שליפה (pop) - פעולה המוציאה את האיבר העליון מהמחסנית.

פעולות נוספות

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

• האם_המחסנית_ריקה? (isEmpty) - פעולה המחזירה true אם מחסנית נתונה ריקה, ואחרת מחזירה false.
• הצצה (peek/top) - פעולה המחזירה את ערכו של האיבר העליון במחסנית מבלי להוציא אותו מהמחסנית. פעולה זו איננה חיונית אם מגדירים את פעולת השליפה ככזאת שמבצעת פעולת הצצה וגם משנה את המחסנית.

פונקציות

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

1. ראש המחסנית הוא האיבר האחרון שהוכנס למחסנית. כלומר top(push(i,S)) = i
2. אם מוסיפים איבר ואז מסירים איבר מקבלים את המחסנית המקורית. כלומר pop(push(i,S)) = s
3. אתחול מחסנית יוצר מחסנית ריקה. isEmpty(init()) = true
4. כל מחסנית שהוסיפו לה יותר איברים משהסירו איננה ריקה. isEmpty(push(i,S)) = false

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

את פעולת ההסרה ניתן להגדיר על מחסנית ריקה ככזאת שמחזירה את אותה המחסנית. לחלופין, ניתן להימנע מלהגדיר אותה, או להגדיר אותה כמחזירה ערך שגיאה מיוחד. באופן דומה, (()top(init (בדיקת ראש מחסנית ריקה) ניתן להגדיר כמחזירה שגיאה, או להימנע מהגדרתה.

חשוב לשים לב לכך שכל אוסף של פונקציות וערכים המקיים את התנאים האלה נחשב למחסנית. דוגמה לא-טריוויאלית לכך היא קבוצת המספרים הטבעיים, עבור הפעולות "החזר 0" (אתחול), "הוסף 1"(push), "הפחת 1"(pop), "האם_אפס"(isEmpty). בכיוון השני ניתן לומר שכל מחסנית עשויה להוות ייצוג למספרים הטבעיים.

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

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

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

מימוש מחסנית

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

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

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

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

ראו גם

• מחסנית קריאות
• אוטומט מחסנית

קישורים חיצוניים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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