TechCodeview

Užuot naudoję masyvą, taip pat galime naudoti susietą sąrašą, kad įdiegtume steką. Susietas sąrašas dinamiškai paskirsto atmintį. Tačiau laiko sudėtingumas abiejuose scenarijuose yra vienodas visoms operacijoms, ty stumti, pop ir žvilgtelėti.

Įdiegus dėklo susietą sąrašą, mazgai atmintyje išlaikomi negretimi. Kiekviename mazge yra žymeklis į jo tiesioginį įpėdinį krūvoje. Sakoma, kad stakas perpildytas, jei atminties krūvoje likusios vietos neužtenka mazgui sukurti.

Viršutiniame krūvos mazge adreso lauke visada yra nulis. Leiskite aptarti, kaip kiekviena operacija atliekama naudojant susieto sąrašo diegimą.

Mazgo pridėjimas prie krūvos (stumimo operacija)

Mazgo įtraukimas į krūvą vadinamas stumti operacija. Elemento perkėlimas į krūvą susieto sąrašo diegime skiriasi nuo masyvo diegimo. Norint įstumti elementą į krūvą, reikia atlikti šiuos veiksmus.

daryti kol java

1. Pirmiausia sukurkite mazgą ir paskirkite jam atmintį.
2. Jei sąrašas tuščias, elementas turi būti stumiamas kaip sąrašo pradžios mazgas. Tai apima vertės priskyrimą mazgo duomenų daliai ir nulio priskyrimą mazgo adreso daliai.
3. Jei sąraše jau yra keletas mazgų, turime įtraukti naują elementą sąrašo pradžioje (kad nepažeistume krūvos savybių). Šiuo tikslu naujo mazgo adreso laukui priskirkite pradinio elemento adresą ir padarykite naują mazgą sąrašo pradiniu mazgu.

Laiko sudėtingumas: o(1)





C įgyvendinimas:

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

Mazgo ištrynimas iš kamino (POP operacija)

Mazgo ištrynimas iš krūvos viršaus vadinamas pop operacija. Mazgo ištrynimas iš susieto sąrašo diegimo kamino skiriasi nuo masyvo diegimo. Norėdami iškelti elementą iš kamino, turime atlikti šiuos veiksmus:

Patikrinkite perpildymo būklę:Nepakankamo srauto sąlyga atsiranda, kai bandome iššokti iš jau tuščio krūvos. Krūvas bus tuščias, jei sąrašo antraštė nukreipia į nulį.Atitinkamai sureguliuokite galvos žymeklį:Stacke elementai iššokami tik iš vieno galo, todėl antraštės rodyklėje saugoma reikšmė turi būti ištrinta ir mazgas turi būti atlaisvintas. Kitas pagrindinio mazgo mazgas dabar tampa pagrindiniu mazgu.

Laiko sudėtingumas: o(n)

C įgyvendinimas

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

Rodyti mazgus (važinėjimas)

Norint rodyti visus krūvos mazgus, reikia pereiti visus susieto sąrašo mazgus, sutvarkytus dėklo forma. Šiuo tikslu turime atlikti šiuos veiksmus.

1. Nukopijuokite galvos žymeklį į laikiną žymeklį.
2. Perkelkite laikiną žymeklį per visus sąrašo mazgus ir atspausdinkite vertės lauką, pridėtą prie kiekvieno mazgo.

Laiko sudėtingumas: o(n)

C Įgyvendinimas

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

Meniu valdoma programa C, įgyvendinanti visas kamino operacijas naudojant susietą sąrašą:

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