Generic Stack

جزء من قسم البرمجة كائنية التوجه في رحلة C على Coddy. الدرس 60 من 61.

التحدي

سهل

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

لننشئ مكدسًا عامًا: بنية بيانات متعددة الاستخدامات يمكنها تخزين أي نوع من البيانات باستخدام مؤشرات void*. سيتبع المكدس الذي تنشئه مبدأ الوارد أخيرًا يصرف أولًا، مع جميع العمليات الأساسية.

ستنظم التعليمات البرمجية عبر ثلاثة ملفات:

stack.h: عرّف البنية Stack بثلاثة أعضاء: مصفوفة void** للعناصر، وint لفهرس الموضع العلوي (الخانة التالية الفارغة)، وint للسعة. أعلن نماذج الدوال الخاصة بإنشاء مكدس (تأخذ سعة)، وإضافة عنصر، وإزالة عنصر، والاطلاع على العنصر العلوي، والتحقق مما إذا كان المكدس فارغًا، وتحرير المكدس.
stack.c: نفّذ المكدس العام:
- create_stack: تخصص بنية Stack على heap، وتخصص مصفوفة العناصر بالسعة given، وتهيّئ top إلى 0، وتعيد المؤشر
- push: تضيف عنصرًا إلى الموضع العلوي إذا كانت هناك مساحة (عندما يكون top أصغر من capacity)
- pop: تزيل العنصر العلوي وتعيده، أو تعيد NULL إذا كان المكدس فارغًا
- peek: تعيد العنصر العلوي دون إزالته، أو تعيد NULL إذا كان فارغًا
- is_empty: تعيد 1 إذا لم يكن لدى المكدس أي عناصر، و0 otherwise
- free_stack: تحرر مصفوفة العناصر أولًا، ثم بنية Stack نفسها
main.c: اقرأ عدد العمليات المطلوب تنفيذها. ثم لكل operation، اقرأ command: push متبوعة بقيمة integer، أو pop، أو peek. أنشئ مكدسًا بسعة 10. بالنسبة إلى push، خصص integer على heap وأضف مؤشره. بالنسبة إلى pop، استرجع العنصر، واطبع قيمته، وحرر integer. بالنسبة إلى peek، اطبع القيمة دون إزالتها. إذا تم استدعاء pop أو peek على مكدس فارغ، فاطبع empty. بعد جميع العمليات، حرر أي عناصر متبقية والمكدس.

سيستقبل برنامجك:

عدد العمليات
كل operation في سطر منفصل (push X أو pop أو peek)

ناتج example عندما تكون المدخلات 5، ثم push 10، وpush 20، وpeek، وpop، وpop:

20
20
10

ناتج example عندما تكون المدخلات 3، ثم pop، وpush 42، وpeek:

empty
42

ناتج example عندما تكون المدخلات 4، ثم push 5، وpush 15، وpop، وpop:

15
5

تذكّر أن المكدس يخزن مؤشرات void*: المتصل مسؤول عن تخصيص البيانات الفعلية وتحريرها. عند إزالة عنصر، حوّل void* المُعاد مرة أخرى إلى int* للوصول إلى القيمة. استخدم strcmp من <string.h> لمقارنة سلاسل command.

جرّب بنفسك

#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;
}