キューのC++クラステンプレート実装
5428 ワード
ヘッダファイル:
実装ファイル:
テストファイル:
/*****************************************************************************
* queue.h
*
* A simple queue implemented by C++ template class .
*
* Zhang Ming, 2009-10
*****************************************************************************/
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
#include <cstdlib>
using namespace std;
namespace itlab
{
/**
* Queue Node
*/
template <typename Type>
struct LinkNode
{
Type data;
LinkNode<Type> *next;
LinkNode() : next(NULL)
{ }
LinkNode( const Type &x, LinkNode<Type> *p=NULL ) : data(x), next(p)
{ }
};
/**
* Queue
*/
template <typename Type>
class Queue
{
public:
Queue();
~Queue();
// Queue( const Queue<Type> &rhs);
// Queue<Type>& operator=( const Queue<Type> &rhs);
inline bool isEmpty() const;
inline void makeEmpty();
inline void enqueue( const Type &x );
inline void dequeue( Type &x );
inline void getFront( Type &x );
private:
LinkNode<Type> *front,
*rear;
inline void handleUnderflow();
};
#include <queue-impl.h>
}
// namespace itlab
#endif
// QUEUE_H
実装ファイル:
/*****************************************************************************
* queue-impl.h
*
* Implementation for Queue class.
*
* Zhang Ming, 2009-10
*****************************************************************************/
/**
* constructors and destructor
*/
template <typename Type>
Queue<Type>::Queue() : front(NULL), rear(NULL)
{
}
template <typename Type>
Queue<Type>::~Queue()
{
makeEmpty();
}
/**
* If the queue is empty, return true.
*/
template <typename Type>
inline bool Queue<Type>::isEmpty() const
{
return front == NULL;
}
/**
* Make the queue empty.
*/
template <typename Type>
inline void Queue<Type>::makeEmpty()
{
LinkNode<Type> *p;
while( front != NULL )
{
p = front;
front = front->next;
delete p;
}
}
/**
* Enter an element into the queue.
*/
template <typename Type>
inline void Queue<Type>::enqueue( const Type &x )
{
if( front == NULL )
{
front = rear = new LinkNode<Type>( x );
if( !front )
{
cerr << "Out of memory!" << endl;
exit( 1 );
}
}
else
{
rear->next = new LinkNode<Type>( x );
if( !rear )
{
cerr << "Out of memory!" << endl;
exit( 1 );
}
rear = rear->next;
}
}
/**
* Pop an element from the queue.
*/
template <typename Type>
inline void Queue<Type>::dequeue( Type &x )
{
if( !isEmpty() )
{
LinkNode<Type> *p = front;
x = front->data;
front = front->next;
delete p;
}
else
handleUnderflow();
}
/**
* Get the front element of the queue.
*/
template <typename Type>
inline void Queue<Type>::getFront( Type &x )
{
if( !isEmpty() )
x = front->data;
else
handleUnderflow();
}
/**
* Handle the error of get element from an empty queue.
*/
template <typename Type>
inline void Queue<Type>::handleUnderflow()
{
cerr << "The queue is empty!" << endl << endl;
exit( 1 );
}
テストファイル:
/*****************************************************************************
* queue_test.cpp
*
* Queue class testing.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#include <iostream>
#include <string>
#include <queue.h>
using namespace std;
using namespace itlab;
struct Student
{
int stuNum;
string stuName;
string department;
Student( int number = 0, const string &name = "Tom&Jerry",
const string &dpt = "Information" )
: stuNum(number), stuName(name), department(dpt)
{ }
};
int main()
{
Student stu;
Queue<Student> q;
q.enqueue( Student(11, "ZhangMing", "Information") );
q.enqueue( Student(16, "HuZhaoJun") );
q.enqueue( Student(11, "ZhangYuYang", "AutoControl") );
q.enqueue( Student() );
q.getFront( stu );
cout << " " << stu.stuNum << "\t" << stu.stuName << "\t"
<< stu.department << endl;
cout << endl;
while( !q.isEmpty() )
{
q.dequeue( stu );
cout << " " << stu.stuNum << "\t" << stu.stuName << "\t"
<< stu.department << endl;
}
cout << endl;
q.getFront( stu );
cout << " " << stu.stuNum << "\t" << stu.stuName << "\t"
<< stu.department;
cout << endl << endl;
return 0;
}