Ćwiczenia 3. (stosy, kolejki i listy)

Zad1.

Napisz program wykorzystujący klasę stos, który ilustruje pracę edytora, który

przekształca łańcuchy.

(a) edytory zawsze pozwalają uŜywać pewnych znaków do kasowania znaków

poprzedzających np. jeśli przyjmiemy, Ŝe & jest takim znakiem, to łańcuch: a b c &

d & & e jest w rzeczywistości łańcuchem: a e.

(b) edytory mają teŜ znaki niszczące wszystkie znaki w danej linii. Niech takim

znakiem jest @.

Edytor moŜe przetwarzać linie tekstu uŜywając stosu. Czyta on linie znak po znaku. JeŜeli znak nie jest niszczący ani kasujący, to umieszcza go na stosie. Jeśli jest niszczący - czyni

stos pustym. Po napotkaniu końca linii, jeśli stos nie pusty wszystkie elementy stosu są zdejmowane ze stosu i zapisywane na ekran. Program działa dopóki na wejściu nie pokaŜe

się pusta linia.

Zad 2. ( III program)

Napisz program, który zilustruje operacje na kolejce priorytetowej, w reprezentacji tablicowej przy czym wybierz wariant, w którym kolejka priorytetowa będzie listą

uporządkowaną nie malejąco.

Utwórz klasę PrQueue, która będzie zawierała następujące operacje:

1. Insert(x) – wstawia element ‘x’ do kolejki, wykorzystując metodę wyszukiwania

połówkowego.

2. DelMax() – usuwa element maksymalny (ostatni) z kolejki

3. Front() – zwraca element maksymalny (ostatni) z kolejki

4. Is_empty() – zwraca ‘true’, gdy kolejka pusta

5. is_Full() – zwraca ‘true’, gdy kolejka jest pełna

6. Display() – wypisuje kolejke.