Modify the ArrayQueue class in the class GitHub (https://github.com/apanangadan/
ID: 3862301 • Letter: M
Question
Modify the ArrayQueue class in the class GitHub (https://github.com/apanangadan/CSUF-CPSC_131/blob/master/ArrayQueue.h) page to make the array queue capacity extendable.
Assuming the default queue capacity is 5.
You only need to write and show the C++ codes to implement the below two functions:
a. void resize(int N);
This function resizes the current queue array capacity to N.
b. void enqueue(const E& e);
This function appends a new element to the back of the queue. If the queue is full then it calls the resize function to double the current capacity and then en-queue the new element to the new capacity queue.
Example of an Extendable Array Queue Class declaration:
template <typename E>
class ExtArrayQueue {
enum { DEF_CAPACITY = 5 }; // default queue capacity
public:
ExtArrayQueue(int cap = DEF_CAPACITY); // constructor from capacity
int size() const; // number of items in the queue
bool empty() const; // is the queue empty?
const E& front() const; // get the front element
void enqueue(const E& e); // add to back of queue
void dequeue(); // remove from front of queue
void printAll(); // print all elements in the queue
Private:
void resize(int N); // resize the array to size N
E* Q; // array of queue elements
int capacity; // queue capacity
int f; // index of the front of the queue
int r; // index of the rear of the queue
int n; // number of elements
};
Explanation / Answer
// Code based on:
// Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011.
//
#pragma once
#include <stdexcept>
using namespace std;
template <typename E>
class ArrayQueue {
enum { DEF_CAPACITY = 100 }; // default queue capacity
public:
ArrayQueue(int cap = DEF_CAPACITY); // constructor from capacity
int size() const; // number of items in the stack
bool empty() const; // is the stack empty?
const E& front() const; // get the top element
void enqueue(const E& e); // add to back of queue
void dequeue(); // remove from front of queue
void printAll(); // print all elements on stack to cout
void resize(int N);
private: // member data
E* Q; // array of queue elements
int capacity; // queue capacity
int f; // index of the front of the queue
int r; // index of the rear of the queue
int n; // number of elements
};
template <typename E> ArrayQueue<E>::ArrayQueue(int cap)
: Q(new E[cap]), capacity(cap), f(0), r(0), n(0) { } // constructor from capacity
template <typename E> int ArrayQueue<E>::size() const
{
return n;
} // number of items in the queue
template <typename E> bool ArrayQueue<E>::empty() const
{
return (n == 0);
} // is the stack empty?
template <typename E> // return element at front of queue
const E& ArrayQueue<E>::front() const {
if (empty()) throw length_error("front of empty queue");
return Q[f];
}
template <typename E> // insert element to back of queue
void ArrayQueue<E>::enqueue(const E& e) {
if (size() == capacity) {resize(capacity*2);}
Q[r] = e;
r = (r + 1) % capacity;
n++;
}
template <typename E>
void ArrayQueue<E>::resize(int N)
{
capacity = N;
E* tempQ = new E[N];
int n = size();
for (int i = 0; i < n; i++) {
tempQ[i] = Q[i];
}
delete Q;
Q = tempQ;
}
template <typename E> // remove element at front of queue
void ArrayQueue<E>::dequeue() {
if (empty()) throw length_error("enqueue from empty queue");
f = (f + 1) % capacity;
n--;
}
// print all elements on queue
template <typename E>
void ArrayQueue<E>::printAll() {
if (empty()) throw length_error("Empty queue");
cout << "Elements in queue: ";
int front = f;
for (int i = 0; i < n; i++) {
cout << "{" << Q[front] << "} ";
front = (front + 1) % capacity;
}
cout << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.