Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2012-queues [2012/03/09 12:12] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-queues [2012/03/10 11:37] ikaf |
**Termin zajęć:** 13/14.03.2011 | ====== Elementarne struktury danych: kolejki i stosy ====== |
| **Termin zajęć:** 13/14.03.2012 |
| |
**Do przygotowania:** | **Do przygotowania:** |
* algorytmy zamiany notacji infixowej na ONP przy pomocy stosu | * algorytmy zamiany notacji infixowej na ONP przy pomocy stosu |
* obliczanie wartości wyrażania w notacji ONP | * 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<code> | |
#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(); | |
};</code> | |
- 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. <code> | |
#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(); | |
| |
};</code> | |
| |
* Type jest zdefiniowany za pomocą: | |
''typedef int type;'' | |
| |
| |