Create a dynamic implementation of a deque using the author\'s linked list imple

Question

Create a dynamic implementation of a deque using the author's linked list implementation. The header file for the deque is “deque.h”.

deque.h

#ifndef _DEQUE_H_
#define _DEQUE_H_

#include <iostream>
#include <cstdlib>
#include "node2.h"

using namespace main_savitch_6B;

template <typename T>
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<T>& dq);
  
// postcondition: current deque is a copy of dq
deque<T>& operator = (const deque<T>& 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 <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:
size_type count; // Total number of items in the queue
node<T>* first;
node<T>* last;
};

#include "deque.template"

#endif

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

node2.h

#ifndef MAIN_SAVITCH_NODE2_H
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib> // 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

Explanation / Answer

#include<conio.h>
#include<stdlib.h
#include<dos.h
#include <iostream.h>
#include<string.h>
#include<fstream.h>
using namespace std;

class Dequee
{
public:
DequeEmptyException()
{
cout << "Deque empty/n" <<
}
};

class Node
{
public:
int data;
Node* next;
Node* previous;
};

class Dequee
{
private:
Node* frnt;
Node* rear;
int count;

public:
Dequee()
{
frnt = NULL;
rear = NULL;
count = 0;
}
  
void InsertFrnt(int element)
{

Node* temp = new Node();
temp->data = element;
temp->next = NULL;
temp->prev = NULL;

if ( isEmpty() ) {
// Add the first element
front = rear = tmp;
}
else {

tmp->next = frnt;
frnt->prev = tmp;
frnt = tmp;
}

count++;
}

int RemoveFrnt()
{
if ( isEmpty() ) {
throw new DequeEmptyException();
}

int ret = front->data;

Node* tmp = frnt;
if ( frnt->next != NULL )
{
frnt = front->next;
frnt->prev = NULL;
}
else
{
frnt = NULL;
}
count--;
delete temp;

return ret;
}

void InsertBack(int element)
{

Node* temp = new Node();
tmp->data = element;
tmp->next = NULL;
tmp->prev = NULL;

if ( isEmpty() ) {
// Add the first element
front = rear = tmp;
}
else {
  
rear->next = temp;
temp->previous = rear;
rear = temp;
}

count++;
}

int RemoveBack()
{
if ( isEmpty() ) {
throw new DequeEmptyException();
}

int ret = rear->data;

Node* temp = rear;
if ( rear->previous != NULL )
{
rear = rear->previous;
rear->next = NULL;
}
else
{
rear = NULL;
}
count--;
delete temp;

return ret;
}
  
int Front()
{
if ( isEmpty() )
throw new DequeEmptyException();

return front->data;
}

int Back()
{
if ( isEmpty() )
throw new DequeEmptyException();

return rear->data;
}
  
int Size()
{
return count;
}

bool isEmpty()
{
return count == 0 ? true : false;
}
};

int main()
{

Deque q;
try {
if ( q.isEmpty() )
{
cout << "Deque is empty" << endl;
}

q.InsertBack(300);
q.InsertBack(400);
q.InsertBack(500);
cout << "Size of dequeue = " << q.Size() << endl;
cout << q.RemoveBack() << endl;
cout << q.RemoveBack() << endl;
cout << q.RemoveBack() << endl;
}
catch (...) {
cout << "Some exception happended" << endl;
}

  
try {
if ( q1.isEmpty() )
{
cout << "Deque is empty" << endl;
}

q1.InsertBack(300);
q1.InsertBack(400);
q1.InsertBack(500);
cout << "Size of dequeue = " << q1.Size() <<
cout << q1.RemoveFrnt() << endl;
cout << q1.RemoveFrnt() << endl;
cout << q1.RemoveFrnt() << endl;
}
catch (...) {
cout << "Some exception happended" << endl;
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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