#ifndef MAIN_SAVITCH_NODE2_H

#define MAIN_SAVITCH_NODE2_H

#include // Provides NULL and size_t

#include // Provides iterator and forward_iterator_tag

namespace main_savitch_6B

{

template

class node

{

public:

// TYPEDEF

typedef Item value_type;

// CONSTRUCTOR

node(const Item& init_data=Item( ), node* init_link=NULL)

{ data_field = init_data; link_field = init_link; }

// MODIFICATION MEMBER FUNCTIONS

Item& data( ) { return data_field; }

node* link( ) { return link_field; }

void set_data(const Item& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// CONST MEMBER FUNCTIONS

const Item& data( ) const { return data_field; }

const node* link( ) const { return link_field; }

private:

Item data_field;

node *link_field;

};

// FUNCTIONS to manipulate a linked list:

template

void list_clear(node*& head_ptr);

template

void list_copy

(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

template

void list_head_insert(node*& head_ptr, const Item& entry);

template

void list_head_remove(node*& head_ptr);

template

void list_insert(node* previous_ptr, const Item& entry);

template

std::size_t list_length(const node* head_ptr);

template

NodePtr list_locate(NodePtr head_ptr, SizeType position);

template

void list_remove(node* previous_ptr);

template

NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list

// A node_iterator of can change the underlying linked list through the

// * operator, so it may not be used with a const node. The

// node_const_iterator cannot change the underlying linked list

// through the * operator, so it may be used with a const node.

// WARNING:

// This classes use std::iterator as its base class;

// Older compilers that do not support the std::iterator class can

// delete everything after the word iterator in the second line:

template

class node_iterator

: public std::iterator

{

public:

node_iterator(node* initial = NULL)

{ current = initial; }

Item& operator *( ) const

{ return current->data( ); }

node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

node_iterator operator ++(int) // Postfix ++

{

node_iterator original(current);

current = current->link( );

return original;

}

bool operator ==(const node_iterator other) const

{ return current == other.current; }

bool operator !=(const node_iterator other) const

{ return current != other.current; }

private:

node* current;

};

template

class const_node_iterator

: public std::iterator

{

public:

const_node_iterator(const node* initial = NULL)

{ current = initial; }

const Item& operator *( ) const

{ return current->data( ); }

const_node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

const_node_iterator operator ++(int) // Postfix ++

{

const_node_iterator original(current);

current = current->link( );

return original;

}

bool operator ==(const const_node_iterator other) const

{ return current == other.current; }

bool operator !=(const const_node_iterator other) const

{ return current != other.current; }

private:

const node* current;

};

}

#include "node2.template"

#endif

#ifndef _DEQUE_H_ #define _DEQUE_H_

#include #include #include "node2.h"

using namespace main_savitch_6B;

template class deque { public: typedef std::size_t size_type; //postcondition: empty deque has been created deque(); // postcondition: all resouroces allocated to the deque // have been deallocated ~deque(); // postcondition: newly created deque is a copy of dq deque(const deque& dq); // postcondition: current deque is a copy of dq deque& operator = (const deque& dq); //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; // postcondition: entry has been inserted at the front // of the deque void push_front (const T& entry); // 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: returned whether 2 deques are equal - equal is defined // as the deques have the same number of elements & // corresponding elements are equal template friend bool operator == (const deque& dq1, const deque& dq2);

// postcondition: dq has been display from front to rear on out template friend std::ostream& operator<< (std::ostream& out, const deque& dq);

private: size_type count; // Total number of items in the queue node* first; node* last; };

#include "deque.template"

#endif

Using the above node header and dequeue header, I need to construct a dequeue class.