מחסנית גנרית

חלק מהיחידה תכנות מונחה עצמים במסלול ה-C של Coddy. שיעור 60 מתוך 61.

אתגר

קל

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

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

תארגנו את הקוד שלכם בשלושה קבצים:

stack.h: הגדירו את המבנה Stack עם שלושה איברים: מערך void** לפריטים, ערך int לאינדקס העליון (המקום הפנוי הבא), וערך int לקיבולת. הכריזו על אבות־טיפוס של פונקציות ליצירת מחסנית (מקבלת קיבולת), לדחיפת פריט, לשליפת פריט, להצצה בפריט העליון, לבדיקה אם המחסנית ריקה ולשחרור המחסנית.
stack.c: ממשו את המחסנית הגנרית שלכם:
- create_stack: מקצה מחסנית בערימה, מקצה את מערך הפריטים בקיבולת הנתונה, מאתחלת את top ל־0 ומחזירה את המצביע
- push: מוסיפה פריט לראש המחסנית אם יש מקום (כאשר top קטן מהקיבולת)
- pop: מסירה ומחזירה את הפריט העליון, או מחזירה NULL אם המחסנית ריקה
- peek: מחזירה את הפריט העליון בלי להסיר אותו, או מחזירה NULL אם המחסנית ריקה
- is_empty: מחזירה 1 אם אין פריטים במחסנית, ו־0 אחרת
- free_stack: משחררת תחילה את מערך הפריטים, ולאחר מכן את מבנה Stack עצמו
main.c: קראו את מספר הפעולות לביצוע. לאחר מכן, עבור כל פעולה, קראו פקודה: push ואחריה ערך שלם, pop או peek. צרו מחסנית בקיבולת 10. עבור push, הקצו מספר שלם בערימה ודחפו את המצביע אליו. עבור pop, שלפו את הפריט, הדפיסו את ערכו ושחררו את המספר השלם. עבור peek, הדפיסו את הערך בלי להסיר אותו. אם קוראים ל־pop או ל־peek כשהמחסנית ריקה, הדפיסו empty. לאחר כל הפעולות, שחררו את הפריטים שנותרו ואת המחסנית.

התוכנית שלכם תקבל:

את מספר הפעולות
כל פעולה בשורה נפרדת (push X, pop או peek)

פלט לדוגמה כאשר הקלט הוא 5, ואז push 10, push 20, peek, pop, pop:

20
20
10

פלט לדוגמה כאשר הקלט הוא 3, ואז pop, push 42, peek:

empty
42

פלט לדוגמה כאשר הקלט הוא 4, ואז push 5, push 15, pop, pop:

15
5

זכרו שהמחסנית שלכם מאחסנת מצביעי void*: האחריות להקצאה ולשחרור של הנתונים עצמם מוטלת על הקוד שקורא לה. בעת שליפה, המירו את void* המוחזר בחזרה ל־int* כדי לגשת לערך. השתמשו ב־strcmp מתוך <string.h> כדי להשוות בין מחרוזות הפקודות.

נסו בעצמכם

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: צור מחסנית בקיבולת 10
    
    // TODO: עבד כל פעולה
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: הקצה מספר שלם בערימה ודחוף מצביע אליו למחסנית
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: שלוף את הפריט מהמחסנית
            // - אם אינו NULL, הדפס את הערך ושחרר את המספר השלם
            // - אם הוא NULL (מחסנית ריקה), הדפס "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: הצץ בפריט העליון במחסנית
            // - אם אינו NULL, הדפס את הערך (אל תסיר או תשחרר אותו)
            // - אם הוא NULL (מחסנית ריקה), הדפס "empty"
        }
    }
    
    // TODO: שחרר את כל הפריטים שנותרו במחסנית
    // TODO: שחרר את המחסנית עצמה
    
    return 0;
}