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