The Standard Library provides stack and queue classes (std::stack and std::queue), but they are actually adapters (a kind of wrapper) for the Standard Librarys deque class (std::deque). Deques allow you to add items or remove them from either end of the deque (e.g., push_back, push_front, pop_back, and pop_front). Most Standard Library implementations of std::deque use two back-to-back vectors, a fronthalf vector that you call push_back on when you need to push to the front of the deque, and a backhalf vector that you call push_back on when you need to push to the back of the queue. The logic needs some adjusting if pop_back is called when the backhalf vector is empty, or if pop_front is called when the fronthalf vector is empty. In those cases, you will want to re-balance the values between the two vectors, making sure you keep the queue items in order - move half the values from fronthalf to backhalf, or vice-versa. It will take a little time to get this part to work correctly. Do not expect it to take 5-10 minutes. You are given a partial implementation of a mini-deque class. minideque is a templated class that holds the deque. Unlike the actual std::deque class, minideque will NOT have the iterator classes (iterator, const_iterator, reverse_iterator, and const_reverse_iterator). This means you will also NOT have to provide the iterator-based functions: erase, begin and end. For this project, you should use the std::vector class from the C++ standard library. Complete the implementation of class minideque, adding public/private member variables and functions as needed. Your code is tested in the provided main.cpp // minideque.h // minidequeproject // #ifndef minideque_h #define minideque_h #include #include #include #include #include template class minideque { private: std::vector fronthalf_; std::vector backhalf_; public: minideque() = default; // do not change, C++ defaults are ok minideque(const minideque& other) = default; // rule of three minideque& operator=(const minideque& other) = default; ~minideque() = default; size_t size() const; // TODO size_t fronthalfsize() const; // TODO size_t backhalfsize() const; // TODO bool empty() const; // TODO // balance queue across both vectors if pop_front/back is requested on an empty vector // e.g., minideque has this: | ABCDEFG // after pop_front BCD | EFG (A discarded) // symmetric logic for converse case: ABCDEFG | ===> ABC | DEF (G discarded) after pop_back void pop_front(); // TODO void pop_back(); // TODO void push_front(const T& value); // TODO void push_back(const T& value); // TODO const T& front() const; // TODO const T& back() const; // TODO T& front(); // TODO T& back(); // TODO const T& operator[](size_t index) const; // TODO T& operator[](size_t index); // TODO void clear(); // TODO friend std::ostream& operator<<(std::ostream& os, const minideque& dq) { // do not change if (dq.empty()) { return os << "minideque is empty"; } dq.printFronthalf(os); os << "| "; dq.printBackhalf(os); os << ", front:" << dq.front() << ", back:" << dq.back() << ", size:" << dq.size(); return os; } void printFronthalf(std::ostream& os=std::cout) const { // do not change if (empty()) { std::cout << "fronthalf vector is empty"; } for (typename std::vector::const_reverse_iterator crit = fronthalf_.crbegin(); crit != fronthalf_.crend(); ++crit) { os << *crit << " "; } } void printBackhalf(std::ostream& os=std::cout) const { // do not change if (empty()) { os << "backhalf vector is empty"; } for (typename std::vector::const_iterator cit = backhalf_.cbegin(); cit != backhalf_.cend(); ++cit) { os << *cit << " "; } } }; #endif /* minideque_h */ // minideque.h // minidequeproject // #ifndef minideque_h #define minideque_h #include #include #include #include #include template class minideque { private: std::vector fronthalf_; std::vector backhalf_; public: minideque() = default; // do not change, C++ defaults are ok minideque(const minideque& other) = default; // rule of three minideque& operator=(const minideque& other) = default; ~minideque() = default; size_t size() const; // TODO size_t fronthalfsize() const; // TODO size_t backhalfsize() const; // TODO bool empty() const; // TODO // balance queue across both vectors if pop_front/back is requested on an empty vector // e.g., minideque has this: | ABCDEFG // after pop_front BCD | EFG (A discarded) // symmetric logic for converse case: ABCDEFG | ===> ABC | DEF (G discarded) after pop_back void pop_front(); // TODO void pop_back(); // TODO void push_front(const T& value); // TODO void push_back(const T& value); // TODO const T& front() const; // TODO const T& back() const; // TODO T& front(); // TODO T& back(); // TODO const T& operator[](size_t index) const; // TODO T& operator[](size_t index); // TODO void clear(); // TODO friend std::ostream& operator<<(std::ostream& os, const minideque& dq) { // do not change if (dq.empty()) { return os << "minideque is empty"; } dq.printFronthalf(os); os << "| "; dq.printBackhalf(os); os << ", front:" << dq.front() << ", back:" << dq.back() << ", size:" << dq.size(); return os; } void printFronthalf(std::ostream& os=std::cout) const { // do not change if (empty()) { std::cout << "fronthalf vector is empty"; } for (typename std::vector::const_reverse_iterator crit = fronthalf_.crbegin(); crit != fronthalf_.crend(); ++crit) { os << *crit << " "; } } void printBackhalf(std::ostream& os=std::cout) const { // do not change if (empty()) { os << "backhalf vector is empty"; } for (typename std::vector::const_iterator cit = backhalf_.cbegin(); cit != backhalf_.cend(); ++cit) { os << *cit << " "; } } }; #endif /* minideque_h */