|
发表于 2004-4-26 14:30:05
|
显示全部楼层
[code:1]// header file lqueue.h
// linked queue
#ifndef LinkedQueue_
#define LinkedQueue_
#include <iostream>
#include "node.h"
#include "xcept.h"
template<class T>
class LinkedQueue {
// FIFO objects
template <class S> friend std::ostream& operator<<(std::ostream&, const LinkedQueue<S>&);
template <class S> friend std::istream& operator>>(std::istream&, LinkedQueue<S>&);
public:
LinkedQueue() {front = rear = 0;} // constructor
~LinkedQueue(); // destructor
bool IsEmpty() const
{return ((front) ? false : true);}
bool IsFull() const;
T First() const; // return first element
T Last() const; // return last element
LinkedQueue<T>& Add(const T& x);
LinkedQueue<T>& Delete(T& x);
int Size() const;
private:
Node<T> *front; // pointer to first node
Node<T> *rear; // pointer to last node
void Erase(); // delete all nodes
};
template<class T>
LinkedQueue<T>::~LinkedQueue()
{// Queue destructor. Delete all nodes.
Node<T> *next;
while (front) {
next = front->link;
delete front;
front = next;
}
}
template<class T>
bool LinkedQueue<T>::IsFull() const
{// Is the queue full?
Node<T> *p;
try {p = new Node<T>;
delete p;
return false;}
catch (NoMem) {return true;}
}
template<class T>
T LinkedQueue<T>::First() const
{// Return first element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return front->data;
}
template<class T>
T LinkedQueue<T>::Last() const
{// Return last element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return rear->data;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
{// Add x to rear of queue. Do not catch
// possible NoMem exception thrown by new.
// create node for new element
Node<T> *p = new Node<T>;
p->data = x;
p->link = 0;
// add new node to rear of queue
if (front) rear->link = p; // queue not empty
else front = p; // queue empty
rear = p;
return *this;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{// Delete first element and put it in x. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
// save element in first node
x = front->data;
// delete first node
Node<T> *p = front;
front = front->link;
delete p;
return *this;
}
template<class T>
void LinkedQueue<T>::Erase()
{// Delete all nodes.
Node<T> *next;
while (front) {
next = front->link;
delete front;
front = next;
}
}
template<class T>
int LinkedQueue<T>::Size() const
{// Return number of elements in the queue.
int size = 0;
Node<T> *current = front;
while (current) {
size++;
current = current->link;
}
return size;
}
// overload >>
template<class S>
std::istream& operator>>(std::istream& in, LinkedQueue<S>& q)
{// Input queue q from front to rear.
// first delete all elements from q
q.Erase();
// determine size of input queue
int size;
std::cout << "Enter size of queue" << std::endl;
in >> size;
if (!size) // no elements
return in;
// at least one element to input
// input the queue elements and link together
std::cout << "Enter the elements from front to rear"
<< std::endl;
// get first element
q.rear = q.front = new Node<S>;
in >> q.front->data;
// get remaining elements
for (int i = 2; i <= size ; i++) {
q.rear->link = new Node<S>;
q.rear = q.rear->link;
in >> q.rear->data;
}
// set pointer in rear node
q.rear->link = 0;
return in;
}
// overload <<
template <class S>
std::ostream& operator<<(std::ostream& out,const LinkedQueue<S>& q)
{// Output the queue q from front to rear
// output queue size
int size = q.Size();
out << "The queue has " << size
<< " element(s)" << std::endl;
// output queue elements
out << "The element(s) from front to rear are"
<< std::endl;
Node<S> *current = q.front;
for (int i = 1; i <= size ; i++) {
out << current->data << ' ';
current = current->link;
}
out << std::endl;
return out;
}
#endif
[/code:1] |
|