használata helyett tömb, mi is használható linked list végrehajtására stack. A csatolt lista dinamikusan lefoglalja a memóriát. Az idő bonyolultsága azonban mindkét forgatókönyvben azonos az összes műveletnél, azaz a push, a pop és a peek esetében.
a stack linked list implementációjában a csomópontok nem összefüggő állapotban vannak a memóriában. Minden csomópont tartalmaz egy mutatót a verem közvetlen utódcsomópontjára. Azt mondják, hogy a verem túlterhelt, ha a memória halomban maradt hely nem elegendő egy csomópont létrehozásához.
a verem legfelső csomópontja mindig null-t tartalmaz a címmezőjében. Lehetővé teszi, hogy megvitassák, hogy milyen módon, minden művelet végrehajtásra láncolt lista végrehajtása verem.
Csomópont hozzáadása a veremhez (Push művelet)
Csomópont hozzáadása a veremhez push műveletnek nevezzük. Nyomja egy elemet egy verem csatolt lista végrehajtása eltér a tömb végrehajtását. Annak érdekében, hogy egy elemet a veremre nyomjon, a következő lépéseket kell végrehajtani.
- először hozzon létre egy csomópontot, és foglaljon hozzá memóriát.
- ha a lista üres, akkor az elemet a lista kezdő csomópontjaként kell nyomni. Ez magában foglalja az érték hozzárendelését a csomópont adatrészéhez, A null hozzárendelését a csomópont címrészéhez.
- ha már van néhány csomópont a listában, akkor hozzá kell adnunk az új elemet a lista elejére (hogy ne sértsük meg a verem tulajdonságát). Ehhez rendelje hozzá a kezdő elem címét az új csomópont címmezőjéhez, és készítse el az új csomópontot, a lista kezdő csomópontját.
- ellenőrizze a underflow feltétel: az underflow feltétel akkor fordul elő, amikor megpróbálunk pop egy már üres verem. A verem üres lesz, ha a lista fejmutatója null-ra mutat.
- ennek megfelelően állítsa be a fejmutatót: a veremben az elemek csak az egyik végéről pattannak be, ezért a fejmutatóban tárolt értéket törölni kell, és a csomópontot ki kell szabadítani. A fejcsomó következő csomópontja most a fejcsomópont lesz.
- másolja a fejmutatót egy ideiglenes mutatóba.
- mozgassa az ideiglenes mutatót a lista összes csomópontján, és nyomtassa ki az összes csomóponthoz csatolt értékmezőt.
idő komplexitás: o(1)
C megvalósítás :
csomópont törlése a veremből (POP művelet)
csomópont törlése a verem tetejéről pop műveletnek nevezzük. A csomópont törlése a stack csatolt listájának megvalósításából eltér a tömb megvalósításától. Annak érdekében, hogy pop egy elemet a verem, meg kell, hogy kövesse az alábbi lépéseket :
Idő Összetettsége : o (n)
C megvalósítás
a csomópontok megjelenítése (áthaladás)
a verem összes csomópontjának megjelenítése a verem formájában szervezett Linkelt lista összes csomópontját át kell haladnia. Ebből a célból a következő lépéseket kell követnünk.
Idő Összetettsége : o (n)