هيكل البيانات هو وسيلة لتنظيم وتخزين المعلومات لضمان الوصول الفعال ومعالجة البيانات. واحدة من هياكل البيانات الأكثر شعبية هي المكدس. وهو نوع البيانات المجردة التي تعمل على مبدأ ليفو (آخر في ، أولا خارج) – آخر في ، أولا خارج. يسمى كل عنصر في المكدس عقدة ويحتوي على بيانات وإشارة إلى العقدة السابقة. يتيح لك تنفيذ العمل مع البيانات كما هو الحال مع المكدس حفظ البيانات واسترجاعها بكفاءة.
وتشمل عمليات كومة إضافة عنصر إلى قمة الرأس (دفع) ، وإزالة عنصر من قمة الرأس (البوب) ، والحصول على قيمة قمة الرأس دون حذف (نظرة خاطفة). يمكن أن يكون تنفيذ العمل مع البيانات كما هو الحال مع المكدس مفيدا في مجموعة متنوعة من المهام ، على سبيل المثال ، عند معالجة التعبيرات الرياضية ، في خوارزميات معالجة الرسم البياني وفي العديد من المجالات الأخرى.
أحد الأمثلة على تنفيذ المكدس هو استخدام بنية بيانات لينكدليست ، وهي سلسلة من العقد المرتبطة ببعضها البعض بواسطة الروابط. في هذه الحالة ، تحتوي كل عقدة على بيانات ورابط للعقدة السابقة. يتيح لك هذا التطبيق إضافة العناصر وإزالتها بكفاءة في الجزء العلوي من المكدس.
ملاحظة: يمكن أيضا تنفيذ تنفيذ المكدس باستخدام مصفوفة ، ومع ذلك ، فإن هذا الأسلوب له بعض القيود في حجم المكدس ويتطلب إعادة تخصيص العناصر عند إضافة العناصر أو إزالتها.
- المكدس: التعريف والمبادئ الأساسية للتشغيل
- هيكل البيانات: ما هو وكيف يساعد في العمل مع البيانات
- تنفيذ المكدس باستخدام قائمة مرتبطة منفردة
- تنفيذ المكدس باستخدام صفيف
- تطبيق المكدس في البرمجة: أمثلة على المهام والخوارزميات
- تقييم فعالية العمل مع المكدس واختيار التنفيذ الأمثل
- سؤال وجواب
- ما هو هيكل البيانات?
- كيف يمكنني تنفيذ العمل مع البيانات كما كومة?
- لماذا استخدام كومة عند العمل مع البيانات?
- ما هي العمليات الأخرى التي يمكن إجراؤها باستخدام المكدس?
- ما أمثلة على استخدام المكدس في البرمجة يمكن أن تعطى?
- ما هو تعقيد عمليات المكدس الأساسية?
المكدس: التعريف والمبادئ الأساسية للتشغيل
المكدس عبارة عن بنية بيانات تستند إلى مبدأ آخر خروج (ليفو). يمكن اعتبار المكدس بمثابة كومة من الألواح ، حيث يتم دائما وضع لوحة جديدة أعلى المكدس ، ويمكن الوصول إلى اللوحة العلوية فقط.
المبادئ الأساسية لعملية المكدس:
- إدخال عنصر (دفع): يتم إضافة عنصر جديد إلى الجزء العلوي من المكدس
- حذف عنصر (بوب): يتم حذف عنصر من أعلى المكدس
- الحصول على العنصر العلوي (أعلى): إرجاع العنصر العلوي من المكدس دون حذفه
- فحص فارغ: يتحقق مما إذا كان المكدس فارغا
- حجم المكدس( الحجم): إرجاع عدد العناصر في المكدس
غالبا ما يتم استخدام المكدس في تنفيذ الخوارزميات والبرامج حيث تحتاج إلى اتباع مبدأ "آخر دخول ، أولا". على سبيل المثال ، عند معالجة الوظائف داخل البرنامج ، تتم إضافة استدعاء الوظيفة إلى المكدس ، وعند اكتمال الوظيفة ، تتم إزالتها من المكدس. يمكن أيضا استخدام المكدس للتحقق من الموضع الصحيح للأقواس في التعبيرات الرياضية.
يمكن تنفيذ المكدس كمصفوفة أو كقائمة مرتبطة منفردة. من المهم أن تكون قادرا على استخدام العمليات بشكل صحيح مع الإدراج والحذف والوصول إلى العنصر العلوي من أجل الحصول على وظيفة المكدس الضرورية.
هيكل البيانات: ما هو وكيف يساعد في العمل مع البيانات
بنية البيانات هي تنسيق خاص لتنظيم البيانات وتخزينها يسمح لك بإجراء العمليات بكفاءة على هذه البيانات. يحدد الترتيب والعلاقات بين عناصر البيانات ، وكذلك العمليات التي يمكن إجراؤها عليها.
يساعد استخدام بنية البيانات على تبسيط العمل مع البيانات وتحسينه. يسمح لك بإجراء عمليات مختلفة بسرعة وكفاءة ، مثل البحث عن العناصر وإضافتها وحذفها وما إلى ذلك. بفضل هياكل البيانات ، يمكنك تحسين أداء البرنامج وتقليل مقدار الذاكرة المستخدمة.
واحدة من هياكل البيانات الأكثر شيوعا هي المكدس. المكدس عبارة عن مجموعة مرتبة من العناصر يتم فيها الوصول إلى العناصر من طرف واحد فقط. في المكدس ، يتم إضافة كل عنصر جديد إلى الجزء العلوي من الهيكل ، ويتم الوصول إلى العناصر في ترتيب آخر في — أولا خارج (ليفو — آخر في ، أولا خارج).
يستخدم المكدس على نطاق واسع في البرمجة عند تنفيذ الخوارزميات وتخزين البيانات المؤقتة. على سبيل المثال ، يمكن استخدام المكدس لتخزين عناوين إرجاع الوظائف عند تنفيذ خوارزميات متكررة ، لتنفيذ تدوين البولندية العكسية ، في أنظمة معالجة الأحداث ، إلخ.
يمكن تنفيذ المكدس باستخدام مصفوفة أو قائمة مرتبطة. في تطبيق باستخدام صفيف ، عادة ما يتم تعيين حجم مكدس ثابت ، مما يحد من عدد العناصر التي يمكن إضافتها إلى المكدس. عند تنفيذها بقائمة مرتبطة ، لا يوجد حد لحجم المكدس ، ولكن يلزم وجود ذاكرة إضافية لتخزين المؤشرات إلى العنصر التالي.
العمل مع المكدس يتضمن عمليات إضافة عنصر إلى المكدس (دفع) ، وإزالة عنصر من المكدس (البوب) وعرض الجزء العلوي من المكدس (أعلى). يتم تنفيذ عمليات الدفع والبوب في وقت ثابت س (1) ، أي أنها لا تعتمد على حجم المكدس (ضمن النطاق المقبول). يتم تنفيذ العملية العليا أيضا في وقت ثابت.
اعتمادا على متطلبات المهمة والأداء ، يمكنك اختيار بنية البيانات الأكثر ملاءمة للعمل مع البيانات. مع الاختيار الصحيح واستخدام بنية البيانات ، يمكن تبسيط البرنامج وتحسينه بشكل كبير.
تنفيذ المكدس باستخدام قائمة مرتبطة منفردة
المكدس عبارة عن بنية بيانات تتكون من مجموعة مرتبة من العناصر التي تحدث فيها إضافة العناصر وإزالتها من طرف واحد فقط — الجزء العلوي من المكدس. وهكذا ، فإن المكدس يعمل على مبدأ" آخر في أول الخروج " (ليفو).
القائمة المرتبطة منفردة هي بنية بيانات تتكون من عقد ، يحتوي كل منها على قيمة ورابط للعقدة التالية. عند تنفيذ مكدس باستخدام قائمة مرتبطة منفردة ، تصبح قيمة كل عقدة عنصرا من عناصر المكدس ، وتصبح الإشارة إلى العقدة التالية مؤشرا إلى أعلى المكدس.
يتضمن تنفيذ المكدس باستخدام قائمة مرتبطة منفردة العمليات التالية:
- دفع-إضافة عنصر إلى الجزء العلوي من المكدس. للقيام بذلك ، يتم إنشاء عقدة جديدة ، ويتم تعيين قيمتها مساوية للعنصر المراد إضافته ، ويشير المؤشر إلى العقدة التالية إلى الجزء العلوي السابق من المكدس. ثم يتم تغيير المؤشر إلى قمة الرأس بحيث يشير إلى العقدة الجديدة.
- البوب-إزالة عنصر من أعلى المكدس. للقيام بذلك ، يتم تخزين قيمة الجزء العلوي من المكدس في متغير مؤقت ، ثم يتم إعادة تعيين المؤشر إلى أعلى المكدس إلى العقدة التالية ، ويتم إرجاع المتغير المؤقت كعنصر محذوف.
- نظرة خاطفة-الحصول على قيمة عنصر في الجزء العلوي من المكدس دون حذفه. للقيام بذلك ، يتم إرجاع قيمة قمة المكدس دون تغيير المؤشر إلى قمة الرأس.
- إيسمبتي-التحقق مما إذا كان المكدس فارغا. للقيام بذلك ، يتم التحقق مما إذا كان المؤشر إلى نقطة الرأس إلى قيمة صفرية.
ميزة تنفيذ كومة باستخدام قائمة مرتبطة منفردة هي مرونة بنية البيانات. على عكس المصفوفة ، لا يقتصر حجم المكدس ، حيث يمكن إضافة عقد القائمة وإزالتها ديناميكيا. بالإضافة إلى ذلك ، يتم تنفيذ عمليات إضافة وإزالة العناصر في وقت ثابت س(1). ومع ذلك ، يتطلب التنفيذ استخدام ذاكرة إضافية لتخزين المؤشرات إلى العقدة التالية.
| العملية | الخوارزمية | التعقيد |
|---|---|---|
| من دفع | قم بإنشاء عقدة جديدة بالقيمة المحددة ورابط للعقدة السابقة. تغيير المؤشر إلى قمة الرأس. | س (1) |
| البوب | احفظ قيمة الرأس في متغير مؤقت. تغيير المؤشر إلى قمة الرأس إلى العقدة التالية. إرجاع القيمة المحفوظة. | س (1) |
| نظرة خاطفة | إرجاع قيمة الرأس. | س (1) |
| إسمبتي | تحقق مما إذا كان المؤشر إلى الرأس يشير إلى قيمة صفرية. | س (1) |
تنفيذ المكدس باستخدام صفيف
المكدس عبارة عن بنية بيانات مرتبة تعمل على مبدأ "آخر دخول ، أول خروج" (ليفو — آخر دخول ، أول خروج). أحد تنفيذ المكدس المحتمل هو استخدام مصفوفة.
عند استخدام صفيف لتنفيذ مكدس ، يجب أن تؤخذ الميزات التالية في الاعتبار:
- تحديد العنصر العلوي من المكدس. كمؤشر للعنصر العلوي ، يمكنك استخدام المتغير العلوي ، والذي يشير إلى آخر عنصر مضاف.
- إضافة عنصر إلى المكدس (دفع). عند إضافة عنصر جديد ، من الضروري زيادة القيمة العليا بمقدار 1 وتعيين قيمة جديدة وفقا للمؤشر الناتج.
- إزالة عنصر من المكدس (البوب). عند حذف عنصر ، من الضروري إرجاع قيمة العنصر الموجود في الفهرس العلوي ، ثم تقليل قيمة الجزء العلوي بمقدار 1.
- التحقق من الفراغ (هوفارغة). يعتبر المكدس فارغا إذا كانت القيمة العليا هي -1.
- الحصول على حجم المكدس. يتم تحديد حجم المكدس من خلال القيمة أعلى + 1.
مثال على تنفيذ مكدس باستخدام مصفوفة في جافا سكريبت:
فئة المكدس {
منشئ () {
هذا.صفيف = [];
هذا.أعلى = -1;
}
دفع (عنصر) {
هذا.أعلى++;
هذا.صفيف [هذا.أعلى] = عنصر;
}
فرقعة () {
إذا (هذا.إسمبتي ()) {
العودة فارغة;
}
عنصر كونست = هذا.صفيف [هذا.أعلى];
هذا.أعلى--;
عنصر الإرجاع;
}
إسمبتي () {
أعد هذا.أعلى = = = -1;
}
الحجم () {
أعد هذا.أعلى + 1;
}
}
عند استخدام تطبيق المكدس هذا ، باستخدام مصفوفة ، يمكنك إجراء عمليات لإضافة العناصر وإزالتها ، والتحقق من الفراغ ، والحصول على حجم المكدس.
تطبيق المكدس في البرمجة: أمثلة على المهام والخوارزميات
المكدس عبارة عن بنية بيانات عبارة عن مجموعة مرتبة من العناصر التي يتم فيها إضافة عناصر جديدة إلى البداية واسترجاعها من البداية (مبدأ ليفو — آخر دخول ، أول خروج).
تستخدم الأكوام على نطاق واسع في البرمجة لحل المشكلات المختلفة وتنفيذ الخوارزميات المختلفة. لنلق نظرة على بعض الأمثلة.
1. التحقق من توازن الأقواس.
أحد الاستخدامات الأكثر شيوعا للمكدس هو التحقق من توازن الأقواس في التعبير. للقيام بذلك ، يمكنك الذهاب من خلال جميع الأحرف من التعبير ، وإذا كان قوس فتح '(' أو '[' يحدث ، ثم وضعه على المكدس. إذا حدث قوس الإغلاق') 'أو'] ' ، فتحقق من أنه يتوافق مع قوس الفتح الأخير في المكدس. إذا كان المكدس فارغا أو كان العنصر الأخير في المكدس عبارة عن قوس فتح من نوع مختلف ، فإن التعبير غير متوازن.
2. عكس صف أو سلسلة من العناصر.
مثال آخر على استخدام المكدس هو قلب صف أو سلسلة من العناصر. في هذه الحالة ، يمكن إضافة كل عنصر إلى المكدس ثم استخراجه بترتيب عكسي ، مما يؤدي إلى قلب الصف أو التسلسل. يمكن أن يكون هذا مفيدا ، على سبيل المثال ، عند العمل مع النص أو عندما تحتاج إلى بيانات الزحف العكسي.
3. حساب التعبير بوستفيكس.
تعبير بوستفيكس (تدوين البولندية العكسي) هو تعبير حسابي يتم فيه وضع المشغل بعد المعاملات. يمكنك استخدام مكدس لحساب تعبير بوستفيكس. من خلال التعبير من اليسار إلى اليمين ، يتم وضع كل معامل على المكدس. عند مواجهة عامل تشغيل ، يتم استخراج المعاملين الأخيرين من المكدس ، ويتم تنفيذ العملية ويتم وضع النتيجة مرة أخرى على المكدس. بعد المرور عبر التعبير بأكمله ، تبقى قيمة واحدة في المكدس — نتيجة حساب التعبير.
4. تجاوز الأشجار.
كما تستخدم المكدس على نطاق واسع لعبور الأشجار. عند عبور الأشجار في العمق (العمق-اجتياز الأول) ، يتم وضع كل عقدة على المكدس. عند الوصول إلى عقدة النهاية أو عدم وجود عقد فرعية ، تتم إزالة العقدة الأخيرة من المكدس ويستمر العبور.
هذه ليست سوى بعض الأمثلة على تطبيقات المكدس في البرمجة. المكدس هو أداة قوية لحل المهام المختلفة وتنفيذ خوارزميات مختلفة. يتيح لك فهم كيفية العمل مع المكدس حل المشكلات بشكل فعال وتحسين رمز البرنامج.
تقييم فعالية العمل مع المكدس واختيار التنفيذ الأمثل
المكدس هو أحد هياكل البيانات الرئيسية ، وهو عبارة عن مجموعة مرتبة من العناصر. يتيح تنفيذ العمل مع البيانات كما هو الحال مع المكدس الاستخدام الفعال للذاكرة ويبسط معالجة البيانات.
يتم تقييم فعالية العمل مع المكدس وفقا لعدة معايير:
- وقت العمليات: لتحديد فعالية العمل مع المكدس ، من الضروري مراعاة وقت تنفيذ العمليات الأساسية ، مثل إضافة عنصر إلى المكدس (الدفع) ، وإزالة عنصر من المكدس (البوب) وعرض العنصر العلوي من المكدس (أعلى). كلما قل الوقت الذي يستغرقه تنفيذ هذه العمليات ، كلما كان تنفيذ المكدس أكثر كفاءة.
- استخدام الذاكرة: تعتمد كفاءة المكدس أيضا على استخدام الذاكرة. يجب أن يشغل تنفيذ المكدس الحد الأدنى من الذاكرة حتى لا يتسبب في حمل غير ضروري وتحسين عملية العمل مع المكدس.
- مقاومة الفائض: يجب أن يكون المكدس مقاوما للفيضان ، أي أنه يجب أن يكون من الممكن التحكم في الحجم والتعامل مع المواقف الاستثنائية عند ملء المكدس إلى أقصى قيمة.
يعتمد اختيار تنفيذ المكدس الأمثل على متطلبات المهمة المحددة:
- صفيف: هذه هي أبسط وأسرع طريقة لتنفيذ مكدس بناء على استخدام صفيف. وقت تنفيذ عمليات الدفع والبوب ثابت وهو س (1) ، ولكنه يتطلب معرفة الحد الأقصى لحجم المكدس مقدما ، والذي قد يكون قيدا.
- قائمة مرتبطة: يتيح لك تنفيذ المكدس استنادا إلى قائمة مرتبطة زيادة حجم المكدس ديناميكيا ولا يتطلب الإعداد المسبق لحجمه الأقصى. وقت تنفيذ عمليات الدفع والبوب هو أيضا ثابت وهو س (1). ومع ذلك ، مطلوب مساحة ذاكرة إضافية لتخزين المؤشرات إلى العنصر التالي في القائمة.
- مجموعة ديناميكية: تنفيذ كومة على أساس مجموعة ديناميكية يجمع بين مزايا مجموعة وقائمة مرتبطة. يسمح لك بزيادة حجم المكدس حسب الحاجة ولديه وقت تنفيذ ثابت لعمليات الدفع والبوب. ومع ذلك ، تشارك الذاكرة في كتلة مستمرة ، والتي يمكن أن تسبب صعوبات في إدارة الذاكرة.
وبالتالي ، يعتمد اختيار تنفيذ المكدس الأمثل على المهمة المحددة ومتطلبات كفاءة المكدس. من الضروري مراعاة وقت تنفيذ العمليات واستخدام الذاكرة ومقاومة الفائض من أجل اختيار خيار تنفيذ المكدس الأنسب.
سؤال وجواب
ما هو هيكل البيانات?
هيكل البيانات هو وسيلة لتمثيل وتنظيم البيانات لغرض الوصول الفعال والتخزين والمعالجة.
كيف يمكنني تنفيذ العمل مع البيانات كما كومة?
يمكن تنفيذ العمل مع البيانات كمكدس باستخدام بنية بيانات خاصة تدعم العمليات التالية: إضافة عنصر إلى الجزء العلوي من المكدس (دفع) ، وإزالة عنصر من أعلى المكدس (البوب) وعرض عنصر في الجزء العلوي من المكدس (نظرة خاطفة).
لماذا استخدام كومة عند العمل مع البيانات?
باستخدام كومة عند العمل مع البيانات يسمح لك لتنفيذ مبدأ ليفو (آخر في أول خارج ، آخر في أول خارج) ، والتي غالبا ما تكون مفيدة لحل بعض المهام. على سبيل المثال ، يمكن استخدام مكدس لتتبع سلسلة من العمليات والعودة إلى حالة سابقة.
ما هي العمليات الأخرى التي يمكن إجراؤها باستخدام المكدس?
بالإضافة إلى عمليات الدفع الأساسية والبوب والنظرة الخاطفة ، يمكن تنفيذ عمليات أخرى باستخدام المكدس ، مثل التحقق من فراغ المكدس (إيسمبتي) والحصول على حجم المكدس (الحجم).
ما أمثلة على استخدام المكدس في البرمجة يمكن أن تعطى?
يستخدم المكدس على نطاق واسع في البرمجة لحل المهام المختلفة. على سبيل المثال ، يمكن استخدامه لتنفيذ خوارزمية بحث العمق أولا ، والتحقق من توازن تعبير الأقواس ، وإجراء عمليات التراجع والإعادة في محرر نصوص ، وغيرها الكثير.
ما هو تعقيد عمليات المكدس الأساسية?
عادة ما يكون تعقيد عمليات المكدس الأساسية(الدفع ، البوب ، النظرة الخاطفة) ثابتا س (1) ، لأنه لا يعتمد على حجم المكدس. يتم تنفيذ العملية إيسيمبتي أيضا في وقت ثابت. ومع ذلك ، فإن تعقيد عملية الحجم يعتمد على تنفيذ المكدس ويمكن أن يكون إما س(1) أو س(ن) في أسوأ الحالات.