Question

A deque (pronounced deck) is an ordered set of items from which items may be deleted at either end and into which items may be inserted at either end. Call the two ends left and right. This is an access-restricted structure since no insertions or deletions can happen other than at the ends. Implement a deque as a doubly-linked circular list with a header. Write InsertRight and DeleteLeft.

Answer 1

code:

#include <iostream>
using namespace std;

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

class Deque
{
private:
Node* front;
Node* rear;
int count;

public:
Deque()
{
front = NULL;
  
  
rear = NULL;
  
       count = 0;
}
bool isEmpty()
{
if(count == 0)
       return true;
       else
return false;
}
int DeleteLeft()
{
if ( isEmpty() ) {
cout<<"deque is empty... can't delete'";
return -1;
}

int ret = front->data;

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

return ret;
}

void InsertRight(int element)
{
Node* tmp = new Node();
tmp->data = element;
tmp->next = NULL;
tmp->prev = NULL;

if ( isEmpty() ) {
front = rear = tmp;
}
else {
rear->next = tmp;
tmp->prev = rear;
rear = tmp;
}

count++;
}

  
};

int main()
{
Deque q;
if ( q.isEmpty() )
{
cout << "Deque is empty" << endl;
}
q.InsertRight(100);
q.InsertRight(200);
q.InsertRight(300);

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

q1.InsertRight(100);
q1.InsertRight(200);
q1.InsertRight(300);

cout << q1.DeleteLeft() << endl;
cout << q1.DeleteLeft() << endl;
cout << q1.DeleteLeft() << endl;

}