Koblet liste implementering av stack

I Stedet for å bruke array, kan vi også bruke koblet liste til å implementere stack. Koblet liste tildeler minnet dynamisk. Tidskompleksitet i begge scenariene er imidlertid det samme for alle operasjonene, dvs.

i koblet listeimplementering av stack opprettholdes nodene ikke-sammenhengende i minnet. Hver node inneholder en peker til sin umiddelbare etterfølger node i stakken. Stack sies å være overflown hvis plassen igjen i minnehopen ikke er nok til å opprette en node.

den øverste noden i stakken inneholder alltid null i adressefeltet. La oss diskutere måten hver operasjon utføres i koblet listeimplementering av stack.

Legge til en node i stakken (Push-operasjon)

Legge til en node i stakken kalles push-operasjon. Å skyve et element til en stabel i koblet listeimplementering er forskjellig fra en arrayimplementering. For å skyve et element på stakken, er følgende trinn involvert.

1. Opprett en node først og tilordne minne til den.
2. hvis listen er tom, skal elementet skyves som startnoden til listen. Dette inkluderer tildeling av verdi til datadelen av noden og tilordne null til adressedelen av noden.
3. hvis det allerede er noen noder i listen, må vi legge til det nye elementet i begynnelsen av listen (for ikke å bryte egenskapen til stakken). Til dette formål tilordner du adressen til startelementet til adressefeltet til den nye noden og gjør den nye noden, startnoden til listen.

Tidskompleksitet: o(1)



c implementering:

Slette en node fra stakken (POP operasjon)

Slette en node fra toppen av stakken er referert til som pop operasjon. Slette en node fra den koblede listeimplementeringen av stakken er forskjellig fra den i arrayimplementeringen. For å pope et element fra stakken må vi følge følgende trinn :

1. Se etter underflow-tilstanden: underflow-tilstanden oppstår når vi prøver å stikke fra en allerede tom stabel. Stakken vil være tom hvis hodet pekeren på listen peker til null.
2. Juster hodepekeren tilsvarende: i stakken poppes elementene bare fra den ene enden, derfor må verdien som er lagret i hodepekeren, slettes og noden må frigjøres. Den neste noden til hodeknuten blir nå hodeknuten.

Tidskompleksitet : o (n)

c implementering

Vise nodene (Traversering)

Vise alle nodene i en stabel må krysse alle nodene i den koblede listen organisert i form av stabel. For dette formålet må vi følge følgende trinn.

1. Kopier hodepekeren til en midlertidig peker.
2. Flytt den midlertidige pekeren gjennom alle nodene i listen, og skriv ut verdifeltet som er knyttet til hver node.

Tidskompleksitet : o (n)

C Implementering

Menydrevet program I C implementere alle stakkoperasjoner ved hjelp av koblet liste :