OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.
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:
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.
};
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;
}
Przygotować implementację realizującą ADT DEQUE na bazie listy powiązanej podwójnie. Wykorzystać klasę DoubleList lub std::list.
Przygotować implementację realizującą ADT DEQUE na bazie std::vector lub std::array jako tablicy cyklicznej.