The goal of this assignment is to reinforce using linear dat

The goal of this assignment is to reinforce using linear data structures in C++. Specifically, the assignment is to create a dynamic implementation of a deque using the author\'s linked list implementation. The header file for the deque is deque.h.

deque.h file

http://pastebin.com/XeJxSF6r

node2.h

http://pastebin.com/GYVk2DiJ

Solution

Given below is the implementation file deque.template Also a simple test for the implementation is given in main.cpp Please use these 2 files along with your files - node2.h , node2.template, deque.h

To compile the main.cpp

use g++ main.cpp

deque.template

//postcondition: empty deque has been created
template <typename T>
deque<T>::deque()
{
count = 0;
first = last = NULL;
}

// postcondition: all resouroces allocated to the deque
// have been deallocated
template <typename T>
deque<T>::~deque()
{
list_clear(first);
}

// postcondition: newly created deque is a copy of dq
template <typename T>
deque<T>::deque(const deque<T>& dq)
{
first = last = NULL;
*this = dq;
}

// postcondition: current deque is a copy of dq
template <typename T>
deque<T>& deque<T>::operator = (const deque<T>& dq)
{
list_clear(first);
list_copy(dq.first, first, last);
count = dq.count;
return *this;
}

//precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
template <typename T>
T& deque<T>::front()
{
if(empty())
throw \"deque empty\";
return first->data();
}

// precondition: deque is not empty
// postcondition: copy of element at front of deque
// has been returned
template <typename T>
T deque<T>::front() const
{
if(empty())
throw \"deque empty\";
return first->data();

}

// precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
template <typename T>
T& deque<T>::back()
{
if(empty())
throw \"deque empty\";
return last->data();
}

// precondition: deque is not empty
// postcondition: copy of element at back of deque
// has been returned
template <typename T>
T deque<T>::back() const
{
if(empty())
throw \"deque empty\";
return last->data();
}

// postcondition: entry has been inserted at the front
// of the deque
template <typename T>
void deque<T>::push_front (const T& entry)
{
list_head_insert(first, entry);
if(last == NULL)
last = first;
count++;
}

// postcondition: entry has been inserted at the back
// of the deque
template <typename T>
void deque<T>::push_back (const T& entry)

{
if(empty())
push_front(entry);
else
{
list_insert(last, entry);
last = last->link();
count++;
}
}

// precondition: deque is not empty
// postcondition: element at front of deque has been removed
template <typename T>
void deque<T>::pop_front()
{
if(empty())
throw \"deque empty.\";

list_head_remove(first);
if(first == NULL)
last = NULL;
count--;

}

// precondition: deque is not empty
// postcondition: element at back of deque has been removed
template <typename T>
void deque<T>::pop_back()
{
if(empty())
throw \"deque empty.\";
if(size() == 1)
pop_front();
else
{
node<T>* prev = list_locate(first, size()-1);
list_remove(prev);
last = prev;
count--;
}

}

// postcondition: number of elements in deque has been returned
template <typename T>
std::size_t deque<T>::size() const
{
return count;
}

// postcondition: whether deque is empty has been returned
template <typename T>
bool deque<T>::empty() const
{
return count == 0;
}

// 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>
bool operator == (const deque<U>& dq1, const deque<U>& dq2)
{
if(dq1.size() == dq2.size())
{
node<U>* p = dq1.first, *q = dq2.first;
while(p != NULL)
{
if(p->data() != q->data())
return false;
p = p->link();
q = q->link();
}
return true;
}
else
return false;
}

// postcondition: dq has been display from front to rear on out
template <typename U>
std::ostream& operator<< (std::ostream& out, const deque<U>& dq)
{
node<U> *curr = dq.first;
while(curr != NULL)
{
out << curr->data() << \" \";
curr = curr->link();
}
return out;
}

main.cpp

#include \"deque.h\"
#include <cassert>
#include <iostream>
using namespace std;
int main()
{
deque<int> dq;

assert(dq.size() == 0);
  
dq.push_front(2);
assert(dq.front() == 2);
  
dq.push_front(4);
assert(dq.front() == 4);
  
dq.push_front(6);
assert(dq.front() == 6);
  
  
assert(dq.size() == 3);
  
cout << dq << endl;
  
dq.push_back(8);
assert(dq.back() == 8);
  
dq.push_back(10);
assert(dq.back() == 10);
assert(dq.size() == 5);
  
cout << dq << endl;
  
deque<int> dq2(dq);
assert(dq == dq2);
  
dq2.push_back(12);
assert(!(dq == dq2));
  
dq.pop_front();
assert(dq.front() == 4);
assert(dq.size() == 4);
dq.pop_front();
assert(dq.front() == 2);
assert(dq.size() == 3);
  
dq.pop_back();
assert(dq.back() == 8);
assert(dq.size() == 2);
dq.pop_back();
assert(dq.back() == 2);
assert(dq.front() == 2);
assert(dq.size() == 1);
assert(!dq.empty());
  
dq.pop_front();
assert(dq.size() == 0);
assert(dq.empty());
  
cout << \"all tests passed\" << endl;
  
}

output

6 4 2
6 4 2 8 10
all tests passed