// QueueLinked.h #include <stdexcept> #include <iostream> using namespace std; #

Question

// QueueLinked.h

#include <stdexcept>

#include <iostream>

using namespace std;

#include "Queue.h"

template <typename DataType>

class QueueLinked : public Queue<DataType> {

public:

QueueLinked(int maxNumber = Queue<DataType>::MAX_QUEUE_SIZE);

QueueLinked(const QueueLinked& other);

QueueLinked& operator=(const QueueLinked& other);

~QueueLinked();

void enqueue(const DataType& newDataItem) throw (logic_error);

DataType dequeue() throw (logic_error);

void clear();

bool isEmpty() const;

bool isFull() const;

// Programming Exercise 2

void putFront(const DataType& newDataItem) throw (logic_error);

DataType getRear() throw (logic_error);

// Programming Exercise 3

int getLength() const;

void showStructure() const;

private:

class QueueNode {

public:

QueueNode(const DataType& nodeData, QueueNode* nextPtr);

DataType dataItem;

QueueNode* next;

};

QueueNode* front;

QueueNode* back;

};

Explanation / Answer

/* * File: queue.h * ------------- * This file exports the Queue class, a collection in which values are * ordinarily processed in a first-in/first-out (FIFO) order. */ #ifndef _queue_h #define _queue_h #include "vector.h" /* * Class: Queue * ----------------------- * This class models a linear structure called a queue in which values are * added at one end and removed from the other. This discipline gives rise * to a first-in/first-out behavior (FIFO) that is the defining feature of * queues. */ template class Queue { public: /* * Constructor: Queue * Usage: Queue queue; * ------------------------------ * Initializes a new empty queue. */ Queue(); /* * Destructor: ~Queue * ------------------ * Frees any heap storage associated with this queue. */ virtual ~Queue(); /* * Method: size * Usage: int n = queue.size(); * ---------------------------- * Returns the number of values in the queue. */ int size() const; /* * Method: isEmpty * Usage: if (queue.isEmpty()) ... * ------------------------------- * Returns true if the queue contains no elements. */ bool isEmpty() const; /* * Method: clear * Usage: queue.clear(); * --------------------- * Removes all elements from the queue. */ void clear(); /* * Method: enqueue * Usage: queue.enqueue(value); * ---------------------------- * Adds value to the end of the queue. */ void enqueue(ValueType value); /* * Method: dequeue * Usage: ValueType first = queue.dequeue(); * ----------------------------------------- * Removes and returns the first item in the queue. */ ValueType dequeue(); /* * Method: peek * Usage: ValueType first = queue.peek(); * -------------------------------------- * Returns the first value in the queue, without removing it. For * compatibility with the STL classes, this method is also exported under * the name front, in which case it returns the value by reference. */ ValueType peek() const; /* * Method: front * Usage: ValueType first = queue.front(); * --------------------------------------- * Returns the first value in the queue by reference. */ ValueType & front(); /* * Method: back * Usage: ValueType last = queue.back(); * ------------------------------------- * Returns the last value in the queue by reference. */ ValueType & back(); /* * Method: toString * Usage: string str = queue.toString(); * ------------------------------------- * Converts the queue to a printable string representation. */ std::string toString(); /* Private section */ /**********************************************************************/ /* Note: Everything below this point in the file is logically part */ /* of the implementation and should not be of interest to clients. */ /**********************************************************************/ /* * Implementation notes: Queue data structure * ------------------------------------------ * The Queue class is implemented using a ring buffer. */ private: /* Instance variables */ Vector ringBuffer; int count; int capacity; int head; int tail; /* Private functions */ void expandRingBufferCapacity(); }; extern void error(std::string msg); const int INITIAL_CAPACITY = 10; /* * Implementation notes: Queue constructor * --------------------------------------- * The constructor must allocate the array storage for the queue elements * and initialize the fields of the object. */ template Queue::Queue() { clear(); } /* * Implementation notes: ~Queue destructor * --------------------------------------- * All of the dynamic memory is allocated in the Vector class, so no work * is required at this level. */ template Queue::~Queue() { /* Empty */ } template int Queue::size() const { return count; } template bool Queue::isEmpty() const { return count == 0; } template void Queue::clear() { capacity = INITIAL_CAPACITY; ringBuffer = Vector(capacity); head = 0; tail = 0; count = 0; } template void Queue::enqueue(ValueType value) { if (count >= capacity - 1) expandRingBufferCapacity(); ringBuffer[tail] = value; tail = (tail + 1) % capacity; count++; } /* * Implementation notes: dequeue, peek * ----------------------------------- * These methods must check for an empty queue and report an error if there * is no first element. */ template ValueType Queue::dequeue() { if (count == 0) error("dequeue: Attempting to dequeue an empty queue"); ValueType result = ringBuffer[head]; head = (head + 1) % capacity; count--; return result; } template ValueType Queue::peek() const { if (count == 0) error("peek: Attempting to peek at an empty queue"); return ringBuffer.get(head); } template ValueType & Queue::front() { if (count == 0) error("front: Attempting to read front of an empty queue"); return ringBuffer[head]; } template ValueType & Queue::back() { if (count == 0) error("back: Attempting to read back of an empty queue"); return ringBuffer[(tail + capacity - 1) % capacity]; } /* * Implementation notes: expandRingBufferCapacity * ---------------------------------------------- * This private method doubles the capacity of the ringBuffer vector. Note * that this implementation also shifts all the elements back to the * beginning of the vector. */ template void Queue::expandRingBufferCapacity() { Vector copy = ringBuffer; ringBuffer = Vector(2 * capacity); for (int i = 0; i > ch; if (ch != '}') { is.unget(); while (true) { ValueType value; readGenericValue(is, value); queue.enqueue(value); is >> ch; if (ch == '}') break; if (ch != ',') { error(std::string("operator >>: Unexpected character ") + ch); } } } return is; } #endif

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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