מחסנית (מבנה נתונים)
מתוך ויקיפדיה, האנציקלופדיה החופשית
מחסנית היא מבנה נתונים הפועל בצורה דומה לזו של מחסנית רובה: האיבר שנכנס ראשון למחסנית יוצא ממנה אחרון (תכונה זו מכונה נכנס אחרון יוצא ראשון - LIFO).
רעיון המחסנית מופיע כבר בפירוש רש"י (בראשית, כה כו) העוסק בהולדת יעקב ועשו, ובו מדמה רש"י את הרחם למחסנית. בלשונו של רש"י: "צא ולמד משפופרת שפיה קצרה, תן בה שתי אבנים זו תחת זו - הנכנסת ראשונה תצא אחרונה, והנכנסת אחרונה תצא ראשונה".
[עריכה] פעולות על המחסנית
שתי הפעולות הבסיסיות במחסנית הן:
- דחיפה (Push) - הכנסת איבר חדש לראש המחסנית ודחיקת שאר האיברים במחסנית פנימה. מכיוון שגודל המחסנית לרוב מוגבל, פעולה זו עלולה לגרום לגלישה (Overflow) מהמחסנית כאשר לא נותר בה מקום לאיבר החדש.
- שליפה (Pop) - פעולה המוציאה את האיבר העליון מהמחסנית, מחזירה את ערכו, ומקדמת את שאר איברי המחסנית לעבר ראשה. מצב של שליפת איבר ממחסנית ריקה מכונה מצב "חמיקה". (Underflow)
לעתים, מוגדרות במחסנית גם פעולות נוספות:
- הצצה (Peek/Top) - פעולה המחזירה את ערכו של האיבר העליון במחסנית מבלי להוציא אותו מהמחסנית.
- האם_המחסנית_ריקה? (IsEmpty) - פעולה הקובעת האם מחסנית נתונה ריקה.
- שכפול (Dup) - פעולה המשכפלת את האיבר העליון במחסנית.
- החלפה (Swap) - פעולה המחליפה בין שני התאים העליונים ביותר במחסנית. (ניתן להגדיר גם פונקציות ההופכות את סדרם של מספר גדול יותר של איברים)
[עריכה] יישומי המחסנית
מחסנית היא מבנה נתונים בסיסי במימוש שפות תכנות. במעבדים רבים קיים אוגר מיוחד המשמש כמצביע למחסנית, ובשפת המכונה של מעבדים אלו ממומשת הקריאה לתת-שיגרה על ידי הכנסת כתובת החזרה למחסנית. ברוב השפות העיליות נשמרים גם המשתנים המקומיים במבנה המחסנית הנתמך במעבד.
[עריכה] מימוש מחסנית
ישנם שני מימושים עיקריים למחסנית:
- מקום רציף בזיכרון המוקצה מראש לצורך שימוש במחסנית. זהו המימוש הפשוט יותר, הנתמך על-ידי המעבד באופן פנימי.
- מימוש באמצעות רשימה מקושרת, כאשר בכל פעולת דחיפה האיבר החדש מתווסף לראש הרשימה. זהו מימוש יעיל פחות, אבל גם מאפשר גמישות רבה יותר, כיוון שאינו דורש מקום רציף דווקא והקצאת זיכרון מראש.
