AiSD (6) - ADT DEQUE

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.

WPROWADZENIE

ADT DEQUE (double-ended queue, kolejka dwustronna) reprezentuje kontener, który pozwala na szybkie O(1) dodawanie i usuwanie elementów z obu końców. W STL mamy kolejkę std::deque, która pozwala dodatkowo na swobodny dostęp do wszystkich elementów w stałym czasie O(1). Typowe operacje dla ADT DEQUE są następujące:

konstruktor tworzący pustą listę,
testowanie, czy lista nie jest pusta [empty()],
odczyt liczby elementów na liście [size()],
dołączanie elementu na początek listy [push_front(item)],
dołączanie elementu na koniec listy [push_back(item)],
dostęp do głowy (head), czyli pierwszego (lewego skrajnego) elementu [front()],
dostęp do ogona (tail), czyli ostatniego (prawego skrajnego) elementu [back()],
usunięcie elementu pierwszego [pop_front()],
usunięcie elementu ostatniego [pop_back()],
czyszczenie listy [clear()],
dostęp do elementu o danym indeksie i,
dołączanie elementu przed element na pozycji i [insert()],
usunięcie elementu o danym indeksie i [erase()].

ADT DEQUE może być zaimplementowany jako lista powiązana podwójnie, tablica cykliczna lub zestaw tablic o stałym rozmiarze z dodatkowymi mechanizmami (STL).

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

#include <deque>

// std::deque is an indexed sequence container that allows fast insertion
// and deletion at both its beginning and its end.
// The elements of a deque are not stored contiguously.
// The storage of a deque is automatically expanded and contracted as needed.

// Przykład użycia std::deque.
std::deque<int> Q; 
assert( Q.empty() );
for (auto item : {1, 3, 5})
    Q.push_front(item);   // wstawienie do kolejki
for (auto item : {2, 4, 6})
    Q.push_back(item);   // wstawienie do kolejki
// Zawartość kontenera: 5 3 1 2 4 6
assert( Q.front() == 5 );
assert( Q.back() == 6 );
assert( Q.size() == 6 );
Q.front() = 55;
Q.back() = 66;
// Zawartość kontenera: 55 3 1 2 4 66
Q.clear();
assert( Q.empty() );

// Interfejs kolejki dwustronnej
template <typename T>
class MyDeque {
    // zależne od implementacji
public:
    MyDeque(); // default constructor
    ~MyDeque();
    MyDeque(const MyDeque& other); // copy constructor
    MyDeque(MyDeque&& other); // move constructor
    MyDeque& operator=(const MyDeque& other); // copy assignment operator, return *this
    MyDeque& operator=(MyDeque&& 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_front(const T& item); // dodanie na początek O(1)
    void push_front(T&& item); // dodanie na początek O(1)
    void push_back(const T& item); // dodanie na koniec O(1)
    void push_back(T&& item); // dodanie na koniec O(1)
    T& front(); // zwraca początek, nie usuwa
    T& back(); // zwraca koniec, nie usuwa
    void pop_front(); // usuwa początek kolejki O(1)
    void pop_back(); // usuwa koniec kolejki O(1)
    void clear(); // czyszczenie listy z elementów
    void display();
    void display_reversed();
    // Operacje z indeksami.
    T& operator[](std::size_t pos); // podstawienie L[pos]=item, odczyt L[pos]
    const T& operator[](std::size_t pos) const; // dostęp do obiektu const
    void erase(std::size_t pos);
    int index(const T& item); // jaki index na liście (-1 gdy nie ma)
    void insert(std::size_t pos, const T& item); // inserts item before pos
    void insert(std::size_t pos, T&& item); // inserts item before pos
    // Jeżeli pos=0, to wstawiamy na początek.
    // Jeżeli pos=size(), to wstawiamy na koniec.
};

ZADANIE 6.1

Przygotować implementację realizującą ADT DEQUE na bazie tablicy o stałym rozmiarze (tablica cykliczna), ustalanym w czasie tworzenia listy. 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.

Przykładowe operacje dla tablicy pięcioelementowej (msize = 5).
W tablicy możemy przechowywać maksymalnie cztery elementy!
kolejka pusta (head = tail)
+--+--+--+--+--+ head = 0 (pierwszy zajęty)
|  |  |  |  |  | tail = 0 (pierwszy wolny)
+--+--+--+--+--+
push_back(11)
push_back(22)
+--+--+--+--+--+ head = 0
|11|22|  |  |  | tail = 2
+--+--+--+--+--+
push_front(33)
+--+--+--+--+--+ head = 4
|11|22|  |  |33| tail = 2
+--+--+--+--+--+
push_front(44), kolejka pełna ((tail + 1) % msize == head)
+--+--+--+--+--+ head = 3
|11|22|  |44|33| tail = 2
+--+--+--+--+--+

// mydeque.h
template <typename T>
class MyDeque {
    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:
    MyDeque(std::size_t s=10) : msize(s+1), head(0), tail(0) {
        tab = new T[s+1];
        assert( tab != nullptr );
    } // default constructor
    ~MyDeque() { delete [] tab; }
    MyDeque(const MyDeque& other); // copy constructor
    MyDeque(MyDeque&& other); // move constructor NIEOBOWIĄZKOWE
    // UWAGA Po przeniesieniu other.msize = 1, other.head = other.tail = 0.
    MyDeque& operator=(const MyDeque& other); // copy assignment operator, return *this
    MyDeque& operator=(MyDeque&& other); // move assignment operator, return *this NIEOBOWIĄZKOWE
    // UWAGA Po przeniesieniu other.msize = 1, other.head = other.tail = 0.
    bool empty() const { return head == tail; }
    bool full() const { return (tail + 1) % msize == head; }
    std::size_t size() const { return (tail - head + msize) % msize; }
    std::size_t max_size() const { return msize-1; }
    void push_front(const T& item); // dodanie na początek O(1)
    void push_front(T&& item); // dodanie na początek O(1) NIEOBOWIĄZKOWE
    void push_back(const T& item); // dodanie na koniec O(1)
    void push_back(T&& item); // dodanie na koniec O(1) NIEOBOWIĄZKOWE
    T& front() { return tab[head]; } // zwraca poczatek
    T& back() { return tab[(tail + msize -1) % msize]; } // zwraca koniec
    void pop_front(); // usuwa początek kolejki O(1)
    void pop_back(); // usuwa koniec kolejki O(1)
    void clear(); // czyszczenie listy z elementów
    void display();
    void display_reversed();
    // Operacje z indeksami. NIEOBOWIĄZKOWE
    T& operator[](std::size_t pos); // podstawienie L[pos]=item, odczyt L[pos]
    const T& operator[](std::size_t pos) const; // dostęp do obiektu const
    void erase(std::size_t pos);
    int index(const T& item); // jaki index na liście (-1 gdy nie ma)
    void insert(std::size_t pos, const T& item); // inserts item before pos
    void insert(std::size_t pos, T&& item); // inserts item before pos
};

template <typename T>
void MyDeque<T>::push_front(const T& item) {
    assert(!full());
    head = (head + msize -1) % msize;
    tab[head] = item;
}

template <typename T>
void MyDeque<T>::push_back(const T& item) {
    assert(!full());
    tab[tail] = item;
    tail = (tail + 1) % msize;
}

template <typename T>
void MyDeque<T>::display() {
    for (std::size_t i = head; i != tail; i=(i+1) % msize) {
        std::cout << tab[i] << " ";
    }
    std::cout << std::endl;
}

ZADANIE 6.2

Przygotować implementację realizującą ADT DEQUE na bazie listy powiązanej podwójnie. Wykorzystać klasę DoubleList lub std::list.

ZADANIE 6.3

Przygotować implementację realizującą ADT DEQUE na bazie std::vector jako tablicy cyklicznej.

AiSD (index)