The purpose of this lab is to help reinforce linear data structure implementations in C++. Specifically, the lab is to construct a C++ implementation of a static deque class. Use the deque.h.

__________________________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;

//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____________________________________________

// FILE: node2.h (part of the namespace main_savitch_6B)

// PROVIDES: A template class for a node in a linked list, and list manipulation

// functions. The template parameter is the type of the data in each node.

// This file also defines a template class: node_iterator.

// The node_iterator is a forward iterators with two constructors:

// (1) A constructor (with a node* parameter) that attaches the iterator

// to the specified node in a linked list, and (2) a default constructor that

// creates a special iterator that marks the position that is beyond the end of a

// linked list. There is also a const_node_iterator for use with

// const node* .

//

// TYPEDEF for the node template class:

// Each node of the list contains a piece of data and a pointer to the

// next node. The type of the data (node::value_type) is the Item type

// from the template parameter. The type may be any of the built-in C++ classes

// (int, char, ...) or a class with a default constructor, an assignment

// operator, and a test for equality (x == y).

// NOTE:

// Many compilers require the use of the new keyword typename before using

// the expression node::value_type. Otherwise

// the compiler doesn't have enough information to realize that it is the

// name of a data type.

//

// CONSTRUCTOR for the node class:

// node(

// const Item& init_data = Item(),

// node* init_link = NULL

// )

// Postcondition: The node contains the specified data and link.

// NOTE: The default value for the init_data is obtained from the default

// constructor of the Item. In the ANSI/ISO standard, this notation

// is also allowed for the built-in types, providing a default value of

// zero. The init_link has a default value of NULL.

//

// NOTE about two versions of some functions:

// The data function returns a reference to the data field of a node and

// the link function returns a copy of the link field of a node.

// Each of these functions comes in two versions: a const version and a

// non-const version. If the function is activated by a const node, then the

// compiler choses the const version (and the return value is const).

// If the function is activated by a non-const node, then the compiler choses

// the non-const version (and the return value will be non-const).

// EXAMPLES:

// const node *c;

// c->link( ) activates the const version of link returning const node*

// c->data( ) activates the const version of data returning const Item&

// c->data( ) = 42; ... is forbidden

// node *p;

// p->link( ) activates the non-const version of link returning node*

// p->data( ) activates the non-const version of data returning Item&

// p->data( ) = 42; ... actually changes the data in p's node

//

// MEMBER FUNCTIONS for the node class:

// const Item& data( ) const <----- const version

// and

// Item& data( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is a reference to the data from this node.

//

// const node* link( ) const <----- const version

// and

// node* link( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is the link from this node.

//

// void set_data(const Item& new_data)

// Postcondition: The node now contains the specified new data.

//

// void set_link(node* new_link)

// Postcondition: The node now contains the specified new link.

//

// FUNCTIONS in the linked list toolkit:

// template

// void list_clear(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: All nodes of the list have been returned to the heap,

// and the head_ptr is now NULL.

//

// template

// void list_copy

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

// Precondition: source_ptr is the head pointer of a linked list.

// Postcondition: head_ptr and tail_ptr are the head and tail pointers for

// a new list that contains the same items as the list pointed to by

// source_ptr. The original list is unaltered.

//

// template

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

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: A new node containing the given entry has been added at

// the head of the linked list; head_ptr now points to the head of the new,

// longer linked list.

//

// template

// void list_head_remove(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list, with at

// least one node.

// Postcondition: The head node has been removed and returned to the heap;

// head_ptr is now the head pointer of the new, shorter linked list.

//

// template

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

// Precondition: previous_ptr points to a node in a linked list.

// Postcondition: A new node containing the given entry has been added

// after the node that previous_ptr points to.

//

// template

// size_t list_length(const node* head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The value returned is the number of nodes in the linked

// list.

//

// template

// NodePtr list_locate(NodePtr head_ptr, SizeType position)

// The NodePtr may be either node* or const node*

// Precondition: head_ptr is the head pointer of a linked list, and

// position > 0.

// Postcondition: The return value is a pointer that points to the node at

// the specified position in the list. (The head node is position 1, the

// next node is position 2, and so on). If there is no such position, then

// the null pointer is returned.

//

// template

// void list_remove(node* previous_ptr)

// Precondition: previous_ptr points to a node in a linked list, and this

// is not the tail node of the list.

// Postcondition: The node after previous_ptr has been removed from the

// linked list.

//

// template

// NodePtr list_search

// (NodePtr head_ptr, const Item& target)

// The NodePtr may be either node* or const node*

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The return value is a pointer that points to the first

// node containing the specified target in its data member. If there is no

// such node, the null pointer is returned.

//

// DYNAMIC MEMORY usage by the toolkit:

// If there is insufficient dynamic memory, then the following functions throw

// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

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

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