الفرق بين المكدس والصف

• 2019

كلا مكدس و قائمة انتظار كلاهما هي بنية البيانات غير الأولية. الاختلافات الرئيسية بين المكدس وقائمة الانتظار هي أن المكدس يستخدم أسلوب LIFO (الأخير في أول) للوصول إلى عناصر البيانات وإضافة إليها بينما يستخدم Queue أسلوب FIFO (الأول في أول خروج) للوصول إلى عناصر البيانات وإضافتها.

يحتوي تطبيق Stack على طرف واحد مفتوح فقط لدفع عناصر البيانات وفرقعها من ناحية أخرى. يحتوي Quue على نهايتين مفتوحة للتضمين وعزل عناصر البيانات.

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

رسم بياني للمقارنة

أساس للمقارنة	كومة	طابور
مبدأ العمل	LIFO (أخيرًا)	FIFO (أولاً في البداية)
بناء	يتم استخدام النهاية نفسها لإدراج العناصر وحذفها.	يتم استخدام نهاية واحدة للإدخال ، أي النهاية الخلفية ويتم استخدام طرف آخر لحذف العناصر ، أي الواجهة الأمامية.
عدد المؤشرات المستخدمة	واحد	اثنين (في حالة طابور بسيط)
العمليات المنفذة	دفع والبوب	الملعب و dequeue
فحص حالة فارغة	أعلى == -1	الجبهة == -1 || الجبهة == خلفي + 1
فحص حالة كاملة	أعلى == ماكس - 1	الخلفية == ماكس - 1
المتغيرات	ليس لديها المتغيرات.	لديها متغيرات مثل طابور دائري ، وقائمة انتظار ذات أولوية ، وقائمة انتظار انتهت بشكل مضاعف.
التنفيذ	بساطة	معقدة نسبيا

تعريف المكدس

A Stack عبارة عن بنية بيانات خطية غير بدائية. وهي قائمة مرتبة يتم فيها إضافة العنصر الجديد ويتم حذف العنصر الموجود من طرف واحد فقط ، ويُسمى باسم الجزء العلوي من المكدس (TOS). نظرًا لأنه يتم إجراء الحذف والإدراج في مجموعة مكدّسة من الجزء العلوي من الحزمة ، فإن آخر عنصر تمت إضافته سيكون أول عنصر تمت إزالته من المكدس. هذا هو السبب في استدعاء المكدس في قائمة نوع Last-in-First-out (LIFO).

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

مثال

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

تعريف قائمة الانتظار

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

مثال

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

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

1. يتبع Stack آلية LIFO من ناحية أخرى تتبع Queue آلية FIFO لإضافة العناصر وإزالتها.
2. في تكديس ، يتم استخدام النهاية نفسها لإدراج العناصر وحذفها. على العكس ، يتم استخدام طرفين مختلفين في قائمة الانتظار لإدراج العناصر وحذفها.
3. كما يحتوي مكدس نهاية مفتوحة واحدة فقط هو السبب في استخدام مؤشر واحد فقط للإشارة إلى الجزء العلوي من المكدس. لكن قائمة الانتظار تستخدم مؤشرين للإشارة إلى الأمام والنهاية الخلفية لقائمة الانتظار.
4. يقوم Stack بإجراء عمليتين تعرفان باسم push و pop بينما في Queue تعرف باسم enqueue و dequeue.
5. تنفيذ المكدس أسهل بينما يكون تطبيق Queue خادعًا.
6. يحتوي قائمة الانتظار على صيغ متنوعة مثل قائمة انتظار دائرية ، قائمة انتظار ذات أولوية ، قائمة انتظار منتهية مضاعفة ، إلخ. في المقابل ، لا تحتوي بنية تخزين العناصر على متغيرات.

تنفيذ المكدس

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

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

تنفيذ قائمة الانتظار

يمكن تنفيذ قائمة الانتظار بطريقتين:

1. التنفيذ الثابت : في حالة تنفيذ قائمة الانتظار باستخدام المصفوفات ، يجب التأكد من العدد الدقيق للعناصر التي نريد تخزينها في قائمة الانتظار مسبقًا ، لأنه يجب الإعلان عن حجم الصفيف في وقت التصميم أو قبل بدء المعالجة. في هذه الحالة ، ستصبح بداية المصفوفة مقدمة الطابور ، وسيعمل الموقع الأخير للصفيف كخلفية لقائمة الانتظار. تعطي العلاقة التالية العناصر الكاملة في قائمة الانتظار عند تنفيذها باستخدام المصفوفات:
   أمامي - خلفي + 1
   إذا كان "rear <front" ، فلن يكون هناك أي عنصر في قائمة الانتظار أو ستكون قائمة الانتظار فارغة دائمًا.
2. التنفيذ الديناميكي : تنفيذ قوائم الانتظار باستخدام المؤشرات ، يتمثل العيب الرئيسي في أن العقدة في تمثيل مرتبط تستهلك مساحة ذاكرة أكبر من عنصر مناظر في تمثيل الصفيف. نظرًا لوجود حقلين على الأقل في كل عقدة واحدة لحقل البيانات والآخر لتخزين عنوان العقدة التالية ، بينما يوجد حقل البيانات في التمثيل المرتبط فقط. تصبح ميزة استخدام التمثيل المرتبط واضحة عندما يكون مطلوبًا لإدراج عنصر أو حذفه في وسط مجموعة عناصر أخرى.

العمليات على المكدس

العمليات الأساسية التي يمكن تشغيلها على المكدس هي كالتالي:

1. PUSH : عند إضافة عنصر جديد إلى الجزء العلوي من المكدس يُعرف باسم عملية PUSH. يؤدي ضغط عنصر في التكديس إلى إضافة العنصر ، حيث سيتم إدراج العنصر الجديد في الجزء العلوي. بعد كل عملية دفع ، يتم زيادة القمة بواحد. إذا كان الصفيف ممتلئًا ، ولا يمكن إضافة عنصر جديد ، فسيتم تسميته بحالة STACK-FULL أو STACK OVERFLOW. PUSH OPERATION - تعمل في C:
   اعتبار المكدس كما هو
   int stack [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
2. POP : عند حذف عنصر من الجزء العلوي من المكدس ، يُعرف باسم عملية POP. يتم تقليل المكدس بمقدار واحد بعد كل عملية منبثقة. إذا لم يكن هناك أي عنصر على المكدس ويتم تنفيذ البوب ​​، فإن هذا سيؤدي إلى حالة STACK UNDERFLOW والتي تعني أن مجموعتك فارغة. تشغيل POP - الوظائف في C:
   اعتبار المكدس كما هو
   int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

العمليات في قائمة الانتظار

العمليات الأساسية التي يمكن القيام بها في قائمة الانتظار هي:

1. Enqueue : لإدراج عنصر في قائمة انتظار. وظيفة تشغيلية في C:
   يتم الإعلان عن قائمة الانتظار باسم
   int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}

2. Dequeue : لحذف عنصر من قائمة الانتظار. وظيفة تشغيلية في C:
   يتم الإعلان عن قائمة الانتظار باسم
   int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

تطبيقات المكدس

• تحليل في مترجم.
• جافا الجهاز الظاهري.
• التراجع في معالج النصوص.
• زر العودة في متصفح الويب.
• لغة PostScript للطابعات.
• تنفيذ استدعاءات الدوال في مترجم.

تطبيقات الطابور

• مخازن البيانات
• نقل بيانات غير متزامن (ملف IO ، أنابيب ، مآخذ).
• طلبات التخصيص على مورد مشترك (طابعة ، معالج).
• تحليل حركة المرور.
• تحديد عدد من الصرافين لديك في سوبر ماركت.

استنتاج

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