במקום להשתמש במערך, אנו יכולים גם להשתמש ברשימה מקושרת כדי ליישם מחסנית. רשימה מקושרת מקצה את הזיכרון באופן דינמי. עם זאת, מורכבות הזמן בשני התרחישים זהה עבור כל הפעולות, כלומר דחיפה, פופ והצצה.

השוואת מחרוזות java

ביישום רשימה מקושרת של מחסנית, הצמתים נשמרים באופן לא רציף בזיכרון. כל צומת מכיל מצביע לצומת היורש המיידי שלו בערימה. אומרים שהמחסום מוצף אם השטח שנותר בערימת הזיכרון אינו מספיק כדי ליצור צומת.

הצומת העליון ביותר בערימה תמיד מכיל null בשדה הכתובת שלו. הבה נדון בדרך שבה כל פעולה מבוצעת ביישום רשימה מקושרת של מחסנית.

הוספת צומת לערימה (פעולת דחיפה)

הוספת צומת לערימה נקראת לִדחוֹף מבצע. דחיפת אלמנט למחסנית ביישום רשימה מקושרת שונה מזו של יישום מערך. על מנת לדחוף אלמנט לערימה, השלבים הבאים מעורבים.

1. תחילה צור צומת והקצה לו זיכרון.
2. אם הרשימה ריקה, יש לדחוף את הפריט כצומת ההתחלה של הרשימה. זה כולל הקצאת ערך לחלק הנתונים של הצומת והקצאת null לחלק הכתובת של הצומת.
3. אם כבר יש כמה צמתים ברשימה, אז עלינו להוסיף את האלמנט החדש בתחילת הרשימה (כדי לא להפר את המאפיין של המחסנית). לשם כך, הקצה את הכתובת של אלמנט ההתחלה לשדה הכתובת של הצומת החדש והפוך את הצומת החדש לצומת ההתחלה של הרשימה.

מורכבות זמן: o(1)





יישום C:

 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)

מחיקת צומת מהחלק העליון של המחסנית נקראת פּוֹפּ מבצע. מחיקת צומת מיישום הרשימה המקושרת של מחסנית שונה מזו שבהטמעת המערך. על מנת להוציא אלמנט מהמחסנית, עלינו לבצע את השלבים הבאים:

בדוק את מצב הזרימה:מצב ה-underflow מתרחש כאשר אנו מנסים לקפוץ מחסנית שכבר ריקה. הערימה תהיה ריקה אם מצביע הראש של הרשימה יצביע על null.כוונן את מצביע הראש בהתאם:ב-Stack, האלמנטים מוקפצים רק מקצה אחד, לכן יש למחוק את הערך המאוחסן במצביע הראש ולשחרר את הצומת. הצומת הבא של צומת הראש הופך כעת לצומת הראש.

מורכבות זמן: o(n)

יישום C

 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; } } }