Generic Stack

جزء من قسم Object Oriented Programming في رحلة C على Coddy — الدرس 60 من 61.

التحدي

سهل

تعد المكدس (stack) بنية بيانات أساسية تتبع مبدأ "آخر من يدخل هو أول من يخرج" (LIFO) — أي أن آخر عنصر تمت إضافته هو أول عنصر يتم إزالته. فكر في الأمر كمجموعة من الأطباق المتراصة فوق بعضها: أنت تضيف طبقاً إلى الأعلى وتزيل طبقاً من الأعلى.

لنقم ببناء مكدس عام (Generic Stack) — وهو بنية بيانات متعددة الاستخدامات يمكنها تخزين أي نوع من البيانات باستخدام مؤشرات void*. سيتبع المكدس الخاص بك مبدأ "آخر من يدخل هو أول من يخرج"، مع استكمال جميع العمليات الأساسية.

ستقوم بتنظيم الكود الخاص بك عبر ثلاثة ملفات:

stack.h: قم بتعريف هيكل Stack بثلاثة أعضاء: مصفوفة void** للعناصر، ومتغير int لمؤشر العنصر العلوي (الفتحة الفارغة التالية)، ومتغير int للسعة (capacity). قم بالتصريح عن النماذج الأولية للدوال لإنشاء مكدس (يأخذ السعة)، ودفع عنصر (push)، وسحب عنصر (pop)، وإلقاء نظرة على العنصر العلوي (peek)، والتحقق مما إذا كان المكدس فارغاً، وتحرير المكدس.
stack.c: قم بتنفيذ المكدس العام الخاص بك:
- create_stack — يخصص Stack على الذاكرة الحيوية (heap)، ويخصص مصفوفة العناصر بالسعة المعطاة، ويضبط top إلى 0، ويعيد المؤشر.
- push — يضيف عنصراً إلى الأعلى إذا كانت هناك مساحة (عندما يكون top أقل من capacity).
- pop — يزيل ويعيد العنصر العلوي، أو يعيد NULL إذا كان المكدس فارغاً.
- peek — يعيد العنصر العلوي دون إزالته، أو NULL إذا كان فارغاً.
- is_empty — يعيد 1 إذا كان المكدس لا يحتوي على عناصر، و 0 خلاف ذلك.
- free_stack — يحرر مصفوفة العناصر أولاً، ثم هيكل Stack نفسه.
main.c: اقرأ عدد العمليات المطلوب تنفيذها. ثم لكل عملية، اقرأ أمراً: push متبوعاً بقيمة صحيحة، أو pop، أو peek. أنشئ مكدساً بسعة 10. بالنسبة لـ push، خصص عدداً صحيحاً على الذاكرة الحيوية (heap) وادفع مؤشره. بالنسبة لـ 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* — المستدعي هو المسؤول عن تخصيص وتحرير البيانات الفعلية. عند استخدام pop، قم بتحويل 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: إنشاء مكدس (stack) بسعة 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: تخصيص عدد صحيح في الذاكرة الحيوية (heap) ودفع المؤشر الخاص به
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: سحب العنصر من المكدس
            // - إذا لم يكن NULL، اطبع القيمة وقم بتحرير الذاكرة للعدد الصحيح
            // - إذا كان NULL (المكدس فارغ)، اطبع "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: إلقاء نظرة على العنصر العلوي
            // - إذا لم يكن NULL، اطبع القيمة (بدون إزالة أو تحرير)
            // - إذا كان NULL (المكدس فارغ)، اطبع "empty"
        }
    }
    
    // TODO: تحرير أي عناصر متبقية في المكدس
    // TODO: تحرير المكدس نفسه
    
    return 0;
}