Kaudze (datu struktūra) — LIFO princips, operācijas un piemēri programmēšanā
Uzzini kaudzes (LIFO) principu, pamatoperācijas un praktiskus programmēšanas piemērus — skaidrojums, ilustrācijas un kods efektīvai datu apstrādei.
Kaudze ir viena no svarīgākajām datu struktūrām datorzinātnē. Lai saprastu, kā darbojas kaudze, iedomājieties spēļu kāršu kasti, kas ir novietota uz leju. Mēs varam viegli piekļūt tikai tai kartei, kas atrodas virsū. Ja vēlamies apskatīt augšējo karti, varam darīt divas lietas: varam uz to paskatīties, bet atstāt to uz kaudzes, vai arī varam to noņemt. Kad mēs atvāžam augšējo objektu, mēs to noņemam no kaudzes. Ja mēs vēlamies kaudzes augšpusē pievienot vēl vienu karti, mēs to izstumjam.
Šādu kaudzi sauc par LIFO (last-in-first-out) kolekciju. Tas nozīmē, ka pēdējā pievienotā (ievietotā) lieta ir pirmā, kas tiek izņemta. Piemēram, ja pēdējā kārts, ko mēs pievienojām mūsu kāršu kaudzei, bija dūzis, tad pirmā kārts, ko mēs no tās izvilkām, būs tas pats dūzis.
Pamatkoncepcijas un operācijas
Kaudze parasti nodrošina šādas pamata operācijas:
- push(x) — pievieno elementu x kaudzes augšpusē.
- pop() — noņem un atgriež augšējo elementu. Ja kaudze ir tukša, parasti tiek ziņots par underflow.
- peek() vai top() — atgriež augšējo elementu, to neizņemot.
- isEmpty() — pārbauda, vai kaudze ir tukša.
- size() — atgriež elementu skaitu kaudzē (ja šo informāciju uztur).
Izpilde un sarežģītība
- Laika sarežģītība: parasti push, pop un peek operācijas veicamas O(1) laikā.
- Vietas sarežģītība: ja kaudze tiek realizēta ar dinamisku atmiņu (piem., saistītu sarakstu), vietas izmantošana ir O(n), kur n ir elementu skaits. Ar statisku masīvu izmērs ir ierobežots, un var rasties overflow.
- Riska gadījumi: stack overflow (pārpildes) gadījumā, ja pievieno vairāk elementu, nekā paredzēts, un stack underflow, ja mēģina izņemt elementu no tukšas kaudzes.
Realizācijas veidi
- Masīvs (array) — vienkārša un ātra realizācija; jāuzmana maksimālais izmērs vai jāizmanto dinamiska pārmērošana (reallocation).
- Saistīts saraksts (linked list) — pievienošana un noņemšana augšpusē var būt O(1) bez nepieciešamības pārmērīgi pārmērīt atmiņu.
- Deque (divpusējs rinda) — ja nepieciešamas operācijas abās galos, var izmantot divpusēju rindu kā elastīgāku struktūru.
Piemēri un pielietojumi programmēšanā
Kaudzes ir plaši izmantotas dažādās vietās:
- Funkciju izsaukumu izsekošana (call stack) — sistēmas izmanto kaudzi, lai atcerētos atgriešanās adreses un lokālās mainīgās.
- Atcelšanas (undo) funkcijas redaktoros — pēdējā darbība tiek atcelta pirmā.
- Izteiksmju novērtēšana un konvertācija (piem., infiksu uz postfixu/RPN), parsēšana un sintakses analīze.
- DFS (dziļuma pirmā meklēšana) grafu algoritmos.
Kods — vienkārši piemēri
Vienkāršs virknes (pseudokods) piemērs kaudzes operācijām:
initialize stack S procedure push(x): S.top = S.top + 1 S[S.top] = x procedure pop(): if S.top == 0: error "Underflow" x = S[S.top] S.top = S.top - 1 return x procedure peek(): if S.top == 0: error "Empty" return S[S.top]
Python stilā (izmantojot sarakstu kā kaudzi):
stack = [] # push stack.append(10) # pop x = stack.pop() # noņem un atgriež pēdējo elementu # peek top = stack[-1] if stack else None
Ierobežojumi un padomi
- Ja izmantojat statisku masīvu, plānojiet maksimālo izmēru vai nodrošiniet pārmērošanu, lai izvairītos no overflow.
- Sekojiet kļūdām, kas saistītas ar pop no tukšas kaudzes.
- Izvēlieties realizācijas veidu atkarībā no vajadzības pēc ātruma, atmiņas un vienkāršības.
Kaudze ir vienkārša, bet ļoti noderīga abstrakta datu struktūra ar plašu pielietojumu klāstu programmēšanā un algoritmos. Izprotot LIFO principu un pamatoperācijas, var efektīvi izmantot kaudzes dažādu problēmu risināšanā.


Divas darbības ar kaudzi: push un pop.
Vēsture
Pirmo reizi šo skursteni 1955. gadā ierosināja un 1957. gadā patentēja vācietis Frīdrihs L. Bauers. Aptuveni tajā pašā laikā to pašu koncepciju neatkarīgi izstrādāja austrālietis Čārlzs Leonards Hamblins.
Citas darbības
Mūsdienu datoru valodās kaudze parasti tiek realizēta ar vairāk operācijām nekā tikai "push" un "pop". Dažās implementācijās ir funkcija, kas atgriež kaudzes pašreizējo garumu. Vēl viena tipiska palīgoperācija ir "top" (pazīstama arī kā "peek"), kas var atgriezt pašreizējo kaudzes augšējo elementu, to neizņemot. Vēl viena izplatīta operācija ir "dup", kas izveido kaudzes augšā esošā elementa kopiju.
Saistītās lapas
- Kraušanas mašīna
Meklēt