länkad lista implementering av stack

istället för att använda array kan vi också använda länkad lista för att implementera stack. Länkad lista allokerar minnet dynamiskt. Tidskomplexiteten i båda scenariot är dock densamma för alla operationer, dvs push, pop och peek.

i länkad lista implementering av stack, noderna bibehålls icke-sammanhängande i minnet. Varje nod innehåller en pekare till sin omedelbara efterföljande nod i stapeln. Stack sägs vara överflödad om utrymmet kvar i minneshögen inte räcker för att skapa en nod.

den översta noden i stacken innehåller alltid null i adressfältet. Låt oss diskutera hur varje operation utförs i länkad lista implementering av stack.

lägga till en nod i stacken (Push operation)

lägga till en nod i stacken kallas push operation. Att trycka ett element till en stapel i länkad listimplementering skiljer sig från en arrayimplementering. För att driva ett element på stapeln är följande steg involverade.

1. skapa en nod först och tilldela minne till den.
2. om listan är tom ska objektet tryckas som startnod för listan. Detta inkluderar att tilldela värde till Datadelen av noden och tilldela null till adressdelen av noden.
3. om det redan finns några noder i listan måste vi lägga till det nya elementet i början av listan (för att inte bryta mot Stackens egendom). För detta ändamål tilldelar du adressen till startelementet till adressfältet för den nya noden och gör den nya noden, listans startnod.

tidskomplexitet: o(1)



C genomförande :

ta bort en nod från stacken (POP operation)

ta bort en nod från toppen av stacken kallas pop operation. Att ta bort en nod från den länkade listimplementeringen av stack skiljer sig från den i arrayimplementeringen. För att poppa ett element från stapeln måste vi följa följande steg :

1. kontrollera om underflödesförhållandet: underflödesförhållandet uppstår när vi försöker poppa från en redan tom stack. Stacken blir tom om listans huvudpekare pekar på null.
2. justera huvudpekaren i enlighet därmed: i stacken poppas elementen bara från ena änden, därför måste värdet som lagras i huvudpekaren raderas och noden måste frigöras. Nästa nod i huvudnoden blir nu huvudnoden.

Tidskomplexitet : o (n)

C implementering

Visa noderna (Traversing)

Visa alla noder i en stack behöver korsa alla noder i den länkade listan organiserad i form av stack. För detta ändamål måste vi följa följande steg.

1. kopiera huvudpekaren till en tillfällig pekare.
2. flytta den tillfälliga pekaren genom alla noder i listan och skriv ut värdefältet som är kopplat till varje nod.

Tidskomplexitet : o (n)

C implementering

menydrivet program i C implementering av alla stackoperationer med länkad lista :