TechCodeview

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

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

تحويل شارع إلى كثافة العمليات

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

إضافة عقدة إلى المكدس (عملية الدفع)

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

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

تعقيد الوقت : س(1)





التنفيذ ج :

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

حذف عقدة من المكدس (عملية POP)

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

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

تعقيد الوقت : o(n)

اجتياز أمر البريد

ج التنفيذ

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

عرض العقد (العبور)

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

1. انسخ مؤشر الرأس إلى مؤشر مؤقت.
2. حرك المؤشر المؤقت عبر كافة العقد في القائمة واطبع حقل القيمة المرفق بكل عقدة.

تعقيد الوقت : o(n)

ج التنفيذ

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

برنامج قائم على القائمة في لغة C ينفذ جميع عمليات المكدس باستخدام القائمة المرتبطة:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }