دليل للأكوام في بايثون

المُقدّمة

في حين أن بعض هياكل البيانات متعددة الاستخدامات ويمكن استخدامها في نطاق واسع من التطبيقات، فإن بعضها الآخر متخصص ومصمم للتعامل مع مشكلات محددة. أحد هذه الهياكل المتخصصة، والمعروف ببساطته وفائدته الرائعة، هو كومة.

إذن، ما هو المكدس؟ المكدس في جوهره عبارة عن بنية بيانات خطية تتبع LIFO مبدأ (ما يدخل أولا يخرج أولا).. فكر في الأمر ككومة من الأطباق في الكافيتيريا؛ أنت تأخذ فقط اللوحة الموجودة في الأعلى، وعند وضع لوحة جديدة، فإنها تذهب إلى أعلى المكدس.

العنصر الأخير المضاف هو العنصر الأول الذي سيتم إزالته

ولكن لماذا يعد فهم المكدس أمرًا بالغ الأهمية؟ على مر السنين، وجدت الأكوام تطبيقاتها في عدد كبير من المجالات، بدءًا من إدارة الذاكرة بلغات البرمجة المفضلة لديك وحتى وظيفة زر الرجوع في متصفح الويب الخاص بك. هذه البساطة الجوهرية، إلى جانب إمكانية تطبيقها على نطاق واسع، تجعل المكدس أداة لا غنى عنها في ترسانة المطور.

في هذا الدليل، سنتعمق في المفاهيم الكامنة وراء الأكوام وتنفيذها وحالات الاستخدام وغير ذلك الكثير. سنحدد ماهية المكدسات، وكيفية عملها، وبعد ذلك، سنلقي نظرة على طريقتين من أكثر الطرق شيوعًا لتنفيذ بنية بيانات المكدس في بايثون.

المفاهيم الأساسية لبنية بيانات المكدس

المكدس في جوهره بسيط بشكل خادع، ومع ذلك فهو يمتلك فروقًا دقيقة تمنحه تطبيقات متعددة الاستخدامات في المجال الحسابي. قبل الغوص في تطبيقاتها واستخداماتها العملية، دعونا نتأكد من فهم راسخ للمفاهيم الأساسية المحيطة بالمكدسات.

مبدأ LIFO (الأخير يخرج أولاً).

LIFO هو المبدأ التوجيهي وراء المكدس. وهذا يعني أن العنصر الأخير الذي يدخل المكدس هو أول عنصر يغادر. تميز هذه الخاصية المكدسات عن هياكل البيانات الخطية الأخرى، مثل قوائم الانتظار.

العمليات الأساسية

يتم تعريف كل بنية بيانات من خلال العمليات التي تدعمها. بالنسبة للمكدسات، تعتبر هذه العمليات واضحة ولكنها حيوية:

• دفع - إضافة عنصر إلى أعلى المكدس. إذا كانت المكدس ممتلئة، فقد تؤدي هذه العملية إلى تجاوز سعة المكدس.

• فرقعة - إزالة وإرجاع العنصر العلوي للمكدس. إذا كانت المكدسة فارغة، فقد تؤدي محاولة الانبثاق إلى حدوث تدفق سفلي للمكدس.

• نظرة خاطفة (أو أعلى) - ملاحظة العنصر العلوي دون إزالته. تكون هذه العملية مفيدة عندما تريد فحص العنصر العلوي الحالي دون تغيير حالة المكدس.

الآن، يجب أن تكون أهمية بنية بيانات المكدس ومفاهيمها الأساسية واضحة. وبينما نمضي قدمًا، سنتعمق في تطبيقاتها، ونلقي الضوء على كيفية ترجمة هذه المبادئ الأساسية إلى تعليمات برمجية عملية.

كيفية تنفيذ المكدس من الصفر في بايثون

بعد أن فهمنا المبادئ الأساسية وراء الأكوام، حان الوقت لنشمر عن سواعدنا ونتعمق في الجانب العملي للأشياء. على الرغم من أن تنفيذ المكدس بسيط، إلا أنه يمكن التعامل معه بطرق متعددة. في هذا القسم، سنستكشف طريقتين أساسيتين لتنفيذ المكدس - استخدام المصفوفات والقوائم المرتبطة.

تنفيذ المكدس باستخدام المصفوفات

المصفوفات، كونها مواقع الذاكرة المتجاورة، تقدم وسيلة بديهية لتمثيل الأكوام. إنها تسمح بتعقيد الوقت O(1) للوصول إلى العناصر عن طريق الفهرس، مما يضمن عمليات الدفع السريع والبوب ​​والنظرة الخاطفة. بالإضافة إلى ذلك، يمكن أن تكون المصفوفات أكثر كفاءة في الذاكرة نظرًا لعدم وجود حمل للمؤشرات كما هو الحال في القوائم المرتبطة.

من ناحية أخرى، المصفوفات التقليدية لها حجم ثابت، مما يعني أنه بمجرد تهيئتها، لا يمكن تغيير حجمها. هذا يمكن أن يؤدي إلى كومة الفائض إذا لم يتم رصدها. يمكن التغلب على ذلك من خلال المصفوفات الديناميكية (مثل صفائف Python list)، والتي يمكن تغيير حجمها، ولكن هذه العملية مكلفة للغاية.

مع كل ذلك، فلنبدأ في تنفيذ فئة المكدس الخاصة بنا باستخدام المصفوفات في بايثون. أولاً، لنقم بإنشاء فئة نفسها، باستخدام المنشئ الذي يأخذ حجم المكدس كمعلمة:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

كما ترون، قمنا بتخزين ثلاث قيم في صفنا. ال size هو الحجم المطلوب للمكدس، و stack هو المصفوفة الفعلية المستخدمة لتمثيل بنية بيانات المكدس، و top هو فهرس العنصر الأخير في stack المصفوفة (الجزء العلوي من المكدس).

من الآن فصاعدًا، سنقوم بإنشاء وشرح طريقة واحدة لكل عملية من عمليات المكدس الأساسية. سيتم تضمين كل من هذه الأساليب ضمن Stack فئة قمنا بإنشائها للتو.

دعونا نبدأ مع push() طريقة. كما ناقشنا سابقًا، تضيف عملية الدفع عنصرًا إلى أعلى المكدس. أولاً، سوف نتحقق مما إذا كان لدى المكدس أي مساحة متبقية للعنصر الذي نريد إضافته. إذا كانت المكدس ممتلئة، فسنقوم برفع Stack Overflow استثناء. بخلاف ذلك، سنقوم فقط بإضافة العنصر وضبطه top و stack وفقا لذلك:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

الآن، يمكننا تحديد طريقة إزالة عنصر من أعلى المكدس - pop() طريقة. قبل أن نحاول إزالة عنصر ما، سنحتاج إلى التحقق مما إذا كان هناك أي عناصر في المكدس لأنه لا فائدة من محاولة إخراج عنصر من مكدس فارغ:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

وأخيرا، يمكننا تحديد peek() الطريقة التي تُرجع فقط قيمة العنصر الموجود حاليًا في الجزء العلوي من المكدس:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

وهذا كل شيء! لدينا الآن فصل ينفذ سلوك المكدسات باستخدام القوائم في بايثون.

تنفيذ المكدس باستخدام القوائم المرتبطة

القوائم المرتبطة، يجري هياكل البيانات الديناميكية، يمكن أن تنمو وتتقلص بسهولة، مما قد يكون مفيدًا في تنفيذ الأكوام. نظرًا لأن القوائم المرتبطة تخصص الذاكرة حسب الحاجة، يمكن للمكدس أن ينمو ويقلل ديناميكيًا دون الحاجة إلى تغيير حجم واضح. فائدة أخرى لاستخدام القوائم المرتبطة لتنفيذ المكدسات هي أن عمليات الدفع والبوب ​​تتطلب فقط تغييرات بسيطة في المؤشر. الجانب السلبي لذلك هو أن كل عنصر في القائمة المرتبطة يحتوي على مؤشر إضافي، مما يستهلك ذاكرة أكبر مقارنة بالمصفوفات.

كما ناقشنا بالفعل في "قوائم بايثون المرتبطة" المقالة، أول شيء نحتاج إلى تنفيذه قبل أن تكون القائمة المرتبطة الفعلية عبارة عن فئة لعقدة واحدة:

class Node: def __init__(self, data): self.data = data self.next = None

يقوم هذا التنفيذ بتخزين نقطتين فقط من البيانات - القيمة المخزنة في العقدة (data) والإشارة إلى العقدة التالية (next).

الآن يمكننا الانتقال إلى فئة المكدس الفعلية نفسها. سيكون المنشئ مختلفًا قليلاً عن السابق. سيحتوي على متغير واحد فقط – الإشارة إلى العقدة الموجودة أعلى المكدس:

class Stack: def __init__(self): self.top = None

كما هو متوقع push() تضيف الطريقة عنصرًا جديدًا (عقدة في هذه الحالة) إلى الجزء العلوي من المكدس:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

• pop() تتحقق الطريقة من وجود أي عناصر في المكدس وتزيل العنصر العلوي إذا لم تكن المكدس فارغة:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

وأخيرا، peek() تقرأ الطريقة ببساطة قيمة العنصر من أعلى المكدس (إذا كان هناك عنصر):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

يعتمد الاختيار بين المصفوفات والقوائم المرتبطة على المتطلبات والقيود المحددة للتطبيق.

كيفية تنفيذ المكدس باستخدام بنيات بايثون المدمجة

بالنسبة للعديد من المطورين، قد لا يكون بناء المكدس من الصفر، على الرغم من أنه تعليمي، الطريقة الأكثر فعالية لاستخدام المكدس في تطبيقات العالم الحقيقي. ولحسن الحظ، فإن العديد من لغات البرمجة الشائعة تأتي مجهزة بهياكل بيانات وفئات مدمجة تدعم عمليات المكدس بشكل طبيعي. في هذا القسم، سنستكشف عروض بايثون في هذا الصدد.

بايثون، كونها لغة متعددة الاستخدامات وديناميكية، لا تحتوي على فئة مكدس مخصصة. ومع ذلك، فإن هياكل البيانات المضمنة، وخاصة القوائم وفئة deque من collections الوحدة النمطية، يمكن أن تكون بمثابة مكدسات دون عناء.

استخدام قوائم بايثون كمكدسات

يمكن لقوائم Python محاكاة المكدس بشكل فعال نظرًا لطبيعتها الديناميكية ووجود طرق مثل append() و pop().

• عملية الدفع - تعد إضافة عنصر إلى أعلى المكدس أمرًا بسيطًا مثل استخدام ملف append() الأسلوب:

  stack = []
  stack.append('A')
  stack.append('B')
  

• عملية البوب - يمكن إزالة العنصر العلوي باستخدام pop() الطريقة بدون أي وسيطة:

  top_element = stack.pop() 

• عملية نظرة خاطفة يمكن الوصول إلى الجزء العلوي دون ظهوره باستخدام الفهرسة السلبية:

  top_element = stack[-1] 

باستخدام صف مزدوج الذيل فئة من مجموعات وحدة

• deque (اختصار لقائمة الانتظار ذات النهاية المزدوجة) هي أداة أخرى متعددة الاستخدامات لتطبيقات المكدس. لقد تم تحسينه من أجل الإلحاق والانبثاق السريع من كلا الطرفين، مما يجعله أكثر كفاءة قليلاً في عمليات المكدس مقارنة بالقوائم.

• التهيئة:

  from collections import deque
  stack = deque()
  

• عملية الدفع - على غرار القوائم، append() يتم استخدام الطريقة:

  stack.append('A')
  stack.append('B')
  

• عملية البوب - مثل القوائم، pop() الطريقة تؤدي المهمة:

  top_element = stack.pop() 

• عملية نظرة خاطفة – النهج هو نفسه كما هو الحال مع القوائم:

  top_element = stack[-1] 

متى تستخدم أي؟

بينما يمكن استخدام كل من القوائم وdeques كمكدسات، إذا كنت تستخدم البنية بشكل أساسي كمكدس (مع الإلحاقات والملوثات العضوية الثابتة من طرف واحد)، فإن deque يمكن أن يكون أسرع قليلاً بسبب تحسينه. ومع ذلك، بالنسبة لمعظم الأغراض العملية وما لم تتعامل مع التطبيقات ذات الأداء الحرج، فإن قوائم بايثون ستكون كافية.

المشكلات المحتملة المتعلقة بالمكدس وكيفية التغلب عليها

على الرغم من أن الأكوام متعددة الاستخدامات وفعالة بشكل لا يصدق، مثل أي بنية بيانات أخرى، إلا أنها ليست محصنة ضد المخاطر المحتملة. من الضروري التعرف على هذه التحديات عند العمل مع الأكوام ووضع استراتيجيات لمعالجتها. في هذا القسم، سنتعمق في بعض المشكلات الشائعة المتعلقة بالمكدس ونستكشف طرقًا للتغلب عليها.

تجاوز المكدس

يحدث هذا عند إجراء محاولة لدفع عنصر إلى مكدس وصل إلى سعته القصوى. إنها مشكلة خاصة في البيئات التي يكون فيها حجم المكدس ثابتًا، كما هو الحال في بعض سيناريوهات البرمجة ذات المستوى المنخفض أو استدعاءات الوظائف العودية.

إذا كنت تستخدم مكدسات قائمة على المصفوفات، ففكر في التبديل إلى المصفوفات الديناميكية أو تطبيقات القائمة المرتبطة، والتي تغير حجمها بنفسها. هناك خطوة أخرى لمنع تجاوز سعة المكدس وهي مراقبة حجم المكدس بشكل مستمر، خاصة قبل عمليات الدفع، وتوفير رسائل خطأ واضحة أو مطالبات بتجاوز سعة المكدس.

إذا حدث تجاوز سعة المكدس بسبب الاستدعاءات المتكررة المفرطة، ففكر في الحلول التكرارية أو قم بزيادة حد التكرار إذا كانت البيئة تسمح بذلك.

مكدس التدفق

يحدث هذا عندما تكون هناك محاولة لإخراج عنصر من مكدس فارغ. لمنع حدوث ذلك، تحقق دائمًا مما إذا كانت المكدس فارغة قبل تنفيذ عمليات البوب ​​أو النظرة الخاطفة. قم بإرجاع رسالة خطأ واضحة أو التعامل مع التدفق السفلي بأمان دون تعطل البرنامج.

في البيئات التي يكون فيها ذلك مقبولاً، فكر في إرجاع قيمة خاصة عند الخروج من مكدس فارغ للإشارة إلى عدم صلاحية العملية.

قيود الذاكرة

في البيئات ذات الذاكرة المحدودة، حتى تغيير حجم الأكوام ديناميكيًا (مثل تلك المستندة إلى القوائم المرتبطة) قد يؤدي إلى استنفاد الذاكرة إذا أصبحت كبيرة جدًا. لذلك، راقب استخدام الذاكرة الإجمالي للتطبيق ونمو المكدس. ربما أدخل غطاءًا ناعمًا على حجم المكدس.

مخاوف تتعلق بسلامة الخيط

في البيئات متعددة الخيوط، يمكن أن تؤدي العمليات المتزامنة على مكدس مشترك بواسطة مؤشرات ترابط مختلفة إلى عدم تناسق البيانات أو سلوكيات غير متوقعة. الحلول المحتملة لهذه المشكلة قد تكون:

• كائنات المزامنة والأقفال - استخدم كائنات المزامنة (كائنات الاستبعاد المتبادل) أو الأقفال للتأكد من أن مؤشر ترابط واحد فقط يمكنه تنفيذ العمليات على المكدس في وقت معين.
• العمليات الذرية – الاستفادة من العمليات الذرية، إذا كانت مدعومة من البيئة، لضمان اتساق البيانات أثناء عمليات الدفع والبوب.
• الأكوام المحلية للخيط - في السيناريوهات التي يحتاج فيها كل مؤشر ترابط إلى مكدسه، فكر في استخدام التخزين المحلي لمؤشر الترابط لمنح كل مؤشر ترابط مثيل مكدس منفصل خاص به.

على الرغم من أن الأكوام قوية بالفعل، إلا أن إدراك المشكلات المحتملة وتنفيذ الحلول بشكل فعال سيضمن تطبيقات قوية وخالية من الأخطاء. إن إدراك هذه المخاطر هو نصف المعركة - والنصف الآخر هو تبني أفضل الممارسات لمعالجتها بفعالية.

وفي الختام

على الرغم من طبيعتها البسيطة، إلا أنها تدعم العديد من العمليات الأساسية في عالم الحوسبة. بدءًا من تحليل التعبيرات الرياضية المعقدة وحتى إدارة استدعاءات الوظائف، فإن فائدتها واسعة وأساسية. أثناء رحلتنا عبر خصوصيات وعموميات بنية البيانات هذه، من الواضح أن قوتها لا تكمن في كفاءتها فحسب، بل أيضًا في تنوعها.

ومع ذلك، كما هو الحال مع جميع الأدوات، تعتمد فعاليتها على كيفية استخدامها. فقط تأكد من أن لديك فهمًا شاملاً لمبادئها والمزالق المحتملة وأفضل الممارسات لضمان قدرتك على الاستفادة من القوة الحقيقية للمكدسات. سواء كنت تنفذ واحدًا من الصفر أو تستفيد من المرافق المضمنة بلغات مثل Python، فإن التطبيق الواعي لهياكل البيانات هذه هو الذي سيميز حلولك عن غيرها.

• محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
• PlatoData.Network Vertical Generative Ai. تمكين نفسك. الوصول هنا.
• أفلاطونايستريم. ذكاء Web3. تضخيم المعرفة. الوصول هنا.
• أفلاطون كربون، كلينتك ، الطاقة، بيئة، شمسي، إدارة المخلفات. الوصول هنا.
• أفلاطون هيلث. التكنولوجيا الحيوية وذكاء التجارب السريرية. الوصول هنا.
• المصدر https://stackabuse.com/guide-to-stacks-in-python/