المكدس وقائمة الانتظار – Stack & Queue

-

المكدس (stack): هو نوع من أنواع البيانات المجردة ((ADT Abstract Data Type)، وهو عبارة عن بنية بيانات خطية linear data structure تتبع ترتيبًا معينًا يتم تنفيذ العمليات عليها. وتنفيذ العمليات قد يكون LIFO (Last In First Out) or FILO (First In Last Out). هذا النوع شائع الاستخدام في معظم لغات البرمجة. وسبب تسميته بالمكدس stack هو: انه يتصرف مثل مكدس في العالم الحقيقي، من الأمثلة في العالم الحقيقي: مجموعة أوراق أو كومة من اللوحات... إلخ.

يمكن اجراء العمليات على stack باكثر من طريقة سواء FILO او LIFO. 

في حال تم استخدام LIFO: هذا يعني ان العنصر الذي تم وضعه او ادراجه أخيرًا، يتم الوصول إليه أولاً.

في مصطلحات المكدس stack terminology، تسمى عملية الإدراج عملية PUSH وتسمى عملية الحذف عملية POP.

تمثيل المكدس Stack Representation

الصورة التالية توضح كيفية الإضافة والحذف من المكدس 

لاحظ من الصورة تم إضافة العنصر رقم 1 الى stack فارغ. ثم اضفنا عنصر رقم 2. وعند الحذف تم الحذف من اخر عنصر تم أضافته وهو 2. 

يوجد اكثر من طريقة لتمثيل stack مثل:

• Array
• Structure
• Pointer
• Linked List

واكيد يمكن ان يكون حجم stack ثابت او متغير (ديناميكي). 

نستخدم في هذا الدرس المصفوفات لتمثيل stack لذا سيكون التعامل مع حجم ثابت. 

العمليات على stack 

مثل ما حكينا يمكن اجراء مجموعة من العمليات على stack مثل: 

• ()push : إضافة (تخزين) عنصر element الى stack
• ()pop : حذف عنصر من stack. 
• ()isFull: تستخدم لتحقق من حالة stack إذا كان ممتلئًا full.
• ()isEmpty: تستخدم لتحقق من حالة stack إذا كان فارغ empty.
• ()peek: تستخدم للحصل على عنصر البيانات العلوي top data element لstack ، دون حذفه.

لتنفيذ هذه العمليات على stack. نحتاج الى مؤشر pointer. بحيث يكون دائما يشير الى اخر عملية تم اضفتها last Push data الى Stack.  بحيث يشير هذا المؤشر دائما الى الجزء العلوي من stack. وبالتالي يمكن الوصول الى اخر عنصر element في stack من خلال هذا المؤشر. 

يطلق على هذا المؤشر Top Pointer . ووجود هذا المؤشر ضروري جدا عن التعامل مع stack . 

تمام التمام. 

نفهم العمليات السابقة بالتفصيل. 

عملية isFull

حكينا يستخدم هذا function لتحقق من حالة stack إذا كان ممتلئًا full.

الخوارزمية لهذه العملية تكتب:

procedure CheckStackIsfull
begin 
   get maxsize of stack
   if top equals to MAXSIZE
      return true
   else
      return false
   endif
  end 

لتمثيل هذه الخوارزمية في لغة C نستخدم الكود:

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

عملية peek

حكينا تستخدم هذه العملية للحصل على عنصر البيانات العلوي top data element لstack ، دون حذفه.

الخوارزمية 

procedure peek
begin
   return stack[top]
end procedure

لتمثيل هذه الخوارزمية في لغة C نستخدم الكود:

int peek() {
   return stack[top];
}

عملية isEmpty

تستخدم لتحقق من حالة stack إذا كان فارغ empty.

الخوارزمية:

procedure isempty
begin
   if top less than 1
      return true
   else
      return false
   endif 
end procedure

لاحظ انه تم كتابة سطر الكود التالي في اول الخوارزمية:

   if top less than 1

السبب في ذلك هو ان المصفوفات تبدا من index رقم صفر . وهذا يعني انه في حال وجود عنصر element في هذا index الذي يساوي صفر فان stack غير فارغ. بناء علية عند التحقق من هذه العملية يجب التأكد من ان المؤشر pointer المسمى top يشير الى index اقل من صفر.

كود C 

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

عملية push 

تستخدم هذه العمية لإضافة (تخزين) عنصر element الى stack.

لتنفيذ هذه العملية نحتاج الى مجموعة من الخطوات: 

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

خوارزمية عملية الإضافة:

begin procedure push: stack, data
   if stack is full
      return null
   endif
   top ← top + 1
   stack[top] ← data
end procedure

الكود الخاص بلغة C 

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

عملية الحذف Pop 

يتم في هذه العملية حذف element من stack.

عند التعامل مع المصفوفات array لا تتم إزالة element فعليًا، بدلاً من ذلك يتم إنقاص المؤشر top إلى موضع أقل في stack للإشارة إلى القيمة السابقة. ولكن عند التعامل مع linked-list يتم في عملية pop إزالة element وإلغاء تخصيص de allocates مساحة الذاكرة بشكل نهائي.

عملية الحذف الخطوات التالية:

• التحقق مما إذا كان stack فارغ Empty.
• في حال كان stack فارغ، لن يتم التنفيذ ويتم ارجاع خطأ.  
• إذا لم يكن stack فارغ، سيتم تحريك المؤشر top الى اعلى للوصول الى element المطلوب حذفه.
• إنقاص قيمة المؤشر top بمقدار 1، بحيث يصبح المؤشر top يشير الى العنصر السابق.
• تمت عملية الحذف بنجاح.

خوارزمية الحذف :

begin procedure pop: stack
   if stack is empty
      return null
   endif
   data ← stack[top]
   top ← top - 1
   return data
end procedure

كود لغة C 

int pop(int data) {
   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

مثال كامل لهذه العمليات 

اضف الكود التالي لمف notepad ثم احفظ الملف باسم مناسب (StackOperations.c)

#include<stdio.h>
#include<stdlib.h>
#define Size 4 
int Top=-1, inp_array[Size];
void Push();
void Pop();
void show();
int main()
{
	int choice;
	while(1)	
	{
		printf("\nOperations performed by Stack");
		printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
		printf("\n\nEnter the choice:");
		scanf("%d",&choice);
		
		switch(choice)
		{
			case 1: Push();
					break;
			case 2: Pop();
					break;
			case 3: show();
					break;
			case 4: exit(0);
			
			default: printf("\nInvalid choice!!");
		}
	}
}
 
void Push()
{
	int x;
	
	if(Top==Size-1)
	{
		printf("\nOverflow!!");
	}
	else
	{
		printf("\nEnter element to be inserted to the stack:");
		scanf("%d",&x);
		Top=Top+1;
		inp_array[Top]=x;
	}
}
 
void Pop()
{
	if(Top==-1)
	{
		printf("\nUnderflow!!");
	}
	else
	{
		printf("\nPopped element:  %d",inp_array[Top]);
		Top=Top-1;
	}
}
 
void show()
{
	if(Top==-1)
	{
		printf("\nUnderflow!!");
	}
	else
	{
		printf("\nElements present in the stack: \n");
		for(int i=Top;i>=0;--i)
			printf("%d\n",inp_array[i]);
	}
}

انتقل الى command prompt بكتابة الامر cmd في المسار الخاص بمكان تخزين الملف السابق . 

ثم اكتب الامر التالي داخل command prompt  : 

gcc StackOperations.c

اذا لم يوجد أي مشكلة سيتم تنفيذ الكود وسيتم إضافة ملف جديد باسم a 

من داخل command prompt اكتب اسم البرنامج الناتج