We will be working with two files lab.cpp Queue.h QUESTIONS 1. Write an expressi

Question

We will be working with two files

lab.cpp

Queue.h

QUESTIONS

1. Write an expression that gives the index of the first element of the queue. Make sure that the expression works for all cases (including when the front element wraps around).

2. Write an expression that gives the index of the last element of the queue.

3. Without wrap-around the loop would be simple to write (where first_index is your answer to question 1 and last_index is your answer to question 2):

for (i = first_index; i <= last_index; i++)

a. What would we need to change i++ to so that it will work for the wrap-around case?

b. Even after this change, i <= last_index will still cause a problem. Explain why.

4. Instead, we will use the following code which will stop when i is past the last index in the queue:

for (i = first_index; i != last_index + 1; increment i)

where we are printing each element in turn.

cout << data [i];

Write the expression for last_index + 1 with wrap-around.

Make the following changes to the implementation file:

Finish writing the queue member function called elements that returns the number of elements in a queue. It should use the loop described above to move through the elements in the queue to count them. It should return the number counted. The function should work if the queue is empty (should return 0).

int elements ();

Finish writing the queue member function called print that prints the elements in the queue on a single line. It should use the loop described above to move through the elements in the queue to print them. If the queue is empty, it should not print anything.

void print ();

Make the following changes to the application file (there are comments to help instruct you where to place each item):

Declare a queue called qute.

print the queue.

Print the number of elements in the queue (add to the cout).

enqueue the characters H, I, P, P and O on the queue.

print the queue.

Print the number of elements in the queue.

dequeue the queue three times.

enqueue the characters K, E and R on the queue.

print the queue.

Print the number of elements in the queue.

Explanation / Answer

1) if (front==-1) cout<<"Queuue is empty"
   else return front;

and to consider for wrap around, we can update front as below in dequeue:
if (front == rear) {
   front = rear =-1;
} else front = (front+1)%queue_size;

2) if(rear == -1) cout<<"Queue is Empty"
   else return rear;

and to consider for wrap around, in enqueue update rear as:
   rear = (rear+1)%queue_size;
   if(front == -1) front = rear;

3)
a) to count for wrap around i++ should be changed to i = (i+1)%queue_size
b) i<=last_index would still cuse problem as now we have a circular queue, so it is not guarenteed that the last_index will always be smaller than the first_index. It can be the other way round too.

4) i != (last_index + 1) % queue_size should do the job for us.

queue.h

// implementation file for the queue class

#include <iostream>
using namespace std;

const int queue_size = 6;

class queue
{
private:
char data [queue_size]; // elements in the queue
int front, // index to the front of the queue, indexes one previous
// to actual front element (remove)
rear; // index of the rear element;
public:
queue (); // create an empty queue
void enqueue (char item); // adds an element to the rear
char dequeue (); // removes an element from the front
bool empty (); // returns true for an empty queue
bool full (); // returns true for a full queue
int elements (); // returns the number of elements in the queue
void print (); // prints the queue from front to rear
};

// returns the number of elements in the queue. If queue is empty, it returns 0.
int queue::elements ()
{
if(empty()) return 0;
int x=0;
for (int i = front+1; i != (rear + 1) % queue_size; i = (i + 1)%queue_size) {
x++;
}
return x;

}

// prints the elements in the queue from first to last element. If the queue is empty, nothing
// is printed
void queue::print ()
{
if(empty()) return;
for (int i = front+1; i != (rear + 1) % queue_size; i = (i + 1)%queue_size) {
cout<<data[i];
}

}

// constructor creates an empty queue
queue::queue ()
{
front = -1;
rear = -1;
}

// enqueue adds an element to the rear of the queue
void queue::enqueue (char item)
{
// if full, can't add another element
if (full ())
{
cout << " Queue Error: Can't add to a full queue";
cout << " Queue will not be changed";
}
else // ok to add an item
{
rear = (rear + 1) % queue_size;
data [rear] = item;
}
}

// dequeue removes an element from the front of the queue
char queue::dequeue ()
{
// if the queue is empty, we can't remove a value
if (empty ())
{
cout << " Queue Error: Can't remove from an empty queue";
cout << " Returning a blank";
return ' ';
}
else // ok to remove a value
{
front = (front + 1) % queue_size;
return data [front];
}
}

// empty returns true if the queue is empty
bool queue::empty ()
{
return front == rear;
}

// full returns true if the queue is full
bool queue::full ()
{
return (rear + 1) % queue_size == front;
}

lab.cpp

#include <cstdlib>
#include <iostream>
#include "queue.h"
/*
Testing program for queue member functions elements and print.
*/

using namespace std;

int main()
{
// declare a queue called qute
queue qute;

cout << " The queue to start is: ";
qute.print();

// print the number of elements in the queue
cout << " Number of elements to start is " << qute.elements()<<endl;

// enqueue the letters H, I, P, P and O
qute.enqueue('H');
qute.enqueue('I');
qute.enqueue('P');
qute.enqueue('P');
qute.enqueue('O');

cout << " The queue after enqueueing is: ";
qute.print();

// print the number of elements in the queue
cout << " Number of elements after enqueueing is " << qute.elements()<<endl;

// dequeue three elements
qute.dequeue();
qute.dequeue();
qute.dequeue();

// enqueue the letters K, E and R
qute.enqueue('K');
qute.enqueue('E');
qute.enqueue('R');

cout << " The final queue is: ";
qute.print();

// print the number of elements in the queue
cout << " Number of elements in final queue is " << qute.elements();

cout << " ";

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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