Kas yra stack ir kam jis naudojamas?

Question

Accepted Answer

**stack** yra **LIFO** (Last-In, First-Out) kolekcija: paskutinis įdėtas elementas pirmasis išimamas. Jūs liečiate tik **viršūnę**.

## Operacijos

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## Pavyzdys

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

Visos operacijos yra **O(1)**, kai jas palaiko dinaminis masyvas arba susietasis sąrašas.

| Operacija | Laikas |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Dažnai naudojami atvejai

- **Funkcijos iškvietimo stack** — sekimas aktyvūs skambučiai ir lokalūs kintamieji.
- **Atšaukti/Pakartoti** — įdėkite kiekvieną veiksmą; išimkite, jei norite atšaukti.
- **Išraiškos įvertinimas / analizavimas** — skliaustų atitikimas, konversija iš infix į postfix.
- **Atgalinis nuėjimas ir DFS** — prisiminkite, kur grįžti.

## Kodėl tai svarbu

Stack modeliuoja „pirmiausia atlikti naujausią veiksmą", kuris pasirodo visur: nuo rekursijos iki naršyklės atgal mygtuko.

Atidesnis LIFO šablono atpažinimas nedelsiant siūlo stack, dažnai paverčiant sudėtingą problemą keliomis švaromis push/pop eilutėmis.