AiSD (index)

AiSD (8) - ADT QUEUE

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

WPROWADZENIE

Kolejka to ADT, który pozwala zapisywać dane i następnie pobierać je w takiej kolejności, w jakiej je zapisano (ang. first in, first out, FIFO; pierwszy wchodzi, pierwszy wychodzi). Typowe operacje dla ADT QUEUE są następujące:

• konstruktor tworzący pustą kolejkę,
• testowanie, czy kolejka nie jest pusta [empty()],
• odczyt liczby elementów w kolejce [size()],
• wstawienie elementu na koniec kolejki [push(item) lub put(item)],
• usuwanie pierwszego elementu z kolejki [pop() lub get()],
• dostęp do pierwszego elementu kolejki [front()],
• dostęp do ostatniego elementu kolejki [back()],
• czyszczenie kolejki [clear()].

// https://en.cppreference.com/w/cpp/container/queue

// https://en.cppreference.com/w/cpp/container/deque

#include <queue>

// W STL std::queue jest zbudowana na bazie std::deque.
// Przykład użycia kolejki.
std::queue<int> Q;   // domyślnie std::deque
assert( Q.empty() );
for (auto item : {1, 2, 3, 5, 7})
    Q.push(item);   // wstawienie do kolejki (na koniec)
assert( Q.front() == 1 );   // odczyt
assert( Q.back() == 7 );   // odczyt
assert( Q.size() == 5 );
Q.front() = 11;   // zmiana na początku kolejki
Q.back() = 77;   // zmiana na końcu kolejki
assert( Q.front() == 11 );
assert( Q.back() == 77 );
while(!Q.empty()) {
    std::cout << Q.front() << std::endl; // odczyt
    Q.pop();   // usuwa z kolejki (z początku) 11, 2, 3, 5, 77
}

// Interfejs kolejki.
template <typename T>
class MyQueue {
    // zależne od implementacji
public:
    MyQueue(); // default constructor
    ~MyQueue();
    MyQueue(const MyQueue& other); // copy constructor
    MyQueue(MyQueue&& other); // move constructor
    MyQueue& operator=(const MyQueue& other); // copy assignment operator, return *this
    MyQueue& operator=(MyQueue&& other); // move assignment operator, return *this
    bool empty() const; // checks if the container has no elements
    std::size_t size() const; // liczba elementów w kolejce
    void push(const T& item); // dodanie na koniec, push_back(item)
    void push(T&& item); // dodanie na koniec, push_back(std::move(item))
    T& front(); // zwraca koniec, nie usuwa
    T& back(); // zwraca koniec, nie usuwa
    void pop(); // usuwa początek kolejki, pop_front()
    void clear(); // czyszczenie listy z elementów
    void display();
};

ZADANIE 8.1

Przygotować implementację realizującą ADT QUEUE na bazie tablicy cyklicznej. Kolejne elementy będą wstawiane do tablicy cyklicznie, czyli po dojściu do końca tablicy będzie przejście do początku tablicy. Rozmiar tablicy jest o jeden większy niż maksymalna planowana liczba elementów w kolejce, po to aby rozróżnić sytuacje pustej i pełnej kolejki.

// myqueue.h
template <typename T>
class MyQueue {
    T* tab;
    std::size_t msize; // największa możliwa liczba elementów plus jeden
    std::size_t head; // pierwszy do pobrania
    std::size_t tail; // pierwsza wolna pozycja
public:
    MyQueue(std::size_t s=10) : msize(s+1), head(0), tail(0) {
        tab = new T[s+1];
        assert( tab != nullptr );
    } // default constructor
    ~MyQueue() { delete [] tab; }
    MyQueue(const MyQueue& other); // copy constructor
    MyQueue(MyQueue&& other); // move constructor
    // UWAGA Po przeniesieniu other.msize = 1, other.head = other.tail = 0.
    MyQueue& operator=(const MyQueue& other); // copy assignment operator, return *this
    MyQueue& operator=(MyQueue&& other); // move assignment operator, return *this
    // UWAGA Po przeniesieniu other.msize = 1, other.head = other.tail = 0.
    bool empty() const { return head == tail; }
    bool full() const { return (head + msize -1) % msize == tail; }
    std::size_t size() const { return (tail - head + msize) % msize; }
    std::size_t max_size() const { return msize-1; }
    void push(const T& item); // dodanie na koniec
    void push(T&& item); // dodanie na koniec
    T& front() { return tab[head]; } // zwraca początek
    T& back() { return tab[(tail + msize -1) % msize]; } // zwraca koniec
    void pop(); // usuwa początek
    void clear(); // czyszczenie listy z elementów
    void display();
};

ZADANIE 8.2

Przygotować implementację realizującą ADT QUEUE na bazie listy powiązanej pojedynczo. Wykorzystać klasę SingleList [push_back(), pop_front()] lub std::forward_list [tu jest trudniej, bo nie ma back() i push_back()].

ZADANIE 8.3

Przygotować implementację realizującą ADT QUEUE na bazie listy powiązanej podwójnie. Wykorzystać klasę DoubleList lub std::list. Możliwe są dwa warianty realizacji push() i pop(): (a) push_back() i pop_front(), (b) push_front() i pop_back().

ZADANIE 8.4

Przygotować implementację realizującą ADT QUEUE na bazie dwóch stosów. Wykorzystać std::stack lub MyStack z zestawu nr 7.

AiSD (index)