3.3 מחסניות

מבנה נתונים ואלגוריתמים

 

 

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

Push - הוספת פריט למחסנית

Pop - הוצאת הפריט שהוכנס אחרון למחסנית

 

לפעמים משתמשים גם בפעולות נוספות:

Top - החזרת ערך הפריט העליון ללא הוצאתו מהמחסנית

Isempty - קביעה באם המחסנית ריקה מפריטים או לא

 

מודל נפוץ למחסנית הוא מתקן לאחסון מטבעות. מטבעות נדחפים (pushed) אחד מעל השני כאשר העליון הוא תמיד האחרון שנוסף, וכאשר לוקחים מטבע, נלקח תמיד המטבע העליון ביותר.

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

 

 

הגדרת מבנה פורמלי של מחסנית נראה כך:

 

typedef struct t_stack *stack;

stack ConsStack( int max_items, int item_size );

/* Construct a new stack

   Pre-condition: (max_items > 0) && (item_size > 0)

   Post-condition: returns a pointer to an empty stack

*/

void Push( stack s, void *item );

/* Push an item onto a stack

   Pre-condition: (s is a stack created by a call to    ConsStack) && (existing item count < max_items) &&

(item != NULL)

   Post-condition: item has been added to the top of s

*/

void *Pop( stack s );

/* Pop an item of a stack

   Pre-condition: (s is a stack created by a call to 

                  ConsStack) &&

                  (existing item count >= 1)

   Post-condition: top item has been removed from s

*/

 

נקודות לתשומת לב:

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

    שבהן השתמשנו לגבי אוסף נתונים כללי. בכל אופן, לאוספי נתונים בעלי תכונות LIFO כגון מחסנית

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

 

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

    היישום השכיח ביותר של מחסנית הוא כאשר המקום לנתונים מוגבל ואז השימוש במחסנית הוא

    טבעי ויעיל (ברוב מערכות ההפעלה הקצאה וביטול הקצאה של זיכרון הן פעולות יקרות יחסית

     - מחיר הגמישות של יישומי רשימה מקושרת).

 

3.3.1 מסגרות מחסנית

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

 

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

 

function f(int x, int y) {

    int a;

    if ( term_cond )return ...;

    a = .....;

    return g(a);

    }

function g(int z) {

                              int p,q;

                                     p = ...; q = ...;

                                     return f(p,q);

                                     }

 

 

ניתן להבחין כיצד כל סביבה של פונקציות f   ו- g (הפרמטרים שלהם ומשתנים מקומיים) נמצאים במסגרת המחסנית. כאשר קוראים ל- f בפעם השניה מתוך g, נוצרת מסגרת חדשה עבור הקריאה השניה לf -.

 

 

 

מושגים

 

Push, Pop

מונחים כלליים להוספת פריט או הסרתו מהמחסנית.

הקשר

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

מלבד משתנים גלובליים מאוחסן במסגרת המחסנית.

מסגרות מחסנית

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

 

 

המשך ל: רקורסיות                    חזור ל: תוכן עניינים