Practice Questions

Queue Implementation Given the following array based implementation of a Queue ADT (this is the same implementation you used in Assignment 11), add the asked for additional member methods to the array based Queue implementation. Recall that the array based implementation is treating an array of dynamically allocated memory as a circular buffer, and thus you have frontIndex and backIndex variables that point to the index at the front and the back of the array of items that represent the current front and back of the queue. /** queue (array implementation) * Implementation of the queue ADT as a fixed array. This * implementation combines a circular buffer implementation, to make * sure that both enqueue() and dequeue() operations are O(1) constant * time. However, it also uses dynamic memory allocation, and * demonstrates doubling the size of the allocated space as needed to * grow queue if/when the queue becomes full. * * @var allocSize The amount of memory currently allocated for this queue. * @var numitems The current length or number of items on the queue. * @var front A pointer to the index of the front item on the queue. * @var back A pointer to the back or last item on the queu. * @var items The items on the queue. This is a dynamically allocated array that * can grow if needed when queue exceeds current allocation. */ template class AQueue : public Queue { private: int allocSize; // amount of memory allocated int numitems; // The current length of the queue int frontIndex; // index of the front item of the queue int backIndex; // index of the last or rear item of the queue T* items; public: AQueue(int initialAlloc = 100); // constructor ~AQueue(); // destructor void clear(); bool isEmpty() const; void enqueue(const T& newItem); T front() const; void dequeue(); int length() const; }; /** queue (array) constructor * Constructor for queue. Default to enough room for 100 items * NOTE: the front pointer points directly to the index of the front item, but * the backIndex pointer points to the index-1 of the item where next insertion * will happen. * NOTE: we treat the items array as a circular buffer, so all increments of * indexes must be modulo current allocSize, to wrap backIndex around to beginning. * * @param initialAlloc Initial space to allocate for queue, defaults to * 100. */ template AQueue::AQueue(int initialAlloc) { allocSize = initialAlloc; numitems = 0; frontIndex = 0; backIndex = allocSize - 1; // back points to (x-1) % allocSize index items = new T[allocSize]; } /** queue (array) destructor */ template AQueue::~AQueue() { // free up currently allocated memory delete [] items; } /** queue (array) clear * Function to initialize the queue back to an empty state. * Postcondition: frontIndex = 0; backIndex = allocSize-1; numitems=0; isEmpty() == true */ template void AQueue::clear() { frontIndex = 0; backIndex = allocSize - 1; numitems = 0; } /** queue (array) isEmpty * Determine whether queue is currently empty or not. * * @returns returns true if the queue is empty, otherwise * returns false. */ template bool AQueue::isEmpty() const { return numitems == 0; } /** queue (array) enqueue * Add newItem to the back of the queue. * Preconditon: The queue exists * Postcondition: The queue is changed and newItem is added to the back * of the queue. * @param newItem The new item to add to the frontIndex of this queue. */ template void AQueue::enqueue(const T& newItem) { // if queue is full, grow it if (isFull()) { // double the current size int newAllocSize = 2 * allocSize; // alloc the new space T* newItems = new T[newAllocSize]; // and copy the queue to the new storage space // since we are copying anyway, we shift the items from the old // frontIndex back to index 0 int oldIndex = frontIndex; for (int index = 0; index < numitems; index++) { newItems[index] = items[oldIndex]; oldIndex = (oldIndex + 1) % allocSize; } frontIndex = 0; backIndex = numitems-1; // free up the old space, start using the new space delete [] items; items = newItems; allocSize = newAllocSize; } // add the item, and increment our top backIndex = (backIndex + 1) % allocSize; numitems++; items[backIndex] = newItem; } /** queue (array) front * Peek at and return the front element of the queue. * Preconditon: The queue exists and is not empty * Postcondition: If the queue is empty, we throw QueueEmpty * exception; otherwise, the front element of the queue is * returned * @returns T The item of type T currently on the front of this * queue. */ template T AQueue::front() const { //assert(topIndex != 0); if (isEmpty()) { throw EmptyQueueException("AQueue::front()"); } else { return items[frontIndex]; } } /** queue (array) dequeue * Remove the front element from the queue. Some ADT combine dequeue * and front. We have two separate operations in this ADT. * Preconditon: The queue exists and is not empty. * Postcondition: If the queue is empty, we throw QueueEmpty * exception; otherwise the front element of the queue is removed * from the queue. */ template void AQueue::dequeue() { // assert(topIndex != 0); if (isEmpty()) { throw EmptyQueueException("Aqueue::dequeue()"); } else { numitems--; frontIndex = (frontIndex + 1) % allocSize; } } /** queue (array) length * Getter method to access the current queue length. * * @returns length Returns the current queue length. */ template int AQueue::length() const { return numitems; } Question 13 (10 points) Using the array based queue implementation, search for and remove the indicated item (if found) from the middle of this queue. This is of course not a normal part of the queue abstraction, but is needed here for a particular application of our queue. When you remove the item, make sure you shift all of the other items in the array to fill in the hole for the removed item. You method can simply do nothing or print an error if the item that is requested to be searched for and removed is not currently present on the queue. Likewise, you only need to search for and remove the first instance of the item requested for removal. Here is the signature for the member function you should implement: /** queue (array) search and remove * Search for the indicated item and remove it from inside of this * queue if found * * @param searchItem A reference to an item of type T that may be on * the current queue and should be removed if found. */ template void AQueue::removeItemFromQueue(const T& searchItem) { } Answer for question Number 13: IS IT RIGHT OR WRONG? template <class T> void AQueue<T>::removeItemFromQueue(const T& searchItem) { if (T.isEmpty()) { return; } else { while (int i = 0; i < T.length(); i++) { if (T[i] = searchItem) { T[i].clear(); } } } } Please do it in c++