Programming and data structure


Implement an unbounded double-ended Queue (using the single or double-linked list) as a template structure (aimed at storing values of any type), and the methods operating on this structure (not more than listed below; it is allowed to omit these which are not used in the program one submits):

the default constructor,

the destructor,

the copy-constructor,

the comparison operator==,

push_front – adding a value to the queue as the first,

pop_front – removig the first value from the queue or throwing an empty queue exception,

push_back – adding a value to the queue as the last,

pop_back – removing the last value from the queue or throwing an empty queue exception,

removeGreater – removing from the queue all the values greater than the one given as the parameter,

front – returning the first value or throwing an empty queue exception,

back – returning the last value or throwing an empty queue exception,

size – returning the number of items in the queue,

clear – removing all the items from the queue,

print – printing all the items from the queue.

here is the code that I have implemented. please help me verify if it's wrong or correct. I am really confused now


#include <iostream.h>
#include<stdio.h>
using namespace std;

// Node of a doubly-linked list
struct Node
{
int data;
Node *prev, *next;
// Function to get a new node
static Node* getnode(int data)
{

Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = newNode->next = NULL;
return newNode;
}
};

// A structure to represent a deque
class Deque
{
Node* front;
Node* rear;
Node* temp;
int Size;

public:
//default constructor
Deque()
{
front = rear = NULL;
Size = 0;
}
//destructor
~Deque()
{
cout<<"Destructor Called"<<endl;
}

// Operations on Deque
void Push_Front(int data);
void Push_Back(int data);
void Pop_Front();
void Pop_Back();
int Front();
int Back();
int size();
bool isEmpty();
void Clear();
void Display();
};

// Function to check whether deque
// is empty or not
void Deque::Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
bool Deque::isEmpty()
{
return (front == NULL);
}

// Function to return the number of
// elements in the deque
int Deque::size()
{
return Size;
}

// Function to insert an element
// at the front end
void Deque::Push_Front(int data)
{
Node* newNode = Node::getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == NULL)
cout << "OverFlow\n";
else
{
// If deque is empty
if (front == NULL)
rear = front = newNode;

// Inserts node at the front end
else
{
newNode->next = front;
front->prev = newNode;
front = newNode;
}

// Increments count of elements by 1
Size++;
}
}

// Function to insert an element
// at the rear end
void Deque::Push_Back(int data)
{
Node* newNode = Node::getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == NULL)
cout << "OverFlow\n";
else
{
// If deque is empty
if (rear == NULL)
front = rear = newNode;

// Inserts node at the rear end
else
{
newNode->prev = rear;
rear->next = newNode;
rear = newNode;
}

Size++;
}
}

// Function to delete the element
// from the front end
void Deque::Pop_Front()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
cout << "UnderFlow\n";

// Deletes the node from the front end and makes
// the adjustment in the links
else
{
Node* temp = front;
front = front->next;

// If only one element was present
if (front == NULL)
rear = NULL;
else
front->prev = NULL;
free(temp);

// Decrements count of elements by 1
Size--;
}
}

// Function to delete the element
// from the rear end
void Deque::Pop_Back()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
cout << "UnderFlow\n";

// Deletes the node from the rear end and makes
// the adjustment in the links
else
{
Node* temp = rear;
rear = rear->prev;

// If only one element was present
if (rear == NULL)
front = NULL;
else
rear->next = NULL;
free(temp);

// Decrements count of elements by 1
Size--;
}
}

// Function to return the element
// at the front end
int Deque::Front()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return front->data;
}

// Function to return the element
// at the rear end
int Deque::Back()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return rear->data;
}

// Function to delete all the elements
// from Deque
void Deque::Clear()
{
rear = NULL;
while (front != NULL)
{
Node* temp = front;
front = front->next;
free(temp);
}
Size = 0;
}

// Driver program to test above
int main()
{
Deque dq;
int choice;
do{
cout<<"Enter Your Choice";
cout<<"\n0. For printing All element in Queue ....";
cout<<"\n1.For Insert element at rear ... ";
cout<<"\n2.For get element at rear ... ";
cout<<"\n3.For Delete element at rear ... ";
cout<<"\n4.For Insert element at Front ... ";
cout<<"\n5.For get element at Front ... ";
cout<<"\n6.For Delete element at front ... ";
cout<<"\n7.For to check if Queue is Empty ... ";
cout<<"\n8.For get Size of Queue ... ";
cout<<"\n9.For Delete/erase all element in queue ... ";
cout<<"\n10. For to Exit...";
cin>>choice;
switch(choice)
{
case 1:
int ele;
cout<<"\nEnter element to insert at Rear";
cin>>ele;

dq.Push_Back(ele);
cout<<"\n"<<ele<<" inserted"<<endl;
break;
case 2:

cout << "\nRear end element: "
<< dq.Back() << endl;
break;
case 3:
dq.Pop_Back();
cout << "\nAfter deleting rear element new rear"
<< " is: " << dq.Back() << endl;
break;
case 4:
int elefr;
cout<<"Enter element to insert at Front";
cin>>elefr;
cout << "Inserting element" <<elefr<<" at front end \n";
dq.Push_Front(elefr);
break;
case 5:

cout << "Front end element: "
<< dq.Front() << endl;
break;
case 6:
dq.Pop_Front();
cout << "After deleting front element new "
<< "front is: " << dq.Front() << endl;
break;
case 7:
bool a = dq.isEmpty();
cout<<a<<endl;
break;
case 8:
cout << "Number of elements in Queue: "
<< dq.size() << endl;
break;

case 9:
dq.Clear();
cout<<"\n After Queue Erase = ";
cout<<"Queue is "<<dq.Front()<<endl;
case 0:
dq.Display();
break;
default:
cout<<"Wrong Option please select 1 to 9"<<endl;
}}while(choice!=10);
return 0;
}
Last edited on
I did not have time to read your code closely. However, based on a quick skim and the question you asked, let me give you a couple of strong suggestions.

1. When posting code here, please use code tags. [ code] your code here [ /code] (without the spaces). Enter these tags, and then paste your code between them. They will preserve indentation and make your code easier to read and comment on.

2. Start very small. Start with the default constructor and the print function. Make sure you can create an empty list and then print it out. Then add the push_back function and see if you can add a couple element and print them out. Then add the push_front function, etc.

Don't try to do everything at once. Get one piece working before you add the next. Then you won't be as confused.

Edit: Do the menu last. Make sure everything works according to a "script" before opening it up to user interaction.
Last edited on
Topic archived. No new replies allowed.