The assignment is to construct a C++ implementation of a static deque class usin

Question

The assignment is to construct a C++ implementation of a static deque class using “deque.h". 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;
}
}

Explanation / Answer

#include <iostream.h>

using namespace std;
#define SIZE 5

class dequeue
{

int input[10],end_front,end_rear,incrementer;

public:
dequeue();
void include_first(int);
void include_second(int);
void remove_front();
void remove_rear_end();
void show();
};

dequeue::dequeue()
{
end_front=-1;
end_rear=-1;
incrementer=0;
}

void dequeue::include_first(int value)
{
if(end_front==-1)
{
end_front++;
end_rear++;
input[end_rear]=value;
incrementer++;
}
else if(end_rear>=SIZE-1)
{
cout<<" Insertion is not possible,overflow!!!!";
}
else
{
for(int i=incrementer;i>=0;i--)
{
input[i]=input[i-1];
}
input[i]=value;
incrementer++;
end_rear++;
}
}

void dequeue::include_second(int value)
{

if(end_front==-1)
{
end_front++;
end_rear++;
input[end_rear]=value;
incrementer++;
}
else if(end_rear>=SIZE-1)
{
cout<<" Insertion is not possible,overflow!!!";
return;
}
else
{
input[++end_rear]=value;
}

}

void dequeue::show()
{

for(int i=end_front;i<=end_rear;i++)
{
cout<   }
}

void dequeue::remove_front()
{
if(end_front==-1)
{
cout<<"Deletion is not possible:: Dequeue is empty";
return;
}
else
{
if(end_front==end_rear)
{
end_front=end_rear=-1;
return;
}
cout<<"The deleted element is "<
end_front=end_front+1;
}

}

void dequeue::remove_rear_end()
{
if(end_front==-1)
{
cout<<"Deletion is not possible:Dequeue is empty";
return;
}
else
{
if(end_front==end_rear)
{
end_front=end_rear=-1;
}
cout<<"The deleted element is "<< input[end_rear];
end_rear=end_rear-1;
}

}

void main()
{
int c,value;
dequeue d1;
clrscr();
do
{
cout<<" ****DEQUEUE OPERATION**** ";
cout<<" 1-Insert at beginning";
cout<<" 2-Insert at end";
cout<<" 3_show";
cout<<" 4_Deletion from end_front";
cout<<" 5-Deletion from end_rear";
cout<<" 6_Exit";
cout<<" Enter your choice<1-4>:";
cin>>c;

switch(c)
{
case 1:
cout<<"Enter the element to be inserted:";
cin>>value;
d1.include_first(value);
break;

case 2:
cout<<"Enter the element to be inserted:";
cin>>value;
d1.include_second(value);
break;

case 3:
d1.show();
break;

case 4:
d1.remove_front();
break;
case 5:
d1.remove_rear_end();
break;

case 6:
exit(1);
break;

default:
cout<<"Invalid choice";
break;
}

}while(c!=7);
getch();

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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