The assignment is to construct a C++ implementation of a static deque class using deque.h". Basically, a deque is a double-ended queue that is a sequence container with dynamic sizes that can be expanded or contracted on both ends. The needed code is below.

deque.h

#ifndef _DEQUE_H_ #define _DEQUE_H_

#include #include

template class deque { public: typedef std::size_t size_type; static const size_type CAPACITY = 10; //postcondition: empty deque has been created deque(); //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; // precondition: deque is not full // postcondition: entry has been inserted at the front // of the deque void push_front (const T& entry); // precondition: deque is not full // 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: whether deque is full has been returned bool full() 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: T data[CAPACITY]; // Circular array size_type first; // Index of item at front of the queue size_type last; // Index of item at rear of the queue size_type count; // Total number of items in the queue

// postcondition: returned next index in array size_type next_index(size_type i) const; // postcondition: returned previous index in array size_type prev_index (size_type i) const; };

#include "deque.template"

#endif

------------------------------------------------------------------------------------------------------------

node2.h

#ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include // Provides size_t and NULL

namespace main_savitch_5 { class node { public: // TYPEDEF typedef double value_type; // CONSTRUCTOR node( const value_type& init_data = value_type( ), node* init_link = NULL ) { data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields: void set_data(const value_type& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data: value_type data( ) const { return data_field; }

// Two slightly different member functions to retreive // the current link: const node* link( ) const { return link_field; } node* link( ) { return link_field; } private: value_type data_field; node* link_field; };

// FUNCTIONS for the linked list toolkit std::size_t list_length(const node* head_ptr); void list_head_insert(node*& head_ptr, const node::value_type& entry); void list_insert(node* previous_ptr, const node::value_type& entry); node* list_search(node* head_ptr, const node::value_type& target); const node* list_search (const node* head_ptr, const node::value_type& target); node* list_locate(node* head_ptr, std::size_t position); const node* list_locate(const node* head_ptr, std::size_t position); void list_head_remove(node*& head_ptr); void list_remove(node* previous_ptr); void list_clear(node*& head_ptr); void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr); }

#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; } }