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" to reinforce linear data structure implementations. The needed code is below.

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

Answer:

#include <iostream>
#include <cstdlib>
using namespace std;
struct node
{
    int content;
    node *later;
    node *before;

}*top, *end;
class dqueue
{
    public:
        int top1, top2;
        void push();
        void remove();
        void show();
        dqueue()
        {
            top1 = 0;
            top2 = 0;
            top = NULL;
            end = NULL;
        }
};
int main()
{
    int choice;
    dqueue dl;
    while (1)
    {
     
        cout<<"Operations on Deque"<<endl;
      
        cout<<"1.push Element into the Deque"<<endl;
        cout<<"2.remove Element from the Deque"<<endl;
        cout<<"3.Traverse the Deque"<<endl;
        cout<<"4.Quit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        cout<<endl;
        switch(choice)
        {
        case 1:
            dl.push();
            break;
        case 2:
            dl.remove();
            break;
        case 3:
            dl.show();
            break;
        case 4:
            exit(1);
            break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;  
}
void dqueue::push()
{
    struct node *read;
    int ch, value;
    if (top1 + top2 >= 50)
    {
        cout<<"Dequeue Overflow"<<endl;
        return;
    }
    if (top1 + top2 == 0)
    {
        cout<<"Enter the value to be pushed: ";
        cin>>value;
        top = new (struct node);
        top->content = value;
        top->later = NULL;
        top->before = NULL;
        end = top;
        top1++;
        cout<<"Element pushed into empty deque"<<endl;
    }
    else
    {
        while (1)
        {
            cout<<endl;
            cout<<"1.push Element at first"<<endl;
            cout<<"2.push Element at last"<<endl;
            cout<<"3.Exit"<<endl;
            cout<<endl;
            cout<<"Enter Your Choice: ";
            cin>>ch;
            cout<<endl;
            switch(ch)
            {
            case 1:
                cout<<"Enter the value to be pushed: ";
                cin>>value;
                read = new (struct node);
                read->content = value;
                read->later = top;
                read->before = NULL;
                top->before = read;
                top = read;
                top1++;
                break;
            case 2:
                cout<<"Enter the value to be pushed: ";
                cin>>value;
                read = new (struct node);
                read->content = value;
                read->later = NULL;
                read->before = end;
                end->later = read;
                end = read;
                top2++;
                break;
            case 3:
                return;
                break;
            default:
                cout<<"Wrong Choice"<<endl;
            }
        }
    }
}
void dqueue::remove()
{
    if (top1 + top2 <= 0)
    {
        cout<<"Deque Underflow"<<endl;
        return;
    }
    int ch;
    while (1)
    {
        cout<<endl;
        cout<<"1.delete element at beginning"<<endl;
        cout<<"2.remove element at end "<<endl;
        cout<<"3.Exit"<<endl;
        cout<<endl;
        cout<<"Enter Your Choice: ";
        cin>>ch;
        cout<<endl;
        switch(ch)
        {
        case 1:
            top = top->later;
            top->before = NULL;
            top1--;
            break;
        case 2:
            end = end->before;
            end->later = NULL;
            top2--;
            break;
        case 3:
            return;
            break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
}
void dqueue::show()
{
    struct node *read;
    int ch;
    if (top1 + top2 <= 0)
    {
        cout<<"Deque Underflow"<<endl;
        return;
    }
    while (1)
    {
        cout<<endl;
        cout<<"1.show Deque from Beginning"<<endl;
        cout<<"2.show Deque from End"<<endl;
        cout<<"3.Exit"<<endl;
        cout<<endl;
        cout<<"Enter Your Choice: ";
        cin>>ch;
        cout<<endl;
        switch (ch)
        {
        case 1:
            read = top;
            cout<<"Deque from Beginning:"<<endl;
            while (read != NULL)
            {
                cout<<read->content<<" ";
                read = read->later;                     
            }
            cout<<endl;
            break;
        case 2:
            cout<<"Deque from End:"<<endl;
            read = end;
            while (read != NULL)
            {
                cout<<read->content<<" ";
                read = read->before;                    
            }
            read = end;
            cout<<endl;
            break;
        case 3:
            return;
            break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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