Implement deque class using Linked Lists in C++

deque.h

#ifndef _DEQUE_H_ #define _DEQUE_H_

#include #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

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 

node2.template

#include // Provides assert #include // Provides NULL and size_t namespace main_savitch_6B { template void list_clear(node*& head_ptr) // Library facilities used: cstdlib { while (head_ptr != NULL) list_head_remove(head_ptr); } template void list_copy( const node* source_ptr, node*& head_ptr, node*& tail_ptr ) // Library facilities used: cstdlib { head_ptr = NULL; tail_ptr = NULL; // Handle the case of the empty list if (source_ptr == NULL) return; // Make the head node for the newly created list, and put data in it list_head_insert(head_ptr, source_ptr->data( )); tail_ptr = head_ptr; // Copy rest of the nodes one at a time, adding at the tail of new list source_ptr = source_ptr->link( ); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data( )); tail_ptr = tail_ptr->link( ); source_ptr = source_ptr->link( ); } } template void list_head_insert(node*& head_ptr, const Item& entry) { head_ptr = new node(entry, head_ptr); } template void list_head_remove(node*& head_ptr) { node *remove_ptr; remove_ptr = head_ptr; head_ptr = head_ptr->link( ); delete remove_ptr; } template void list_insert(node* previous_ptr, const Item& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); } template std::size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; std::size_t answer; answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; } template NodePtr list_locate(NodePtr head_ptr, SizeType position) // Library facilities used: cassert, cstdlib { NodePtr cursor; SizeType i; assert(0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); ++i) cursor = cursor->link( ); return cursor; } template void list_remove(node* previous_ptr) { node *remove_ptr; remove_ptr = previous_ptr->link( ); previous_ptr->set_link(remove_ptr->link( )); delete remove_ptr; } template NodePtr list_search(NodePtr head_ptr, const Item& target) // Library facilities used: cstdlib { NodePtr cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; } }