Struktury danych: stos i kolejka
²'
Stos
²'
Odwrotna Notacja Polska (ONP)
²'
Kolejka
Zastosowanie
Stos jest dobrym rozwiÄ…zaniem, gdy gromadzÄ…c jakieÅ› dane
przeprowadzamy operacje najpierw na tych najnowszych (ostatnio
dodanych), a gdy te nie są nam już potrzebne, to zabieramy się za te
nieco starsze.
Ideę stosu danych można zilustrować jako stos położonych jedna na
drugiej książek  nowy egzemplarz kładzie się na wierzch stosu i z
wierzchu stosu zdejmuje siÄ™ kolejne egzemplarze. Elementy stosu
poniżej wierzchołka stosu można wyłącznie obejrzeć, aby je ściągnąć,
trzeba najpierw po kolei ściągnąć to, co jest nad nimi.
Stos jest stosowany w systemach komputerowych na wszystkich
poziomach funkcjonowania systemów informatycznych, używane są
przez procesory do chwilowego zapamiętywaniarejestrów procesora ,
do przechowywania zmiennych lokalnych , a także w programowaniu
wysokopoziomowym.
Zważywszy na kolejność dodawania i usuwania elementów ze
stosu, struktura ta określana jest
jako LIFO (ang. Last In First Out - Ostatni na wejściu,
Pierwszy na wyjściu).
Dobrym przykładem na działanie stosu może być ONP ale
najpierw wyjaśnijmy czym to jest i jak to się pisze.
Do implementacji stosu o stałym
rozmiarze n wystarczy n-elementowa tablica
i jedna zmienna, która będzie przetrzymywać
aktualną liczbę elementów.
const
StosMax = 10; //Stos 10 elementowy
var
stos : array[1..StosMax] of integer;
szczyt : integer = 0;
procedure push(element : integer);
begin
if szczyt < StosMax then
begin
//wrzuć na stos
Inc(szczyt);
stos[szczyt] := element;
end
else
begin
writeln('Stos jest pelny'); //Stos jest pełny
end;
end;
function pop : integer;
begin
if szczyt <> 0 then
begin
//zdejmij ze stosu
pop := stos[szczyt];
Dec(szczyt);
end
else
begin
writeln('Nie ma juz nic na stosie');
end;
end;
Odwrotna Notacja Polska
jest sposobem zapisu wyrażeń arytmetycznych, w którym znak
wykonywanej operacji umieszczony jest po operandach (zapis
postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie
algebraicznym (zapis infiksowy ) lub przed operandami jak w zwykłej
notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą
rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie
określa kolejność wykonywanych działań.
ONP bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i
zachowaniem kolejności działań. Zarówno algorytm konwersji notacji
konwencjonalnej (infiksowej) na odwrotnÄ… notacjÄ™ polskÄ… (postfiksowÄ…),
jak i algorytm obliczania wartości wyrażenia danego w ONP są bardzo
proste i wykorzystujÄ… stos .
ONP jest używana w niektórych językach programowania (np. FORTH ,
Postscript ) oraz w niektórych kalkulatorach naukowych (np.
Hewlett-Packard , National Semiconductor ). Programy komputerowe
kompilujące program dokonują analizy wyrażenia arytmetycznego,
przekształcając je na ciąg instrukcji odpowiadający odwrotnej notacji
polskiej. Wyrażenie to jest obliczane podczas wykonywania programu.
Przykład: ((3+7)/5+(14-3)*4)/2
((3+7)/5+(14-3)*4)/2
²'
Najprościej pozaznaczać kolejność działań
a)3+7
b)a/5
c)14-3
d)c*4
e)b+d
f)e/2
²'
Teraz zapisujemy po kolei w ONP.
3 7 + 5 / 14 3  4 * + 2 /
3 7 + 5 / 14 3  4 * + 2 /
²'
Na ONP zastosujemy działanie stosu
Gdy wczytany element jest liczbÄ…, to zapisujemy jÄ… na stos. W przeciwnym
wypadku należy wykonać działanie arytmetyczne na 2 ostatnich liczbach na
stosie. Wartość wyrażenia znajduje się na stosie.
START
Koniec
TAK
KONIEC
danych?
Wyświetl wynik
NIE
Pobierz symbol z lewej ku
prawej
Czy to
TAK
Wrzuć na stos
argument?
NIE
Pobierz argumenty ze
stosu, wykonaj
Czy to
TAK
działania , wynik na stos.
operator?
NIE
BA

D
Zamiana wyrażenia algebraicznego zapisanego w notacji infiksowej na postać
postfiksowÄ… (ONP)
Gdy wczytany element jest:
- stałą lub nazwą zmiennej: to przesyłamy go na wyjście.
- '(': to dopisujemy go na stos.
- ')': to odczytaj ze stosu i prześlij na wyjście wszystkie operatory aż do
nawiasu '(', który należy odczytać, ale nie wysyłać na wyjście.
- '+, - , *, /, %': Jeżeli priorytet operatora wczytywanego jest wyższy od
priorytetu operatora znajdującego się w wierzchołku stosu lub stos jest
pusty, to dopisz do stosu operator, a w przeciwnym razie odczytaj i
prześlij na wyjście kolejne operatory z wierzchołka stosu o priorytecie
większym lub równym priorytetowi wczytanego operatora, po czym wpisz
do stosu operator.
Jeśli priorytet operatora wczytywanego jest równy priorytetowi operatora na
stosie to dopisz go na stos.
Np:12 + a * (b * c + d / e)
ONP:12 a b c * d e / + * +
Kolejka
Kolejka (ang. queue)  liniowa struktura danych , w której nowe dane
dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane
do dalszego przetwarzania (bufor typu FIFO, First In, First
Out; pierwszy na wejściu, pierwszy na wyjściu).
Specjalną modyfikacją kolejki jest kolejka priorytetowa  każda ze
znajdujÄ…cych siÄ™ w niej danych dodatkowo ma przypisany priorytet,
który modyfikuje kolejność póz
niejszego wykonania. Oznacza to, że
pierwsze na wyjściu niekoniecznie pojawią się te dane, które w kolejce
oczekują najdłużej, lecz te o największym priorytecie.
Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego
rodzaju obsługą zdarzeń. W szczególności w systemach operacyjnych
ma zastosowanie kolejka priorytetowa, przydzielajÄ…ca zasoby
sprzętowe uruchomionym procesom .
W porównaniu ze stosem kolejki są rzadziej stosowane w praktyce
programowania.
Pewne zagadnienia natury algorytmicznej dajÄ… siÄ™ jednak relatywnie
łatwo rozwiązywać właśnie przy użyciu tej struktury