Create a dynamic implementation of a deque using the author's linked list implementation.

deque.h

#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; deque(); ~deque(); deque(const deque& dq); deque& operator = (const deque& dq); T& front(); T front() const; T& back(); T back() const; void push_front (const T& entry); void push_back (const T& entry); void pop_front(); void pop_back(); size_type size() const; bool empty() const; template friend bool operator == (const deque& dq1, const deque& dq2);

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

node2.h

#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