A verem hasonlóan működik, mint egy földbe ásott verem. Az elemeket éppen fordított sorrendben vesszük ki, mint ahogy betettük.

Adatszerkezet alatt adatok tárolásának és elrendezésének egy lehetséges módját értjük. Az adattípus a mi értelmezésünkben egy adatszerkezet, a rajta értelmezett műveletekkel együtt.

A verem LIFO (last-in first-out) adattípus, azaz mindig csak az utoljára betett adat elérhető, illetve törölhető. Egyaránt lehet tömbösen és láncoltan is ábrázolni.

Tömbös ábrázolás:

A verem tömbös ábrázolásában a $A: \mathcal{T} []$ (dinamikus tömb) mellett az $n : \mathbb{N}$ (a verem aktuális mérete) is a verem részét képezi.

$Stack$

$- \space A: \mathcal{T} []$ $- \space n : \mathbb{N}$

$+ \space Stack ( m : \mathbb{N} ) \space \{ A := \text{new} \space \mathcal{T}[m]; n := 0 \}$ $+ \space \sim Stack() \space \{ delete \space A \}$ $+ \space push(x : \mathcal{T})$ $ + \space pop() : \mathcal{T}$ $+ \space top() : \mathcal{T}$ $+ \space isFull() : \mathbb{B} \space \{ \text{return} \space n = A.length \}$ $+ \space isEmpty() : \mathbb{B} \space \{ \text{return} \space n = 0 \}$ $+ \space setEmpty() \space \{ n := 0 \}$

Mivel van a veremnek egy maximális mérete, ezért bevezetjük az $IsFull()$ műveletet is.

A $push()$ a verem tetejére teszi a paraméterként kapott elemet. A $pop()$ visszaadja a legfelső elemet a veremből és ki is törli azt a veremből. A $top()$ visszaadja a legfelső elemet és a veremben hagyja azt.

Ha egy üres veremből próbálunk meg elemet kivenni, a verem alulcsordul, amit hibának tekintünk. Ha a tömb betelt és elemet raknánk bele, akkor a verem túlcsodul, amit szintén hibának tekintünk.

Láncolt ábrázolás:

A verem láncolt reprezentációjában a $L$ pointer nem csak az adattípushoz biztosít hozzáférést, hanem egyben a verem felső elemére mutat, ugyanis mindig a láncolt lista elejére szúrjuk be az új elemet. Ezért nem kell külön bevezetni egy felső elemre mutató pointert és ezért elég lesz az S1L.

$Stack$

$- \space L : E1^*$

$+ \space Stack () \space \{ L := \emptyset \}$ $+ \space push(x : \mathcal{T})$ $ + \space pop() : \mathcal{T}$ $+ \space top() : \mathcal{T}$ $+ \space isEmpty() : \mathbb{B} \space \{ \text{return} \space L = \emptyset \}$ $+ \space setEmpty() \space \{ L := \emptyset \}$

A láncolt ábrázolású verem műveletei között nem szerepel az $IsFull()$ művelet, mivel ebben a reprezentációban nem számolunk a tárolókapacitás gyakorlati felső korlátjával. A destruktor futási ideje, így $\Theta (n)$.

A $push()$ a lista elejére szúrja be a paraméterként kapott elemet. A $pop()$ visszaadja a lista első elemét és ki is törli a lista elejéről. A $top()$ visszaadja a lista elején lévő elemet.

Műveletigény:

A tömbös és a láncolt reprezentációban a verem minden művelete konstans időben végrehajtható, azaz $\Theta (1)$, mivel nem tartalmaz se ciklust, se rekurziót.

Gyakorlati alkalmazása:

A verem alapvetően egy sorozat megfordítására alkalmas. Ha azonban a verembe írást és a kivételt nem elkülönítve, egymás után két blokkban, hanem váltakozva alkalmazzuk, akkor egy sorozatnak számos átrendezését meg tudjuk valósítani. Egy másik alkalmazása a lengyel forma.