construct a C++ implementation of a static deque class. needs to be an array imp

Question

construct a C++ implementation of a static deque class. needs to be an array implementation

template <typename T>

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 <typename U>

friend bool operator == (const deque<U>& dq1, const deque<U>& dq2);

// postcondition: dq has been display from front to rear on out

template <typename U>

friend std::ostream& operator<< (std::ostream& out, const deque<U>& 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;

};

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.