C++ implementation of a static deque class.

“deque.h” provided below

PROGRAMS:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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_tagnamespace 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_tnamespace 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;    }}