Termin zajęć: 12/13.04.2011
Do przygotowania:
Znajomość zasad działania podstawowych struktur danych:
Odwrotna Notacja Polska:
co to jest notacja postfixowa, prefixowa i infixowa?
algorytmy zamiany notacji infixowej na ONP przy pomocy stosu
obliczanie wartości wyrażania w notacji ONP
Proszę zaimplementować następujące klasy wraz z odpowiednimi metodami:
Stos: implementujemy z wykorzystaniem tablicy, przechowujemy indeks elementu na szczycie stosu
#define MAX 10 // rozmiar stosu
class stack
{
private:
type arr[MAX]; // tablica z danymi
int top; // indeks elementu na wierzchu stosu
public:
stack(); // konstruktor
void push(type a); // połóż element na stosie
type pop(); // zdejmij element ze stosu
type peek(); // zwróć element ze szczytu stosu, nie zdejmując go
bool isEmpty();
bool isFull();
};
kolejka FIFO: dodajemy elementy na koniec kolejki, pobieramy z jej początku. Kolejka powinna być implementowana tak, że po wyciągnięciu elementu z kolejki wszystkie pozostałe są przesuwane na początek, czyli usuwany jest zawsze pierwszy element kolejki.
#define MAX 5 // rozmiar kolejki
class queue
{
private:
type t[MAX];
int rear;
public:
queue();
type remove(); // usuwa i zwraca pierwszy element kolejki
void insert(type item); // wstawia element na koniec kolejki
type front(); // zwraca pierwszy element kolejki nie usuwając go
bool isEmpty();
bool isFull();
};
typedef int type;