Stosy - struktura algebraiczna
Stosy to struktura algebraiczna znajdująca wiele zastosowań w informatyce. By wymienić kilka przykładów: automaty ze stosem to ważna część każdego kompilatora, stos rekordów aktywacji to podstawowa struktura maszyny wirtualnej (lub running-systemu), ...
Definicja
Struktura algebraiczna
taka, że jej uniwersum jest sumą dwu rozłącznych zbiorów [math]E[/math] i [math]S[/math], [math]E \cap S=\emptyset[/math]z działaniami
[math]w\colon E \times S \rightarrow S [/math]
[math]u\colon S \rightarrow S [/math]
[math]p\colon S \rightarrow E [/math]
[math]n\colon S \rightarrow \{true, false\}[/math]
[math]=_E \colon E \times E \rightarrow \{true, false\} [/math]
[math]=_S \colon S \times S \rightarrow \{true, false\} [/math]
które zapewniają prawdziwość następującego zbioru aksjomatów
[math]\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(w(e,s)) [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ p(w(e,s)) =_E e [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ u(w(e,s)) =_S s [/math]
[math]\forall_{e \in E}\,\forall_{s \in S}\ \lnot n(s) \implies w(p(s),u(s)) =_S s [/math]
[math]\forall_{s \in S}\ \{\mathbf{while}\ \lnot n(s) \ \mathbf{do} \ s:= u(s) \ \mathbf{od}\}\ n(s)[/math]
oraz aksjomaty identyczności dla relacji [math]=_E[/math] i [math]=_S[/math]
jest strukturą stosów. koniec definicji.
Zbiór [math]E[/math] jest nazywany zbiorem elementów. Elementy zbioru [math]S[/math] to stosy. Działanie [math]w[/math] najczęściej jest nazywane push, działanie [math]u[/math] to operacja pop, działanie [math]p[/math] to operacja top. Predykat [math]n[/math] oznacza relację empty.
