Уместо да користимо низ, можемо користити и повезану листу за имплементацију стека. Повезана листа динамички додељује меморију. Међутим, временска сложеност у оба сценарија је иста за све операције, тј. пусх, поп и пеек.

У имплементацији стека повезане листе, чворови се одржавају неконтинуирано у меморији. Сваки чвор садржи показивач на његов непосредни наследни чвор у стеку. Каже се да је стек пребачен ако простор који је остао у меморијској хрпи није довољан за креирање чвора.

Највиши чвор у стеку увек садржи нулл у свом адресном пољу. Хајде да разговарамо о начину на који се свака операција изводи у имплементацији стека повезане листе.

блокирај иоутубе огласе за андроид

Додавање чвора у стек (Пусх операција)

Додавање чвора стеку се назива гурати операција. Гурање елемента у стек у имплементацији повезане листе разликује се од имплементације низа. Да би се елемент гурнуо на стек, укључени су следећи кораци.

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

Брисање чвора из стека (ПОП операција)

Брисање чвора са врха стека се назива поп операција. Брисање чвора из имплементације стека повезане листе разликује се од оног у имплементацији низа. Да бисмо избацили елемент из стека, потребно је да следимо следеће кораке:

Проверите стање доњег тока:Услов нижег тока настаје када покушамо да искочимо из већ празног стека. Стек ће бити празан ако показивач главе листе показује на нулл.Подесите показивач главе у складу са тим:У стеку, елементи се искачу само са једног краја, стога, вредност сачувана у показивачу главе мора бити избрисана и чвор мора бити ослобођен. Следећи чвор главног чвора сада постаје главни чвор.

Временска сложеност: о(н)

Ц имплементација

 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. Померите привремени показивач кроз све чворове листе и одштампајте поље вредности прикачено за сваки чвор.

Временска сложеност: о(н)

Ц Имплементација

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

Програм вођен менијем у Ц-у који имплементира све операције стека користећи повезану листу:

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