28. 2. 2023
Zásobník funguje na principu LIFO = last in, first out. Hlavními operacemi se zásobníkem jsou operace push (vkládání prvku) a pop (vrátí naposled přidaný prvek, a odstraní jej).
struct stack
data:[]key
top:int
Operace určená ke vkládání prvků. Daný klíč k vloží na 'top'. Podmínka if v následujícíh pseudokódu řeší, jestli máme dostatek alokovaného místa.
push(S:stack, k:key)
if S.top < len(S.data)
S.data[S.top] <- k
S.top <- S.top + 1
Operace k odebírání prvku ze zásovníku. Odebíráme vždy poslední prvek v poli. LIFO protože jako poslední máme prvek, který jsme naposledy přidali, takže půjde i jako první pryč.
pop(S:stack):
if S.top = 0
return nil
S.top <-- S.top - 1
return S.data[S.top]
Vytvoříme algoritmus pro vyhodnocení správně uzávorkovaného aritmetického výrazu. Máme dva zásobníky: Q1 pro operátory, Q2 pro čísla.
Budeme číst výraz zleva doprava. Symbol ( přeskočíme, protože nám pouze signalizuje začátek výrazu. Následně se budeme chovat podle toho co čteme za znak. Jestli čteme číslo, tak jej vložíme do zásovníku Q2. Narazili jsme na operátor, pak jej vložíme do zásobníku Q1. Takto si postupně načteme celý výraz do zásobníků. Když dojdeme na konec výrazu - tedy narazíme na znak ), pak začneme výraz vyhodnocovat tím, že odebere z Q1 operátor a z Q2 dva operandy a na ně operátor aplikujeme. Výsledek potom vložíme do Q2.
Fronta funguje na principu FIFO = first in, first out. Jejími hlavními operacemi je enqueue(vložení prvku) a dequeue(odebrání prvku).
struct queue
data:[]key
head:int - index nejdříve přidaného prvku
tail:int - index prvního volného místa
Pokud je fronta prázdná tak se hodnoty head a tail rovnají. Naopak pokud je fronta plná, pak (tail + 1) mod len(data) = head
Operace pro vkládání prvku do fronty. Prvek vkládáme na první volné místo, které je určení pomocé tail. Musíme jen ošetřit, že již není zásobník plný. Po vložení klíče je nutné ještě upravit hodnotu tail.
enqueue(Q:queue, k:key):
if (Q.tail +1) mod len(Q.data) != Q.head:
Q.data[Q.tail] <- k
Q.tail <- (Q.tail +1) mod len(Q.data)
Operace pro mazání prvků ve frontě. Smaže první vložený prvnek a posune se na druhý vložený prvek. Mažeme tedy prvky od nejstaršího.
dequeue(Q:queue):
if Q.head = Q.tail
return nil
x <- Q.data[Q.head]
Q.head <- (Q.head + 1) mod len(Q.data)
return x
Minule jsme si představili pointer machine a jeho velmi důležitou strukturu node. Spojový seznam jsou tedy uzly spojené pomocí pointerů. V základu dělíme seznamy na jednosměrné a obousměrné.
Stačí si nám tedy pamatovat první uzel seznamu, protože tato struktura nám odkazuje na další uzly, takže se k nim dokážeme jednoduše dostat. Pokud je seznam nebo následující položka prázdná (neexistuje), pak je hodnota nil (None).
struct node:
id:key
next:node - další uzel v seznamu
Vyhledávání v jednosměrném seznamu provádíme pomocí cyklu a posunování do dalších uzlů.
search(r:node, k:key):
x <- r
while x != nil a současně x.id != k
nastav x <- x.next
return x
Přístup k n-tému prvku provádíme velmi podobně jako vyhledávání.
nth(r:node, n:int):
m <- 0
x <- r
while x != nil a současně m < n
x <- x.next
m <- m + 1
return x
Vkládání uzlu za uzel probíhá přepojením pointerů.
insert-after(r:node, added:node):
added.next <- r.next
r.next <- added
return r
Odstranení následujícího uzlu
remove-after(r:node):
ret <- r.next
if r.next != nill
r.next <- r.next.next
return ret
Přidávání uzlu je operace, která může změnit první uzel, proto musí vracet pointer na první uzel seznamu.
insert-nth(r:node, added:node, n:int):
if n = 0:
added.next <- r
return added
x <- nth(r, n - 1)
if x != nil:
insert-after(x, added)
return r
Odstranění prvního uzlu je speciální případ. V ostatních případech musíme nejdřív najít uzel před ostraňovaným uzlem.
remove-nth(r:node, n:int):
if r = nil:
return (nil, nil)
if n = 0:
return (r, r.next)
x <- nth(r, n-1)
if x != nil:
x <- delete-after(x)
return (x, r)
remove(r:node, d:node):
if d == r:
return r.next
x <- r
while x.next != d a zároveň x.next != nil:
x <- x.next
delete-after(x)
return r
Spojení seznamů
concatenate(r:node, s:node):
pokud je jeden z uzlů roven nil, vrať druhý uzel jako výsledek
x <- r
while x != nil:
x <- x.next
x.next <- S
return r