Hi, this is for C++. Any help would be much appreciated. I\'ve included the clas
ID: 3715521 • Letter: H
Question
Hi, this is for C++. Any help would be much appreciated. I've included the class notes for the assignment at the bottom.
In this assignment, you will implement a CircularQueue class that stores chars, with the following characteristics:
A circular queue is stored in an array.
In addition to the array, the data structure keeps track two indices in the array: a "start" position, and an "end" position.
When an item is enqueued (added) to the queue, it is added at the end position. The end position is then incremented, wrapping around to zero it reaches the end of the array.
To dequeue (remove and return) an item from the queue, we return the item at the start position, and increment the start position (once again wrapping around when it reaches the end of the array).
If start and end are the same, then the queue is empty.
If (end+1) % arrayLength == start, then the queue is full. To add another element to the queue, a new array must be allocated with twice the size of the current one, and all of the elements copied to it, starting at position 0. In C++, after the copying, the old array should be deleted to avoid a memory leak.
Write a class called CircularQueue, or something similar, that implements a circular queue for chars as described above, using an array of chars as the array storage. The queue should start out with an array of length 2.
Write a program that uses your CircularQueue class to answer queries that either add letters to the queue, or remove them from the queue. When a letter is removed from the queue, print out both the letter's position in the array, and the letter itself.
Sample program run
Notes:
Data model
Implementation notes
To add something to the queueFirst check if it is full:
if (((end+1)%capacity) == start)
Resize if full
create a new array that holds 2 * capacity elements
copy all the elements over to data starting at element 0.
delete the old data
set data to point to the new array
set end to be capacity-1
set start to be 0
double size of capacity
Place new item at data[end]
increment end:
end = (end+1) % capacity
To remove something from the queue and print
Print start
Print data[start]
start = (start+1) % capacity
The queue will be empty when end equals start.
-Do not need to check for assignment
Explanation / Answer
#include <iostream>
#define SIZE 3
using namespace std;
class Queue {
private:
char items[SIZE];
int front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if(front == 0 && rear == SIZE - 1){
return true;
}
if(front == rear + 1) {
return true;
}
return false;
}
bool isEmpty(){
if(front == -1) return true;
else return false;
}
void enQueue(char element){
if(isFull()){
cout << "Queue is full";
} else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}
}
char deQueue(){
char element;
if(isEmpty()){
cout << "Queue is empty" << endl;
return(-1);
} else {
element = items[front];
if(front == rear){
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front=(front+1) % SIZE;
}
cout << endl << "Deleted: " << element << " Posotion:" << front;
return(element);
}
}
};
int main()
{
Queue q;
int i;
char c;
do
{
cout<<" Enter your choice: 1.Add 2.Delete 3.Quit ";
cin>>i;
if(i==1)
{
cout<<"Enter Element: ";
cin>>c;
q.enQueue(c);
}
else if(i==2)
q.deQueue();
else
break;
} while(i!=3);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.