Linked list implementering af stack

i stedet for at bruge array kan vi også bruge linked list til at implementere stack. Sammenkædet liste tildeler hukommelsen dynamisk. Imidlertid er tidskompleksiteten i begge scenarier den samme for alle operationer, dvs.push, pop og peek.

i linket listeimplementering af stack opretholdes noderne ikke-sammenhængende i hukommelsen. Hver node indeholder en markør til dens umiddelbare efterfølgende node i stakken. Stak siges at være overfyldt, hvis den plads, der er tilbage i hukommelseshaugen, ikke er nok til at oprette en node.

den øverste mest node i stakken indeholder altid null i sit adressefelt. Lad os diskutere den måde, hvorpå, hver operation udføres i sammenkædet liste implementering af stack.

tilføjelse af en node til stakken (Push operation)

tilføjelse af en node til stakken kaldes push operation. Skubbe et element til en stak i linked List implementering er forskellig fra en array implementering. For at skubbe et element på stakken er følgende trin involveret.

1. Opret en node først og allokere hukommelse til det.
2. hvis listen er tom, skal elementet skubbes som startknudepunkt på listen. Dette omfatter tildeling af værdi til datadelen af noden og tildele null til adressedelen af noden.
3. hvis der allerede er nogle noder på listen, skal vi tilføje det nye element i begyndelsen af listen (for ikke at krænke stakens egenskab). Til dette formål skal du tildele adressen til startelementet til adressefeltet for den nye node og oprette den nye node, startknudepunktet på listen.

tidskompleksitet: o(1)



C implementering:

sletning af en node fra stakken (POP-operation)

sletning af en node fra toppen af stakken kaldes pop-operation. Sletning af en node fra Den sammenkædede listeimplementering af stack er forskellig fra den i array-implementeringen. For at poppe et element fra stakken skal vi følge følgende trin :

1. kontroller for understrømningstilstanden: understrømningstilstanden opstår, når vi prøver at poppe fra en allerede tom stak. Stakken vil være tom, hvis hovedmarkøren på listen peger på null.
2. Juster hovedpegeren i overensstemmelse hermed: i stakken poppes elementerne kun fra den ene ende, derfor skal værdien, der er gemt i hovedpegeren, slettes, og noden skal frigøres. Den næste knude i hovednoden bliver nu hovednoden.

Tidskompleksitet : o (n)

C implementering

Vis knudepunkterne (gennemkører)

visning af alle knudepunkter i en stak skal gennemkøres alle knudepunkter i den linkede liste organiseret i form af stak. Til dette formål skal vi følge følgende trin.

1. Kopier hovedmarkøren til en midlertidig markør.
2. Flyt den midlertidige markør gennem alle knudepunkter på listen, og udskriv det værdifelt, der er knyttet til hver node.

Tidskompleksitet : o (n)

C implementering

Menu drevet program i C implementering af alle stakoperationer ved hjælp af linket liste :