The purpose of this task is to help reinforce linear data structure implementati
ID: 3805881 • Letter: T
Question
The purpose of this task is to help reinforce linear data structure implementations in C++. Specifically, the task is to construct a C++ implementation. The aim is to implement the deque class using "Arrays". The header file that we will use is deque.h.
#ifndef _DEQUE_H_
#define _DEQUE_H_
#include <iostream>
#include <cstdlib>
template <typename T>
class deque
{
public:
typedef std::size_t size_type;
static const size_type CAPACITY = 10;
//postcondition: empty deque has been created
deque();
//precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& front();
// precondition: deque is not empty
// postcondition: copy of element at front of deque
// has been returned
T front() const;
// precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& back();
// precondition: deque is not empty
// postcondition: copy of element at back of deque
// has been returned
T back() const;
// precondition: deque is not full
// postcondition: entry has been inserted at the front
// of the deque
void push_front (const T& entry);
// precondition: deque is not full
// postcondition: entry has been inserted at the back
// of the deque
void push_back (const T& entry);
// precondition: deque is not empty
// postcondition: element at front of deque has been removed
void pop_front();
// precondition: deque is not empty
// postcondition: element at back of deque has been removed
void pop_back();
// postcondition: number of elements in deque has been returned
size_type size() const;
// postcondition: whether deque is empty has been returned
bool empty() const;
// postcondition: whether deque is full has been returned
bool full() const;
// postcondition: returned whether 2 deques are equal - equal is defined
// as the deques have the same number of elements &
// corresponding elements are equal
template <typename U>
friend bool operator == (const deque<U>& dq1, const deque<U>& dq2);
// postcondition: dq has been display from front to rear on out
template <typename U>
friend std::ostream& operator<< (std::ostream& out, const deque<U>& dq);
private:
T data[CAPACITY]; // Circular array
size_type first; // Index of item at front of the queue
size_type last; // Index of item at rear of the queue
size_type count; // Total number of items in the queue
// postcondition: returned next index in array
size_type next_index(size_type i) const;
// postcondition: returned previous index in array
size_type prev_index (size_type i) const;
};
#include "deque.template"
#endif
Explanation / Answer
deque.h
#ifndef _DEQUE_H_
#define _DEQUE_H_
#include <iostream>
#include <cstdlib>
namespace LAB_07_ALUEBKE
{
template <typename T>
class deque
{
public:
typedef std::size_t size_type;
static const size_type CAPACITY = 10;
//postcondition: empty deque has been created
deque();
//precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& front();
// precondition: deque is not empty
// postcondition: copy of element at front of deque
// has been returned
T front() const;
// precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& back();
// precondition: deque is not empty
// postcondition: copy of element at back of deque
// has been returned
T back() const;
// precondition: deque is not full
// postcondition: entry has been inserted at the front
// of the deque
void push_front (const T& entry);
// precondition: deque is not full
// postcondition: entry has been inserted at the back
// of the deque
void push_back (const T& entry);
// precondition: deque is not empty
// postcondition: element at front of deque has been removed
void pop_front();
// precondition: deque is not empty
// postcondition: element at back of deque has been removed
void pop_back();
// postcondition: number of elements in deque has been returned
size_type size() const {return count;}
// postcondition: whether deque is empty has been returned
bool empty() const;
// postcondition: whether deque is full has been returned
bool full() const;
// postcondition: returned whether 2 deques are equal - equal is defined
// as the deques have the same number of elements &
// corresponding elements are equal
template <typename U>
friend bool operator == (const deque<U>& dq1, const deque<U>& dq2);
// postcondition: dq has been display from front to rear on out
template <typename U>
friend std::ostream& operator<< (std::ostream& out, const deque<U>& dq);
private:
T data[CAPACITY]; // Circular array
size_type first; // Index of item at front of the queue
size_type last; // Index of item at rear of the queue
size_type count; // Total number of items in the queue
// postcondition: returned next index in array
size_type next_index(size_type i) const;
// postcondition: returned previous index in array
size_type prev_index (size_type i) const;
};
}
#include "deque.template"
#endif
deque.template
#include <iostream>
#include <cstdlib>
#include <cassert>
#include "deque.h"
using namespace std;
namespace LAB_07_ALUEBKE
{
template <typename T>
deque<T>::deque()
{
count = 0;
first = 0;
last = 0;
}
template <typename T>
T& deque<T>::front()
{
assert(!empty());
return data[first];
}
template <typename T>
T deque<T>::front() const
{
assert(!empty());
return data[first];
}
template <typename T>
T& deque<T>::back()
{
assert(!empty());
return data[last];
}
template <typename T>
T deque<T>::back() const
{
assert(!empty());
return data[last];
}
template <typename T>
void deque<T>::push_front(const T& entry)
{
assert(!full());
if(empty())
{
data[0] = entry;
first = 0;
last = 0;
}
else if(first == 0)
{
first = 9;
data[first] = entry;
}
else
{
first--;
data[first] = entry;
}
count++;
}
template <typename T>
void deque<T>::push_back (const T& entry)
{
assert(!full());
if(empty())
{
data[0] = entry;
first = 0;
last = 0;
}
else if(last == 9)
{
last = 0;
data[last] = entry;
}
else
{
last++;
data[last] = entry;
}
count++;
}
template <typename T>
void deque<T>::pop_front ()
{
assert(!empty());
data[first] = 0;
first++;
count--;
if(first > 9)
{
first = 0;
}
}
template <typename T>
void deque<T>::pop_back ()
{
assert(!empty());
data[last] = 0;
last--;
count--;
if(last < 0)
{
last = 9;
}
}
template <typename T>
bool deque<T>::empty() const
{
if(count == 0)
{
return true;
}
else
{
return false;
}
}
template <typename T>
bool deque<T>::full() const
{
if(count == CAPACITY)
{
return true;
}
else
{
return false;
}
}
template <typename U>
bool operator == (const deque<U>& dq1, const deque<U>& dq2)
{
if(dq1.size() == dq2.size())
{
size_t loops = 0;
while( loops < dq1.size())
{
size_t i = dq1.first;
size_t j = dq2.first;
if( i > 9)
{
i = 0;
}
if( j > 9)
{
j = 0;
}
if(dq1.data[i] != dq2.data[j])
{
return false;
}
i++;
j++;
loops++;
}
return true;
}
else
{
return false;
}
}
template <typename U>
ostream& operator << (ostream& out, const deque<U>& dq)
{
for(size_t i = dq.first; i != (dq.last + 1); i++)
{
if( i > 9)
{
i = 0;
}
out << dq.data[i] << " ";
}
return out;
}
template <typename T>
typename deque<T>::size_type deque<T>::next_index (size_type i) const
{
if (i == 9)
{
i = 0;
return i;
}
else
{
i++;
return i;
}
}
template <typename T>
typename deque<T>::size_type deque<T>::prev_index (size_type i) const
{
if (i == 0)
{
i = 9;
return i;
}
else
{
i--;
return i;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.