C++ Create a abstract data type. Do not use any existing containers, such as the

ID: 3672884 • Letter: C

Question

C++

Create a abstract data type. Do not use any existing containers, such as the STL. Use a doubly-linked circular structure to store the values and links. Data will be positive integers. There will be no NULL pointers. Every NEXT pointer will point to a QueueNode as will every PREV pointer. Create a new node when the queue is full. As you take data out you will NOT remove the node. Use a sentinel value of -1 to indicate a node is empty.

You will need a QueueNode. You can use a struct for this, as each node will not have any associated functions. It will have members for data, and the next and previous pointers.

You will create a Queue class. In your class you will only have the QueuNode pointers to the front and a pointer to the back:

QueueNode *front // first item in the queue, where you take off

QueueNode *back // last item in the queue, where you add to

addBack() // puts on item at the end of the structure and // creates a new node if the queue is

full getFront() // returns the value at the front of the structure

removeFront() // removes the first item in the structure

Include appropriate constructors and destructors. Do not have a data member (or variable) for size.

The removeFront() function only replaces the value in the front node by inserting the sentinel. It does nothing else.

The getFront() and removeFront() functions will return a -1 if the queue is empty when the function is called.

Also write a driver program that uses your queue to demonstrate it works correctly. Prompt the user with a menu. The options should be: a) Enter a value”, “b) Display first value”, “c) Remove a value”, “d) Display the queue contents” , and “x) Exit” For example you display the menu. The user enters a). Your program then reads the integer to put in the back node. You can have the user type a) 7, or you have a) 7. You will return an error message if the user attempts to read or remove a value from an empty queue. Validate the user inputs.

Explanation / Answer

Given below is the C++ implementation of a Doubly Linked Circular Queue using a sentinel value of -1.

It adds a new node only when queue is full and when a value is removed, just replaces the value in the corresponding value by the sentinel as described in the question. Output is shown below. Please don't forget to rate the answer if it helped. Thank you.

queue.h

#ifndef queue_h
#define queue_h
#include <iostream>
using namespace std;
struct QueueNode
{
int value;
struct QueueNode *next;
struct QueueNode *prev;

QueueNode(int v, struct QueueNode *p = NULL, struct QueueNode *n = NULL)
{
value = v;
prev = p;
next = n;
if(prev != NULL)
prev->next = this;
if(next != NULL)
next->prev = this;
}
};

class Queue
{
private:
struct QueueNode *front, *back;
public:
Queue();
void addBack(int v);
int getFront();
int removeFront();
bool isFull();
bool isEmpty();
void display();
~Queue();
};

#endif /* queue_h */

queue.cpp

#include "queue.h"

Queue::Queue()
{
//create a sentinel node
front = back = new QueueNode(-1);
front->prev = back;
back->next = front;
}
void Queue::addBack(int v)
{
if(isFull())
back = new QueueNode(v, back, back->next);
else
{
back = back->next;
back->value = v;
}
if(front->value == -1)
front = front->next;
}
int Queue::getFront()
{
return front->value;
}
int Queue::removeFront()
{
if(isEmpty())
return -1;
else
{
int v = front->value;
front->value = -1;
front = front->next;
return v;
}
}
bool Queue::isFull()
{
return back->next == front->prev;
}
bool Queue::isEmpty()
{
return front->value == -1;
}
void Queue::display()
{
if(isEmpty())
cout << "Queue is empty." << endl;
else
{
QueueNode *n = front;
while(n->value != -1)
{
cout << n->value << " ";
n = n->next;
}

}
cout << endl;
}
Queue::~Queue()
{
QueueNode *n = front->next;
QueueNode *temp;
while(n != front)
{
temp = n->next;
delete n;
n = temp;
}
delete front;
}

main.cpp

#include "queue.h"
#include <iostream>
using namespace std;
int main()
{
char option = ' ';
int num;
Queue que;
while(option != 'x' && option != 'X')
{
cout << "a) Enter a value " << endl;
cout << "b) Display first value" << endl;
cout << "c) Remove a value" << endl;
cout << "d) Display queue" << endl;
cout << "x) Exit" << endl;
cout << "Enter your choice: ";
cin >> option;
switch(option)
{
case 'a':
case 'A':
cout << "Enter the number: ";
cin >> num;
que.addBack(num);
break;
case 'b':
case 'B':
cout << "Front = " << que.getFront() << endl;
break;
case 'c':
case 'C':
num = que.removeFront();
if(num == -1)
cout << "Queue empty." << endl;
else
cout << "Removed " << num << endl;
break;
case 'd':
case 'D':
que.display();
break;
case 'x':
case 'X':
break;
default:
cout << "Invalid menu choice!" << endl;

}
}
return 0;
}

output

a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = -1
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Queue empty.
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
Queue is empty.

a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 4
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
2 4
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 6
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
2 4 6
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 8
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
2 4 6 8 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Removed 2
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 4
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Removed 4
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
6 8 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 6
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
6 8 10 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 12
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
6 8 10 10 12
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 14
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: a
Enter the number: 16
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
6 8 10 10 12 14 16
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: b
Front = 6
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Removed 6
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
8 10 10 12 14 16
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Removed 8
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
10 10 12 14 16
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: c
Removed 10
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: d
10 12 14 16
a) Enter a value
b) Display first value
c) Remove a value
d) Display queue
x) Exit
Enter your choice: x

Navigate

C++ Create a Triangle class that has the following member variables: side1 - a d

C++ Create a binary tree as described in chapter 20 of the text. Your functions

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

C++ Create a abstract data type. Do not use any existing containers, such as the

Question

Explanation / Answer

Related Questions

Navigate