A tömb használata helyett használhatunk linkelt listát is a verem megvalósításához. A csatolt lista dinamikusan foglalja le a memóriát. Az időbonyolultság azonban mindkét forgatókönyvben azonos minden műveletnél, azaz a push, pop és peek esetében.

A verem csatolt listás megvalósításában a csomópontok nem egybefüggően vannak karbantartva a memóriában. Minden csomópont tartalmaz egy mutatót a közvetlen utódcsomópontjára a veremben. A verem túlcsordul, ha a memóriakupacban maradt hely nem elegendő egy csomópont létrehozásához.

A verem legfelső csomópontjának címmezője mindig null értéket tartalmaz. Vizsgáljuk meg az egyes műveletek végrehajtásának módját a verem csatolt listás megvalósításában.

Csomópont hozzáadása a veremhez (push művelet)

Csomópont hozzáadását a veremhez úgy nevezzük nyom művelet. Egy elem verembe tolása a csatolt lista megvalósításában különbözik a tömb megvalósításától. Ahhoz, hogy egy elemet a veremre tolhasson, a következő lépéseket kell végrehajtania.

1. Először hozzon létre egy csomópontot, és foglaljon hozzá memóriát.
2. Ha a lista üres, akkor az elemet a lista kezdőcsomópontjaként kell tolni. Ez magában foglalja az érték hozzárendelését a csomópont adatrészéhez és a nullát a csomópont cím részéhez.
3. Ha már van néhány csomópont a listában, akkor az új elemet a lista elejére kell adnunk (hogy ne sértsük a verem tulajdonságait). Ehhez rendelje hozzá a kiinduló elem címét az új csomópont címmezőjéhez, és tegye az új csomópontot a lista kezdő csomópontjává.

Időbonyolultság: o(1)





C megvalósítás:

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

Csomópont törlése a veremből (POP művelet)

Egy csomópont törlését a verem tetejéről úgy nevezzük pop művelet. Egy csomópont törlése a verem csatolt lista megvalósításából eltér a tömb megvalósításától. Egy elem veremből való kiemeléséhez a következő lépéseket kell követnünk:

Ellenőrizze az alulfolyó állapotát:Az alulcsordulás feltétele akkor következik be, amikor egy már üres veremből próbálunk kilépni. A verem üres lesz, ha a lista fejmutatója nullra mutat.Állítsa be a fejmutatót ennek megfelelően:Veremben az elemek csak az egyik végéről kerülnek elő, ezért a fejmutatóban tárolt értéket törölni kell, és a csomópontot fel kell szabadítani. A fejcsomópont következő csomópontja mostantól a fejcsomópont lesz.

Időbonyolultság: o(n)

C megvalósítás

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

A csomópontok megjelenítése (bejárás)

A verem összes csomópontjának megjelenítéséhez be kell járni a csatolt lista összes csomópontját, verem formájában rendezve. Ebből a célból a következő lépéseket kell követnünk.

1. Másolja a fejmutatót egy ideiglenes mutatóba.
2. Mozgassa az ideiglenes mutatót a lista összes csomópontján, és nyomtassa ki minden csomóponthoz csatolt értékmezőt.

Időbonyolultság: o(n)

C Megvalósítás

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

Menüvezérelt program C nyelven, amely végrehajtja az összes veremműveletet a linkelt listával:

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