Termin zajęć: 12/13.04.2011

Do przygotowania:

  1. Znajomość zasad działania podstawowych struktur danych:
    • stos
    • kolejka FIFO
  2. 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
  3. Proszę zaimplementować następujące klasy wraz z odpowiednimi metodami:
    1. 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();
      };
    2. 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();
      
      };
  • Type jest zdefiniowany za pomocą:

typedef int type;

pl/dydaktyka/asd/cwiczenia/2011-queues.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0