Mnohokrát je zásobník implementovaný ako prepojenýzoznam, Je pole reprezentácia nie je dosť dobrý, v poli môžeme vykonať push pop ľahko, a prepojený zoznam cez pole komplikuje kód, a nemá žiadnu výhodu oproti implementácii poľa.
Môžete uviesť akýkoľvek príklad, kde implementácia prepojeného zoznamu je výhodnejšia, alebo bez neho nemôžeme urobiť.
odpovede:
2 pre odpoveď č. 1Povedal by som, že mnoho praktických implementácií komínov sú zapísané pomocou polí. Napríklad implementácia .NET Stack používa pole ako záložný ukladací priestor.
Polia sú zvyčajne efektívnejšie, pretože môžete ponechať uzly zásobníka v blízkosti v súvislej pamäti, ktorá sa pekne zmestí do rýchlych riadkov vyrovnávacej pamäte procesora.
Predstavujem si, že vidíte implementáciu učebniceZásobníky, ktoré používajú prepojené zoznamy, pretože "ľahšie písať a don" t vás núti písať trochu extra kód pre správu backing pole obchod, rovnako ako prísť s rastom / kopírovanie / rezervný priestor heuristický.
Okrem toho, ak ste naozaj stlačení na použitiemalá pamäť, implementácia prepojeného zoznamu by mohla dávať zmysel, pretože si "odpad" priestor, ktorý nie je v súčasnosti používaný. Avšak na moderných procesoroch s veľkým množstvom pamäte je zvyčajne lepšie použiť polia na získanie výhod cache, ktoré ponúkajú, namiesto toho, aby sa starali o chyby stránok pomocou prístupu prepojeného zoznamu.
1 pre odpoveď č. 2
Veľkosť poľa je obmedzená a preddefinovaná. Keď neviete, koľko z nich je tam potom prepojený zoznam je ideálnou voľbou.
Viac Vypracované porovnanie: - (+ pre dominantný prepojený zoznam a - pre pole)
Size and type constraint:-
(+) Ďalšie členy poľa sú zarovnané na rovnakej úrovnivzdialenosť a potrebujú súvislú pamäť, zatiaľ čo na druhej strane zoznam odkazov môže poskytnúť neprerušované riešenie pamäte, takže niekedy to je dobré pre pamäť, rovnako ako v prípade veľkých dát (vyhýba sa cpu polling pre zdroje).
(+) Predpokladajme, že v prípade, že používate pole ako zásobník, a pole je typu int.Now, ako budete ubytovať double v ňom?
Portability
- (+) Array môže spôsobiť výnimky ako index mimo viazaných výnimiek, ale reťaz môžete kedykoľvek zvýšiť v prepojenom zozname.
Speed and performance
- (-) Ak je jeho výkon, potom zrejme najviacZložitosť spadá okolo O (1) pre polia. V prípade prepojeného zoznamu budete musieť vybrať štartovací uzol, aby sa začalo sledovanie a to zvyšuje výkonnostný trest.
0 pre odpoveď č. 3
Keď sa veľkosť zásobníka môže značne líšiť, stratíte priestor, ak máte zovšeobecnené postupy, ktoré vždy prideľujú obrovské pole.
0 pre odpoveď č. 4
Je zrejmé, že pole s pevnou veľkosťou má obmedzenú znalosť maximálnej veľkosti pred rukou.
Ak uvažujete dynamic array potom Prepojený zoznam vs. polia zahŕňa podrobnosti vrátane zložitosti vykonávania operácií.
0 pre odpoveď č. 5
Stack je implementovaný pomocou Link List, pretože operácie Push a Pop sú O (1) časovej zložitosti v porovnaní s O (n) pre polia. (okrem výhody flexibilnej veľkosti v zozname odkazov)