can someone explain the deque to me ?? C++ #pragma once // TODO: delete the foll
ID: 3687311 • Letter: C
Question
can someone explain the deque to me ??
C++
#pragma once
// TODO: delete the following #include
#include <deque>
const int B_NODE_CAPACITY = 16;
// TODO: create a template class called BNode that represents a
// doubly-linked node holding a fixed-capacity array of
// B_NODE_CAPACITY elements.
template <typename Element>
class BList {
public:
// These two statements tell the compiler to delete the the copy and
// assignment constructors. If you get an error at these lines, you are
// attempting to copy a list, so don't do that! (because the destructor
// will double delete your nodes)!
BList(const BList&) = delete;
BList& operator=(const BList&) = delete;
BList() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
}
~BList() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
}
bool is_empty() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
return deque_.empty();
}
int size() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
return deque_.size();
}
Element front() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_nonempty();
return deque_.front();
}
Element back() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_nonempty();
return deque_.back();
}
void add_front(Element e) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
deque_.push_front(e);
}
void add_back(Element e) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
deque_.push_back(e);
}
void remove_front() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_nonempty();
deque_.pop_front();
}
void remove_back() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_nonempty();
deque_.pop_back();
}
Element get(int index) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_index(index);
return deque_.at(index);
}
void set(int index, Element e) {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
check_index(index);
deque_.at(index) = e;
}
void clear() {
// TODO: re-implement this function to operate on BNode objects
// instead of just using std::deque
deque_.clear();
}
private:
// TODO: change this from a std::deque to head and tail pointers
// into a doubly-linked list of BNode objects.
std::deque<Element> deque_;
void check_nonempty() {
assert(!deque_.empty());
}
void check_index(int index) {
assert(index >= 0 && index < size());
}
};
Explanation / Answer
Answer:
Note: code is modified as per the method declarations provided. TODO parts are implemented
Code:
template <typename Element>
class BList
{
public:
BList(const BList&) = delete;
BList& operator=(const BList&) = delete;
BList()
{
_header = new BNode<Element>(NULL, Element(), NULL);
_trailer = new BNode<Element>(_header, Element(), NULL);
_header->set_next(_trailer);
_size = 0;
}
~BList() {
clear();
delete _header;
delete _trailer;
}
bool is_empty() {
return (_header->next() == _trailer);
}
int size() {
return _size;
//return _deque.size();
}
Element front() throw(UnderflowException)
{
check_nonempty();
return _header->next()->get_frontElement();
}
Element back() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
return _trailer->prev()->get_backElement();
}
void add_front(Element e) {
if ((_size == B_NODE_CAPACITY) || (_size == 0)) {
add_before(_header->next(), e);
}
else
{
for (int i = 0; i < B_NODE_CAPACITY; i++) {
if (_header->next()->get_element(i) == 0)
{
_header->next()->set_element(i, e);
}
}
}
_size++;
}
void add_back(Element e) {
if ((_size == B_NODE_CAPACITY) || (_size == 0)) {
add_before(_trailer, e);
}
else {
for (int i = 0; i < B_NODE_CAPACITY; i++) {
if (_trailer->prev()->get_element(i) == 0)
{
_trailer->prev()->set_element( i, e);
}
}
}
_size++;
}
void remove_front() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
remove(_header->next());
_size--;
}
void remove_back() throw(UnderflowException) {
if (is_empty())
throw UnderflowException();
remove(_trailer->prev());
_size--;
}
Element get(int index) throw(IndexException) {
check_index(index);
return _elements->get_element(index);
}
void set(int index, ELEMENT e) throw(IndexException) {
check_index(index);
_elements->set_element(index, e);
}
void clear() {
while (!is_empty())
remove_front();
}
private:
std::deque<Element> deque_;
void check_nonempty()
{
assert(!deque_.empty());
}
void check_index(int index)
{
assert(index >= 0 && index < size());
}
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.