Kaupas (stakas) — LIFO duomenų struktūra: apibrėžimas ir pavyzdys

Sužinokite, kas yra kaupas (stakas) — LIFO duomenų struktūra: aiškus apibrėžimas, paprastas pavyzdys ir praktinės operacijos (push/pop) supratimas.

Kaupas yra viena svarbiausių duomenų struktūrų informatikoje. Kad suprastumėte, kaip veikia stekas, įsivaizduokite atverstų žaidimo kortų kaladę: galime lengvai pasiekti tik viršuje esančią kortą. Kai norime pažvelgti į viršutinę kortą, galime daryti du dalykus: galime į ją žvilgtelėti, bet palikti ją ant krūvelės, arba galime ją nuimti. Kai „iššokame“ nuo viršutinio objekto, jį nuimame nuo krūvos. Jei norime pridėti kitą kortelę prie krūvos viršaus, ją pastumiame.

Kaupas vadinamas paskutinio įėjimo — pirmojo išėjimo (LIFO) kolekcija. Tai reiškia, kad paskutinis pridėtas (pastumtas) daiktas yra pirmasis, kuris ištraukiamas (iššokantis). Pavyzdžiui, jei paskutinė kortelė, kurią įdėjome į kortų krūvą, buvo tūzas, tai pirmoji kortelė, kurią ištrauksime iš viršaus, bus tas tūzas.

Pagrindinės operacijos

• push(x) — pridėti elementą x ant kaupto viršaus.
• pop() — pašalinti ir grąžinti viršutinį elementą; klaida arba speciali reikšmė, jei kaupas tuščias.
• peek() arba top() — grąžinti viršutinį elementą be jo pašalinimo.
• isEmpty() — patikrinti, ar kaupas tuščias.
• size() — (nebūtina) sužinoti elementų skaičių kaupe.

Trumpas pseudokodas

 push(x):     add x to top  pop():     if isEmpty() then error     remove and return top element  peek():     if isEmpty() then error     return top element without removing 

Įgyvendinimas

Kaupas galima įgyvendinti keliais būdais. Du dažniausi:

• Masyvas (array) — paprasta ir greita implementacija, kai kaupo dydis iš anksto žinomas arba leidžiama išplėsti masyvą (dinaminis masyvas). Privalumai: greitas atsitiktinis prieėjimas prie paskutinio elemento, mažas kaštas vietos tvarkymui. Trūkumai: statiniu masyvu apribotas dydis; dinaminis plečiasi, bet gali reikalauti kopijavimo.
• Sąrašas (linked list) — vienmatis arba dvigubas sąrašas, kur elementai leidžiami pridėti/pašalinti priekinėje galvoje. Privalumai: paprasta operacijų implementacija be išankstinio dydžio ribos. Trūkumai: didesnės atminties sąnaudos dėl nuorodų ir mažesnis kaštas prieigos prie kitų elementų.

Panaudojimo pavyzdžiai

• Skambinimų stekas programose (call stack) — saugo funkcijų iškvietimus, vietines reikšmes ir grįžimo adresus.
• Undo/redo mechanizmai teksto redaktoriuose — kiekvienas veiksmas dedamas ant steko, atšaukiant imamasi paskutinio veiksmo.
• Sąrašo ar išraiškos analizė — įvertinant arba konvertuojant infiksines išraiškas į postfiksines (RPN) naudojamas stekas operatoriams ir operandams.
• Giluminis pirmasis paieškos algoritmas (DFS) grafuose — naudojamas tiek rekursinei, tiek iteracinei versijai (iteracinė naudoja steką).
• Backtracking problemos (pvz., keliavimo pardavėjo, sudoku sprendimas) — kelio žymėjimui ir grįžimams laikyti.

Laiko ir atminties sudėtingumas

• push — O(1) (amortizuotai O(1) dinaminio masyvo plečiamose implementacijose)
• pop — O(1)
• peek/top — O(1)
• Atminties naudojimas — O(n), kur n yra elementų skaičius kaupe

Pastabos ir variantai

• Yra ribotas (bounded) kaupas, kurio dydis fiksuotas, ir neribotas (unbounded) kaupas, kuris plečiamas dinamiškai.
• Konkurentinės (multi-threaded) programose naudojami sudėtingesni, srauto saugūs (thread-safe) arba be blokavimo (lock-free) stekai.
• Kaupo sąvoka sutampa su terminais stakas arba stakas (stack) — lietuviškai dažnai vartojamas žodis „kaupas“ arba „stakas“.

Apibendrinant, kaupas (LIFO) yra paprasta, bet labai universali duomenų struktūra, plačiai naudojama tiek žemo lygio programavimo mechanizmams (funkcijų iškvietimų valdymui), tiek aukštesnio lygio algoritmams (analizė, backtracking, parsing).

Paieška pagal raidę