Różnice
Różnice między wybraną wersją a wersją aktualną.
|
|
pl:dydaktyka:asd:cwiczenia:2012-queues [2012/03/09 12:12] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-queues [2019/06/27 15:50] |
**Termin zajęć:** 13/14.03.2012 | |
| |
**Do przygotowania:** | |
- Znajomość zasad działania podstawowych struktur danych: | |
* stos | |
* kolejka FIFO | |
- 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<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;'' | |
| |
| |