Stosy i kolejki. Stos.
Stos zawierający nie więcej niż n elementów można
Stosy i kolejki są realizacjami zbiorów dynamicznych, na których są
zaimplementować w tablicy S[1..n]. Potrzebna jest dodatkowa
określone operacje dodawania nowego elementu oraz usuwania,
zmienna top, której wartość jest numerem ostatnio dodanego
przy czym element usuwany jest wyznaczony jednoznacznie.
elementu, lub 0 jeżeli stos jest pusty. Oczywiście największa
W przypadku stosu jest to element, który został dodany jako
wartość, jaką może przyjąć top wynosi n. Stos składa się z
ostatni (strategia last in, first out, w skrócie LIFO).
elementów
W przypadku kolejki usuwany jest zawsze element, który został
S[1], S[2], . . . , S[top],
dodany jako pierwszy (strategia first in, first out, w skrócie
gdzie S[1] jest elementem na dnie stosu, a S[top] jest elementem
FIFO).
na wierzchołku stosu.
Istnieje wiele sposobów implementacji stosów i kolejek. My
Operację wstawienia elementu do stosu nazywamy PUSH, a
omówimy ich realizację za pomocą zwykłej tablicy.
operację usunięcia elementu ze stosu nazywamy POP.
Operacja PUSH. Operacja POP.
Operacja POP(S, top) zdejmuje ostatnio dodany element ze stosu
Operacja PUSH(S, top, x) wstawia element x do stosu S. Gdy nie S. Próba zdjęcia elementu z pustego stosu sygnalizowana jest jako
ma wolnego miejsca w tablicy, to próba wstawienia nowego błąd niedomiaru.
elementu sygnalizowana jest jako błąd przepełnienia.
POP(S, top)
PUSH(S, top, x) 1. begin
1. begin 2. if top = 0
2. if top = n 3. then error  niedomiar
3. then error  stos przepełniony 4. else begin
4. else begin 5. top := top - 1;
5. top := top + 1; 6. return S[top + 1]
6. S[top] := x 7. end
7. end 8. end;
8. end;
Operacja POP zwraca jako swoją wartość usunięty element (wiersz
6).
Przykład Kolejka.
Stos w tablicy liczb całkowitych S[1..6].
Kolejka ma początek (głowę) i koniec (ogon). Nowy element może
Operacja top S
zostać dodany na koniec (w ogonie). Element może zostać
0 [0, 0, 0, 0, 0, 0]
usunięty jeżeli znajduje się na początku (w głowie).
PUSH(S, top, 11);
Kolejkę zawierającą nie więcej niż n - 1 elementów można
1 [11, 0, 0, 0, 0, 0]
zaimplementować w tablicy Q[1..n]. Potrzebne będą dwie
PUSH(S, top, 2);
dodatkowe zmienne: head i tail wyznaczające odpowiednio pozycję
2 [11, 2, 0, 0, 0, 0]
głowy i pozycję, na którą można wstawić nowy element.
PUSH(S, top, 9);
Elementami kolejki są
3 [11, 2, 9, 0, 0, 0]
POP(S, top);
Q[head], Q[head + 1], . . . , Q[tail - 1].
2 [11, 2, 9, 0, 0, 0]
PUSH(S, top, 7);
Zakładamy, że tablica Q jest  cykliczna , to znaczy po pozycji o
3 [11, 2, 7, 0, 0, 0]
numerze n następuje pozycja o numerze 1. Jeśli head = tail to
POP(S, top); kolejka jest pusta, a jeżeli head = tail + 1, to kolejka jest pełna.
2 [11, 2, 7, 0, 0, 0]
Operacje ENQUEUE. Operacja DEQUEUE.
Operacja DEQUEUE(Q, head) usuwa element z początku kolejki Q
Operacja ENQUEUE(Q, tail, x) wstawia element x na koniec
i zwraca go jako swoją wartość.
kolejki Q.
DEQUEUE(Q, head)
ENQUEUE(Q, tail, x)
1. begin
1. begin
2. x := Q[head];
2. Q[tail] := x;
3. if head = n
3. if tail = n
4. then head := 1
4. then tail := 1
5. else head := head + 1;
5. else tail := tail + 1
6. return x
6. end;
7. end;
Ćwiczenie.
Ćwiczenie.
Uzupełnić procedurę ENQUEUE tak, żeby próba wstawienia
Uzupełnić procedurę DEQUEUE tak, żeby próba usunięcia
elementu do pełnej kolejki była sygnalizowana jako błąd.
elementu z pustej kolejki była sygnalizowana jako błąd.
Przykład Przykład c.d.
Kolejka w tablicy liczb całkowitych Q[1..6].
Operacja head tail Q
3 5 [11, 2, 9, 7, 0, 0]
Operacja head tail Q
ENQUEUE(Q, tail, 3);
1 1 [0, 0, 0, 0, 0, 0]
3 6 [11, 2, 9, 7, 3, 0]
ENQUEUE(Q, tail, 11);
ENQUEUE(Q, tail, 5);
1 2 [11, 0, 0, 0, 0, 0]
3 1 [11, 2, 9, 7, 3, 5]
ENQUEUE(Q, tail, 2);
ENQUEUE(Q, tail, 4);
1 3 [11, 2, 0, 0, 0, 0]
3 2 [4, 2, 9, 7, 3, 5]
ENQUEUE(Q, tail, 9);
DEQUEUE(Q, head);
1 4 [11, 2, 9, 0, 0, 0]
4 2 [4, 2, 9, 7, 3, 5]
DEQUEUE(Q, head);
ENQUEUE(Q, tail, 1);
2 4 [11, 2, 9, 0, 0, 0]
4 3 [4, 1, 9, 7, 3, 5]
ENQUEUE(Q, tail, 7);
DEQUEUE(Q, head);
2 5 [11, 2, 9, 7, 0, 0]
5 3 [4, 1, 9, 7, 3, 5]
DEQUEUE(Q, head);
3 5 [11, 2, 9, 7, 0, 0]
Czas działania. Listy.
Lista jest strukturą danych, w której elementy tworzą ciąg.
Omówimy implementację listy dwukierunkowej przy użyciu
W przypadku procedur POP, PUSH, ENQUEUE i DEQUEUE
wskaz
ników. Każdy element takiej listy jest rekordem składającym
operacjami elementarnymi są działania na polach tablic S i Q oraz
się z trzech pól:
zmiennych top, head, tail. Są to: sprawdzenie czy wartość
zmiennej jest równa pewnej stałej, na przykład top = 0 oraz
key zawiera klucz elementu,
przypisania zmiennym nowych wartości, na przykład
prev zawiera wskaz
nik do poprzedniego elementu,
head := head + 1, S[top] := x.
next zawiera wskaz
nik do następnego elementu.
Zauważmy, że każda operacja elementarna w tych procedurach jest
Wskaz
nik, który na nic nie wskazuje, ma specjalną wartość NIL.
wykonywana co najwyżej raz, zatem liczba wszystkich wykonanych
Jeżeli prev[x] = NIL, to element x nie ma poprzednika, jest więc
operacji jest ograniczona przez pewna stałą, niezależną od liczby
pierwszym elementem listy, czyli jej głową. Jeżeli next[x] = NIL, to
elementów w zbiorze (stosie lub kolejce).
element x nie ma następnika, jest więc ostatnim elementem listy,
Mówimy, że procedury POP, PUSH, ENQUEUE i DEQUEUE
czyli jej ogonem.
działają w czasie O(1).
W zmiennej list będziemy przechowywać wskaz
nik do pierwszego
elementu listy. Jeżeli list = NIL, to lista jest pusta.
Przykład Wyszukiwanie w liście.
Procedura LIST-SEARCH(list, k) wyszukuje pierwszy element o
kluczu k na liście. Zwracany jest wskaz
nik do tego elementu, a
jeśli takiego nie ma, to zwracana jest wartość NIL.
/ /
list 7 2 11 5
LIST-SEARCH(list, k)
Lista dwukierunkowa reprezentująca ciąg liczb (7, 2, 11, 5).
1. begin
2. x := list;
prev
key next
Każdy element jest rekordem . Wskaz
niki są
3. while x = NIL i key[x] = k

przedstawione w postaci strzałek, / oznacza stałą NIL.
4. do x := next[x];
5. return x
6. end;
Czas wyszukiwania. Wstawianie do listy.
Procedura LIST-SEARCH działa najdłużej w przypadku, gdy
elementu o szukanym kluczu nie ma na liście, ponieważ wtedy
Procedura LIST-INSERT(list, x) wstawia element wskazywany
konieczne jest przejście całej listy.
przez x na początek listy. Zakładamy, że pole key[x] zostało
wcześniej zainicjowane.
Jeżeli lista zawiera n elementów, to w pesymistycznym przypadku
operacja z wiersza 4. będzie wykonana n razy, a warunek pętli w
LIST-INSERT(list, x)
wierszu 3. będzie sprawdzany n + 1 razy. A
ączna liczba operacji
1. begin
elementarnych w tym przypadku wynosi
2. next[x] := list;
3. if list = NIL

n + n + 1 + 2 = 2n + 3 = Ś(n).
4. then prev[list] := x;
5. list := x;
Gdy pierwszy element o szukanym kluczu znajduje się na końcu
6. prev[x] := NIL
listy, to wyszukiwanie również zajmuje czas Ś(n).
7. end;
Pesymistyczny czas działania procedury LIST-SEARCH na liście o
n elementach wynosi Ś(n).
Przykład. Usuwanie z listy.
Dodanie elementu o kluczu 7 do listy reprezentującej ciąg (2, 11, 5)
Procedura LIST-DELETE(list, x)  wycina z listy element
wskazywany przez x.
x
7
LIST-DELETE(list, x)
/ /
list 2 11 5 1. begin
2. if prev[x] = NIL

4. then next[prev[x]] := next[x]
/
list 7
5. else list := next[x];
6. if next[x] = NIL

/
2 11 5
7. then prev[next[x]] := prev[x]
8. end;
Po dodaniu lista reprezentuje ciąg (7, 2, 11, 5).
Przykład. Czas działania.
Usunięcie z listy reprezentującej ciąg (7, 2, 11, 5) elementu o kluczu
Podobnie jak w przypadku stosu i kolejki, operacje LIST-INSERT i
11.
LIST-DELETE działają w czasie O(1).
/ /
list 7 2 11 5
Pesymistyczny czas usunięcie elementu o zadanym kluczu z listy
zawierającej n elementów wynosi Ś(n), ponieważ trzeba najpierw
wywołać procedurę LIST-SEARCH, aby uzyskać wskaz
nik do
takiego elementu:
/ /
list 7 2 11 5
1. x := LIST-SEARCH(list,k);
2. LIST-DELETE(list, x);
Po usunięciu lista reprezentuje ciąg (7, 2, 5).
Rodzaje list.
Oprócz omówionej przez nas listy dwukierunkowej stosuje się inne
rodzaje list. Lista może być:
jednokierunkowa - elementy nie zawierają wskaz
nika prev,
cykliczna - pole prev elementu w głowie wskazuje na ogon, a
pole next w ogonie wskazuje na głowę,
posortowana - kolejność elementów na liście jest zgodna z
porządkiem ich kluczy (zakładamy, że zbiór kluczy jest liniowo
uporządkowany); element o najmniejszym kluczu znajduje się
w głowie listy, a ten o największym kluczu w ogonie.
Zauważmy, że stos i kolejkę możemy traktować jako specjalne
rodzaje list, ponieważ ich elementy tworzą ciąg (uporządkowany
według kolejności dodania).