Tā vietā, lai izmantotu masīvu, mēs varam izmantot arī saistīto sarakstu, lai ieviestu steku. Saistītais saraksts dinamiski piešķir atmiņu. Tomēr laika sarežģītība abos scenārijos ir vienāda visām darbībām, t.i., push, pop un peek.
Saistītā saraksta steka ieviešanā mezgli atmiņā tiek uzturēti nepārtraukti. Katrs mezgls satur norādi uz tā tiešo pēcteci stekā. Tiek uzskatīts, ka kaudze ir pārpildīta, ja atmiņas kaudzē nepietiek vietas, lai izveidotu mezglu.
Augšējais mezgls stekā vienmēr satur nulli savā adreses laukā. Ļauj apspriest veidu, kādā katra darbība tiek veikta steka saistīto sarakstu ieviešanā.
Mezgla pievienošana skurstei (spiešanas darbība)
Mezgla pievienošana stekam tiek apzīmēta kā spiediet darbība. Elementa nosūtīšana uz steku saistītā saraksta īstenošanā atšķiras no masīva ieviešanas. Lai uzspiestu elementu uz kaudzes, ir jāveic šādas darbības.
math.random java
- Vispirms izveidojiet mezglu un piešķiriet tam atmiņu.
- Ja saraksts ir tukšs, vienums ir jānospiež kā saraksta sākuma mezgls. Tas ietver vērtības piešķiršanu mezgla datu daļai un nulles piešķiršanu mezgla adreses daļai.
- Ja sarakstā jau ir daži mezgli, tad jaunais elements ir jāpievieno saraksta sākumā (lai nepārkāptu steka īpašību). Šim nolūkam jaunā mezgla adreses laukam piešķiriet sākuma elementa adresi un izveidojiet jauno mezglu par saraksta sākuma mezglu.
- Kopējiet galvas rādītāju pagaidu rādītājā.
- Pārvietojiet pagaidu rādītāju pa visiem saraksta mezgliem un izdrukājiet katram mezglam pievienoto vērtību lauku.
Laika sarežģītība: o(1)
gimp kā noņemt atlasi
C ieviešana:
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'); } }
Mezgla dzēšana no steka (POP darbība)
Mezgla dzēšana no steka augšdaļas tiek apzīmēta kā pop darbība. Mezgla dzēšana no steka saistītā saraksta ieviešanas atšķiras no masīva ieviešanas. Lai izceltu elementu no steka, mums ir jāveic šādas darbības :
Laika sarežģītība: o(n)
C ieviešana
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'); } }
Parādīt mezglus (pārvietošanās)
Lai parādītu visus steka mezglus, ir jāšķērso visi saistītā saraksta mezgli, kas sakārtoti steka formā. Šim nolūkam mums ir jāveic šādas darbības.
Laika sarežģītība: o(n)
C Īstenošana
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; } } }
Izvēlnes vadīta programma C valodā, kas īsteno visas steka darbības, izmantojot saistīto sarakstu:
#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; } } }