logo

Saistītā saraksta steka ieviešana

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.


DS saistītā saraksta ieviešanas steks

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
  1. Vispirms izveidojiet mezglu un piešķiriet tam atmiņu.
  2. 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.
  3. 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.
  4. Laika sarežģītība: o(1)

    gimp kā noņemt atlasi

    DS saistītā saraksta ieviešanas steks

    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 :

      Pārbaudiet zemplūsmas stāvokli:Nepietiekamas plūsmas stāvoklis rodas, kad mēs cenšamies izkļūt no jau tukšas kaudzes. Kaudze būs tukša, ja saraksta sākuma rādītājs norāda uz nulli.Attiecīgi noregulējiet galvas rādītāju:Stackā elementi tiek izspiesti tikai no viena gala, tāpēc ir jādzēš galvas rādītājā saglabātā vērtība un jāatbrīvo mezgls. Nākamais galvenā mezgla mezgls tagad kļūst par galveno mezglu.

    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.

    1. Kopējiet galvas rādītāju pagaidu rādītājā.
    2. 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(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; } } }