Data Abstraction and Problem Solving with C++
Walls and Mirrors
by Frank M. Carrano
QueueP.cpp
Go to the documentation of this file.00001 00017 #include <cstddef> // for NULL 00018 #include <cassert> // for assert 00019 #include <new> // for bad_alloc 00020 #include "QueueP.h" // header file 00021 00022 using namespace std; 00023 00024 Queue::Queue() : backPtr(NULL), frontPtr(NULL) 00025 { 00026 } // end default constructor 00027 00028 Queue::Queue(const Queue& Q) 00029 { // Implementation left as an exercise (Exercise 6). 00030 } // end copy constructor 00031 00032 Queue::~Queue() 00033 { 00034 while (!isEmpty()) 00035 dequeue(); 00036 assert ( (backPtr == NULL) && (frontPtr == NULL) ); 00037 } // end destructor 00038 00039 bool Queue::isEmpty() const 00040 { 00041 return backPtr == NULL; 00042 } // end isEmpty 00043 00044 void Queue::enqueue(const QueueItemType& newItem) 00045 throw(QueueException) 00046 { 00047 try 00048 { // create a new node 00049 QueueNode *newPtr = new QueueNode; 00050 00051 // set data portion of new node 00052 newPtr->item = newItem; 00053 00054 newPtr->next = NULL; 00055 00056 // insert the new node 00057 if (isEmpty()) 00058 // insertion into empty queue 00059 frontPtr = newPtr; 00060 else 00061 // insertion into nonempty queue 00062 backPtr->next = newPtr; 00063 00064 backPtr = newPtr; // new node is at back 00065 } 00066 catch (bad_alloc e) 00067 { 00068 throw QueueException( 00069 "QueueException: enqueue cannot allocate memory."); 00070 } // end try 00071 } // end enqueue 00072 00073 void Queue::dequeue() throw(QueueException) 00074 { 00075 if (isEmpty()) 00076 throw QueueException( 00077 "QueueException: empty queue, cannot dequeue"); 00078 else 00079 { // queue is not empty; remove front 00080 QueueNode *tempPtr = frontPtr; 00081 if (frontPtr == backPtr) // special case? 00082 { // yes, one node in queue 00083 frontPtr = NULL; 00084 backPtr = NULL; 00085 } 00086 else 00087 frontPtr = frontPtr->next; 00088 00089 tempPtr->next = NULL; // defensive strategy 00090 delete tempPtr; 00091 } // end if 00092 } // end dequeue 00093 00094 void Queue::dequeue(QueueItemType& queueFront) 00095 throw(QueueException) 00096 { 00097 if (isEmpty()) 00098 throw QueueException( 00099 "QueueException: empty queue, cannot dequeue"); 00100 else 00101 { // queue is not empty; retrieve front 00102 queueFront = frontPtr->item; 00103 dequeue(); // delete front 00104 } // end if 00105 } // end dequeue 00106 00107 void Queue::getFront(QueueItemType& queueFront) const 00108 throw(QueueException) 00109 { 00110 if (isEmpty()) 00111 throw QueueException( 00112 "QueueException: empty queue, cannot getFront"); 00113 else 00114 // queue is not empty; retrieve front 00115 queueFront = frontPtr->item; 00116 } // end getFront 00117 // End of implementation file.
