TechCodeview

Matriisin sijaan voimme käyttää myös linkitettyä listaa pinon toteuttamiseen. Linkitetty luettelo varaa muistin dynaamisesti. Kuitenkin aika monimutkaisuus molemmissa skenaarioissa on sama kaikille toiminnoille eli push, pop ja peek.

puu- ja graafiteoria

Pinon linkitetyssä listatoteutuksessa solmut säilyvät ei-vierekkäin muistissa. Jokainen solmu sisältää osoittimen sen välittömään seuraajasolmuun pinossa. Pinon sanotaan olevan ylivuoteltu, jos muistikasaan jätetty tila ei riitä solmun luomiseen.

Pinon ylimmän solmun osoitekentässä on aina nolla. Keskustellaan tavasta, jolla jokainen toiminto suoritetaan pinon linkitetyssä listatoteutuksessa.

Solmun lisääminen pinoon (push-toiminto)

Solmun lisäämistä pinoon kutsutaan nimellä työntää operaatio. Elementin työntäminen pinoon linkitetyssä luettelossa on eri asia kuin taulukkototeutuksessa. Elementin työntämiseksi pinoon tarvitaan seuraavat vaiheet.

1. Luo ensin solmu ja varaa sille muisti.
2. Jos lista on tyhjä, kohde tulee työntää listan aloitussolmuksi. Tämä sisältää arvon määrittämisen solmun dataosalle ja nolla-arvon määrittämisen solmun osoiteosalle.
3. Jos listassa on jo solmuja, meidän on lisättävä uusi elementti listan alkuun (jotta ei rikota pinon ominaisuuksia). Tätä tarkoitusta varten määritä uuden solmun osoitekenttään aloituselementin osoite ja tee uusi solmu listan aloitussolmuksi.

Aika monimutkaisuus: o(1)





C toteutus:

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

Solmun poistaminen pinosta (POP-toiminto)

Solmun poistamista pinon yläosasta kutsutaan nimellä pop operaatio. Solmun poistaminen pinon linkitetystä listasta on erilaista kuin taulukkototeutuksessa. Elementin nostamiseksi pinosta meidän on noudatettava seuraavia vaiheita:

kuinka poistaa ensimmäinen merkki excelissä

Tarkista alivuototilanne:Alivuototila ilmenee, kun yritämme ponnahtaa jo tyhjästä pinosta. Pino on tyhjä, jos luettelon pääosoitin osoittaa nulla.Säädä pään osoitin vastaavasti:Pinossa elementit pompataan vain yhdestä päästä, joten pääosoittimeen tallennettu arvo on poistettava ja solmu vapautettava. Pääsolmun seuraavasta solmusta tulee nyt pääsolmu.

Aika monimutkaisuus: o(n)

C-toteutus

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

Näytä solmut (kulkeminen)

Pinon kaikkien solmujen näyttäminen edellyttää pinon muodossa järjestetyn linkitetyn luettelon kaikkien solmujen läpikulkua. Tätä tarkoitusta varten meidän on noudatettava seuraavia vaiheita.

1. Kopioi pääosoitin väliaikaiseksi osoittimeksi.
2. Siirrä väliaikainen osoitin luettelon kaikkien solmujen läpi ja tulosta jokaiseen solmuun liitetty arvokenttä.

Aika monimutkaisuus: o(n)

C Toteutus

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

Valikkoohjattu ohjelma C:ssä, joka toteuttaa kaikki pinotoiminnot linkitetyn listan avulla:

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