This assignment is an exercise in implementing the queue ADT using an array-base
ID: 3815320 • Letter: T
Question
This assignment is an exercise in implementing the queue ADT using an array-based data structure.
Assignment
This program creates and implements a class to represent the Queue ADT using an array.
A driver program is provided for this assignment to test your implementation. You don't have to write the tests.
Program
You will need to write a single class for this assignment, the Queue class. You will need to implement several methods and functions associated with this class.
The class should be implemented as two separate files. The class definition should be placed in an appropriately named header (.h) file. The implementations of the class methods and any other associated functions should be placed in a separate .cpp file for the class.
class Queue
Data members
This class contains a pointer to an integer that will point to the first element of a dynamically allocated array of integers (the queue array). Because the array is allocated dynamically, a data member is also maintained inside the class to determine the maximum number of elements that may be stored in the array (the queue capacity). Another data member is used to keep track of the number of data items currently stored in the vector (the queue size). Both of these data members should be declared as data type size_t (which corresponds to an unsigned integer).
The class also requires two integer data members: the subscript of the front item in the queue (the queue front subscript) and the subscript of the back item in the queue (the queue back subscript).
Methods and associated functions
As usual, methods that do not alter the data members of the object that called the method should be declared to be const.
Constructor
The class should have a default constructor that takes no arguments. The constructor should set the queue size and queue capacity to 0 and the queue array pointer to nullptr. The queue front subscript should be initialized to 0. The queue back subscript should be initialized to the queue capacity - 1. Alternately, the data members can be initialized in the class declaration, in which case this method's body can be empty.
Destructor
The class should have a destructor that deletes the dynamic memory for the queue array. The destructor should NOT call the clear() method.
Copy Constructor
The class should also have a proper copy constructor. This will be similar to the copy constructor you wrote for the Vector class for Assignment 5. The main difference is that you will need to copy the contents of the entire queue array (elements 0 to queue capacity - 1), not just elements 0 to queue size - 1.
Copy Assignment Operator
The copy assignment operator should be properly overloaded to allow one Queue to be assigned to another. Once again, the code here will be similar to what you wrote for Assignment 5. As with the copy constructor, you will need to copy the contents of the entire queue array.
operator<<
The output operator should be overloaded so that a Queue can be printed on the standard output. As in Assignments 4 and 5, this will need to be a standalone friend rather than a method.
Looping through the queue array to print the elements is complicated by the fact that the queue front subscript will not necessarily be less than the queue back subscript. One way to make this work is to have a counter that controls how many times the loop is done, and a subscript that starts at the front of the queue and is incremented until it reaches the back of the queue:
clear()
This method takes no arguments and returns nothing. It should properly set the queue back to the empty state (set the queue size to 0, the queue front subscript to 0, and the queue back subscript to the queue capacity - 1).
size()
This method takes no arguments and returns a size_t. It should return the queue size.
capacity()
This method takes no arguments and returns a size_t. It should return the queue capacity.
empty()
This method takes no arguments and returns a boolean value. It should return true if the queue size is 0; otherwise it should return false.
front()
This method takes no arguments and returns an integer. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should return the front element of the queue array (the one at the queue front subscript).
back()
This method takes no arguments and returns an integer. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should return the back element of the queue array (the one at the queue back subscript).
push()
This method takes an integer argument, the item to insert into the queue. If the queue is full (the queue size is equal to the queue capacity), this method will need to call the reserve() method to increase the capacity of the queue array and make room for the item to insert. If the queue capacity is currently 0, pass a new capacity of 1 to the reserve() method. Otherwise, pass a new capacity of twice the current queue capacity to the reserve() method.
To insert an item, the method should increment the queue back subscript (wrapping around to the front of the queue array if needed) and then copy the method argument into the queue array as the new back item in the queue. The queue size should be incremented by 1.
pop()
This method takes no arguments and returns nothing. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should increment the queue front subscript (wrapping around to the front of the queue array if needed) to effectively remove the front item in the queue array. The queue size should be decremented by 1.
reserve()
This method takes an unsigned integer argument, the new capacity to allocate for the queue array. It returns nothing. It should reserve additional capacity for the queue array equal to the new capacity passed in.
Explanation / Answer
class queue
{
int Capacity=5;
int queue1[Capacity];
int rear,front;
public:
queue()
{
rear=-1;
front=-1;
}
//pushing element to queue
void push(int x)
{
if(rear > 4)
{
cout <<"queue over flow";
front=rear=-1;
return;
}
queue1[++rear]=x;
}
//clearing the queue
void clear(){
rear=-1;
front=-1;
}
//clearing the queue
void empty(){
rear=-1;
front=-1;
}
//returns size of the queue
int capacity(){
return Capacity;
}
//returns size
int size(){
return rear;
}
//returns front element
int front(){
return queue1[front];
}
//returns rear element
int back(){
return queue1[rear];
}
void pop()
{
if(front==rear)
{
cout <<"queue under flow";
return;
}
cout <<"deleted" <<queue1[++front];
}
};