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).
// 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
int 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[](int pos); // podstawienie L[pos]=item, odczyt L[pos]
const T& operator[](int pos) const; // dostęp do obiektu const
void erase(int pos);
int index(const T& item); // jaki index na liście (-1 gdy nie ma)
void insert(int pos, const T& item); // inserts item before pos
void insert(int 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;
int msize; // największa możliwa liczba elementów plus jeden
int head; // pierwszy do pobrania
int tail; // pierwsza wolna pozycja
public:
MyDeque(int 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; }
int size() const { return (tail - head + msize) % msize; }
int 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[](int pos); // podstawienie L[pos]=item, odczyt L[pos]
const T& operator[](int pos) const; // dostęp do obiektu const
void erase(int pos);
int index(const T& item); // jaki index na liście (-1 gdy nie ma)
void insert(int pos, const T& item); // inserts item before pos
void insert(int 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 (int 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 jako tablicy cyklicznej.