Implement deque class using Linked Lists in C++ deque.h #ifndef _DEQUE_H_ #defin

Question

Implement deque class using Linked Lists in C++

deque.h

#ifndef _DEQUE_H_
#define _DEQUE_H_

#include <iostream>
#include <cstdlib>
#include <cassert>
#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

node2.template

Explanation / Answer

Please find the code below:

CODE:

You have not said anything about your code.

A working code is given below.

#include <iostream>
#include <cstdlib>
using namespace std;

// Node Declaration

struct node
{
int info;
node *next;
node *prev;

}*head, *tail;

class dqueue
{
public:
int top1, top2;
void display();
       void insert();
void del();
dqueue()
{
top1 = 0;
top2 = 0;
head = NULL;
tail = NULL;
}
};

// Insert Element in Doubly Ended Queue
void dqueue::insert()
{
struct node *temp;
int ch, value;
if (top1 + top2 >= 50)
{
cout<<"Dequeue Overflow"<<endl;
return;
}
if (top1 + top2 == 0)
{
cout<<"Enter the value to be inserted: ";
cin>>value;
head = new (struct node);
head->info = value;
head->next = NULL;
head->prev = NULL;
tail = head;
top1++;
cout<<"Element Inserted into empty deque"<<endl;
}
else
{
while (1)
{
cout<<endl;
cout<<"1.Insert Element at first"<<endl;
cout<<"2.Insert 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 inserted: ";
cin>>value;
temp = new (struct node);
temp->info = value;
temp->next = head;
temp->prev = NULL;
head->prev = temp;
head = temp;
top1++;
break;
case 2:
cout<<"Enter the value to be inserted: ";
cin>>value;
temp = new (struct node);
temp->info = value;
temp->next = NULL;
temp->prev = tail;
tail->next = temp;
tail = temp;
top2++;
break;
case 3:
return;
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
}
}

// Delete Element in Doubly Ended Queue
void dqueue::del()
{
if (top1 + top2 <= 0)
{
cout<<"Deque Underflow"<<endl;
return;
}
int ch;
while (1)
{
cout<<endl;
cout<<"1.Delete Element at first"<<endl;
cout<<"2.Delete Element at last"<<endl;
cout<<"3.Exit"<<endl;
cout<<endl;
cout<<"Enter Your Choice: ";
cin>>ch;
cout<<endl;
switch(ch)
{
case 1:
head = head->next;
head->prev = NULL;
top1--;
break;
case 2:
tail = tail->prev;
tail->next = NULL;
top2--;
break;
case 3:
return;
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
}

// Display Doubly Ended Queue
void dqueue::display()
{
struct node *temp;
int ch;
if (top1 + top2 <= 0)
{
cout<<"Deque Underflow"<<endl;
return;
}
while (1)
{
cout<<endl;
cout<<"1.Display Deque from Beginning"<<endl;
cout<<"2.Display Deque from End"<<endl;
cout<<"3.Exit"<<endl;
cout<<endl;
cout<<"Enter Your Choice: ";
cin>>ch;
cout<<endl;
switch (ch)
{
case 1:
temp = head;
cout<<"Deque from Beginning:"<<endl;
while (temp != NULL)
{
cout<<temp->info<<" ";
temp = temp->next;   
}
cout<<endl;
break;
case 2:
cout<<"Deque from End:"<<endl;
temp = tail;
while (temp != NULL)
{
cout<<temp->info<<" ";
temp = temp->prev;
}
temp = tail;
cout<<endl;
break;
case 3:
return;
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
}

int main()
{
int choice;
dqueue dl;
while (1)
{
cout<<" -------------"<<endl;
cout<<"Operations on Deque"<<endl;
cout<<" -------------"<<endl;
cout<<"1.Insert Element into the Deque"<<endl;
cout<<"2.Delete 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.insert();
break;
case 2:
dl.del();
break;
case 3:
dl.display();
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}

OUTPUT:

$ g++ deque.cpp
$ a.out
-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3

Deque Underflow

-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 2

Deque Underflow

-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 1

Enter the value to be inserted: 100
Element Inserted into empty deque

-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3


1.Display Deque from Beginning
2.Display Deque from End
3.Exit

Enter Your Choice: 1

Deque from Beginning:
100

1.Display Deque from Beginning
2.Display Deque from End
3.Exit

Enter Your Choice: 2

Deque from End:
100

1.Display Deque from Beginning
2.Display Deque from End
3.Exit

Enter Your Choice: 3


-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 1


1.Insert Element at first
2.Insert Element at last
3.Exit

Enter Your Choice: 1

Enter the value to be inserted: 200

1.Insert Element at first
2.Insert Element at last
3.Exit

Enter Your Choice: 2   

Enter the value to be inserted: 150

1.Insert Element at first
2.Insert Element at last
3.Exit

Enter Your Choice: 3


-------------
Operations on Deque

-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 4

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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