I am able to compile my code on a Linux box using g++ and run the driver just fine. When compiling and running the driver on my Windows machine I encounter a read access violation error with the ptr->next statement, in the size() method. (Assuming there is only one node) While debugging I can step through the while statements once as intended and on the second pass it continues through the ptr != nullptr even if there is no node.
This error occurs when adding nodes and the list size == 1.
I have been looking through all the statements and cant seem to find where I went wrong. Any information on this is appreciated!
Header
#ifndef DEQUE_H
#define DEQUE_H
#include <iostream>
using namespace std;
template <class Object>
class Deque {
public:
Deque( ); // the constructor
Deque( const Deque &rhs ); // the copy constructor
~Deque( ); // the destructor
bool isEmpty( ) const; // checks if a deque is empty.
int size( ) const; // retrieves # deque nodes
const Object &getFront( ) const; // retrieve the front node
const Object &getBack( ) const; // retrieve the tail node
void clear( ); // clean up all deque entries.
void addFront( const Object &obj ); // add a new node to the front
void addBack( const Object &obj ); // add a new node to the tail
Object removeFront( ); // remove the front node
Object removeBack( ); // remove the tail node
const Deque &operator=( const Deque &rhs ); // assignment
private:
struct DequeNode { // a deque node
Object item;
DequeNode *next;
DequeNode *prev;
};
DequeNode *front;
DequeNode *back;
};
#include "deque.cpp.h"
#endif
CPP
template <class Object>
Deque<Object>::Deque( ) { // the constructor
front = back = NULL;
}
template <class Object>
Deque<Object>::Deque( const Deque &rhs ) { // the copy constructor
front = back = NULL;
*this = rhs;
}
template <class Object>
Deque<Object>::~Deque( ) { // the destructor
clear( );
}
template <class Object>
bool Deque<Object>::isEmpty( ) const { // check if a deque is empty
return front == NULL;
}
template <class Object>
int Deque<Object>::size( ) const { // retrieves # deque nodes
int length = 0;
DequeNode* ptr = front;
while (ptr != nullptr) {
length++;
ptr = ptr->next;
}
return length;
}
template <class Object>
const Object &Deque<Object>::getFront( ) const { // retrieve the front node
if ( isEmpty( ) )
throw "empty queue";
return front->item;
}
template <class Object>
const Object &Deque<Object>::getBack( ) const { // retrieve the tail node
if ( isEmpty( ) )
throw "empty queue";
return back->item;
}
template <class Object>
void Deque<Object>::clear( ) { // clean up all entries.
while ( !isEmpty( ) ) // dequeue till the queue gets empty.
removeFront( );
}
template <class Object>
void Deque<Object>::addFront( const Object &obj ) {// add a new node to front
// Implement the function body.
DequeNode* newNode = new DequeNode;
newNode->item = obj;
// if no nodes, new node is front and back
if (isEmpty()){
front = back = newNode;
}
// if one node, new front and back are established
else if (size() == 1){
back->prev = newNode;
front = newNode;
front->next = back;
}
// add to front and shift right
else {
DequeNode* oldFront = front;
front->prev = newNode;
front = newNode;
front->next = oldFront;
}
}
template <class Object>
void Deque<Object>::addBack( const Object &obj ) { // add a new node to tail
// Implement the function body.
DequeNode* newNode = new DequeNode;
newNode->item = obj;
// if no nodes, new node is front and back
if (isEmpty()){
front = back = newNode;
}
// if one node, new front and back are established
else if (size() == 1){
front->next = newNode;
back = newNode;
back->prev = front;
}
// add to back and shift left
else {
DequeNode* oldBack = back;
back->next = newNode;
back = newNode;
back->prev = oldBack;
}
}
template <class Object>
Object Deque<Object>::removeFront( ) { // remove the front node
// Implement the function body.
if (isEmpty())
throw "empty queue";
// if only one node, return item, Deque is now NULL.
else if (size() == 1){
DequeNode* remove = front;
Object result = remove->item;
front = back = NULL;
delete remove;
remove = NULL;
return result;
}
// remove front node, shift right
else {
Object result = front->item;
DequeNode* remove = front;
front = front->next;
front->prev = NULL;
delete remove;
remove = NULL;
return result;
}
}
template <class Object>
Object Deque<Object>::removeBack( ) { // remove the tail node
// Implement the function body.
if (isEmpty())
throw "empty queue";
// if only one node, return item, Deque is now NULL.
else if (size() == 1){
DequeNode* remove = back;
Object result = remove->item;
front = back = NULL;
delete remove;
remove = NULL;
return result;
}
// remove back node, shift left
else {
Object result = back->item;
DequeNode* remove = back;
back = back->prev;
back->next = NULL;
delete remove;
remove = NULL;
return result;
}
}
template <class Object>
const Deque<Object> &Deque<Object>::operator=( const Deque &rhs ) { // assign
if ( this != &rhs ) { // avoid self assignment
clear( );
for ( DequeNode *rptr = rhs.front; rptr != NULL; rptr = rptr->next )
addBack( rptr->item );
}
return *this;
}
Driver
#include <iostream>
#include "deque.h"
using namespace std;
int main( ) {
Deque<int> deque1;
int item;
for ( int j = 0; j < 5; j++ )
deque1.addBack( j );
for ( int j = 5; j < 10; j++ )
deque1.addFront( j );
Deque<int> deque2 = deque1;
deque2.addBack( 10 );
cout << "deque1: " << endl;
while ( !deque1.isEmpty( ) )
cout << deque1.removeFront( ) << endl;
cout << "deque2: " << endl;
while ( !deque2.isEmpty( ) )
cout << deque2.removeBack( ) << endl;
}
