Вместо да използваме масив, можем също да използваме свързан списък за внедряване на стек. Свързаният списък разпределя паметта динамично. Времевата сложност и в двата сценария обаче е еднаква за всички операции, т.е. натискане, изскачане и надникване.

При внедряването на стека в свързан списък възлите се поддържат несвързани в паметта. Всеки възел съдържа указател към неговия непосредствен наследник възел в стека. Казва се, че стекът е препълнен, ако останалото място в паметта не е достатъчно за създаване на възел.

Най-горният възел в стека винаги съдържа null в полето за адрес. Нека обсъдим начина, по който всяка операция се изпълнява в реализация на свързан списък на стека.

Добавяне на възел към стека (операция Push)

Добавянето на възел към стека се нарича тласък операция. Избутването на елемент към стека при внедряване на свързан списък е различно от това при изпълнение на масив. За да поставите елемент в стека, са включени следните стъпки.

1. Първо създайте възел и разпределете памет към него.
2. Ако списъкът е празен, тогава елементът трябва да бъде избутан като начален възел на списъка. Това включва присвояване на стойност на частта с данни на възела и присвояване на нула на адресната част на възела.
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 възниква, когато се опитаме да изскочим от вече празен стек. Стекът ще бъде празен, ако началният показалец на списъка сочи към нула.Регулирайте съответно показалеца на главата:В стека елементите се изваждат само от единия край, следователно стойността, съхранена в указателя на главата, трябва да бъде изтрита и възелът трябва да бъде освободен. Следващият възел на главния възел сега става главен възел.

Времева сложност: 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)

C Изпълнение

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