数据结构 --队列 --- C++实现.doc

目录
一、 题目内容及要求 3
二、 题目设计思路 3
三、 类设计与类关系 4
四、 主要功能函数流程图 4
五、 运行结果及分析 5
六、 总结 6

一、 题目内容及要求
1. 队列是一种连续的存储结构，存入数据只能从一端（称为尾部）进入，取出数据则只能从另一端（头部）取出。根据下述描述实现一个自定义的队列类：
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)
{ }
};
template <typename Type>
class Queue
{
public:
Queue (); //构造函数
~Queue (); //析构函数
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; //指向头结点的指针,front->next->data 是队头的第一个元素
LinkNode<Type> *rear; //指向队尾（最后添加的一个元素）的指针
inline void handleUnderflow(); //控制队列下溢
};
二、 题目设计思路
1. queue.h文件
在queue.h头文件中使用命名空间itlab在其中声明：
（1） 模板结构体链表结点（struct LinkNode），其中包含的数据成员有：
①模板参数类类型Type 对应的data，存放模板实现类的具体数据，②LinkNode<Type> 模板类型结构体指针 next，用来指向下一个结点；
成员函数包括：
①LinkNode()无参构造函数，其中数据成员next默认为NULL，②LinkNode(const Type &x,LinkNode<Type> *p = NULL)，采用参数初始化表对数据成员初始化，其中第一个参数为常量Type类型的引用x，初始化数据成员data，第二个参赛为结构体类型指针p默认值为NULL，用来初始化数据成员next。
（2） 模板类队列（class Queue），包含的公共成员函数有：
①无参构造函数 Queue()，在定义对象时，由系统调用，完成对象的初始化；
②析构函数~Queue()，与构造函数相反，是在撤销对象占用内存前进行一些清理工作。可以被用来执行“用户希望在最后一次使用对象之后所执行的任何操作”；
③内联函数判断队列是否为空，返回值为布尔类型常量，inline bool isEmpty() const;
④内联函数清空队列，无返回值，inline void makeEmpty();
⑤内联函数向队列中插入一个元素，inline void enqueue(const Type &x)，参数为Type类型常量，插入的新元素作为队列中的队尾结点；
⑥内联函数从队列中弹出一个元素， inline void dequeue( Type &x )，无返回值，但传入参数为Type类型的引用x，从对首取出结点元素的数据，将其赋值给x，实现函数值的返回；
⑦内联函数得到对首元素结点的数据，inline void getFront( Type &x)，同样采用函数参数引用类型间接返回函数值；
私有数据成员包括：
①指向模板结构体类型变量的头指针，LinkNode<Type> *front
②指向模板结构体类型变量的后继指针，LinkNode<Type> *rear
③内联函数控制队列下溢，inline void handleUnderflow()。
（3） 同时包含其实现文件queue-impl.h，#include "queue-impl.h" 。
2. queue-impl.h文件
在queue-impl.h头文件，是实现queue.h头文件中声明的模板类Queue，实现其声明的函数，完成函数的定义，在预编译时，会将头文件queue-impl.h中的内容取代头文件queue.h中的 #include "queue-impl.h"这一行。
3. queue_test.cpp
在queue_test.cpp文件中，包含主函数，声明结构体类型Student，是模板结构体链表（LinkNode<Type>）的实现类，将其作为插入队列和弹出队列的基本元素，测试队列类Queue的主要成员函数：判断队列是否为空（isEmpty）、向对列中插入一个元素（enqueue）、从队列中弹出一个元素（dequeue）、得到队首元素的数据（getFront）、私有成员函数控制队列下溢（handleUnderflow）。
三、 类设计与类关系
1. 类设计
主要包含队列类Queue。其私有数据成元是指向结构体类型变量（struct Student）的头指针和指向结构体类型的后继指针。
在main函数中声明了结构体类型Student，其主要包含整型的学号、字符串类型的学生姓名、字符串类型的系部名称，以及带默认参数的构造函数。
2. 类关系
在main函数中，通过定义一个队列类类型的对象q（Queue<Student> q），显示的将结构体类型（Student为结构体类型）传递给 Queue<Type>对应的类参Type（模板参数类型）。
四、 主要功能函数流程图
1. 向对列中插入一个元素函数（ inline void enqueue(const Type &x) ）流程图

2. 从队列中弹出一个元素函数（ inline void dequeue( Type &x ) ）流程图

五、 运行结果及分析
1. 运行结果：

2. 结果分析：
（1） 队列初始为空，依次将学生插入队列，并打印入队顺序；
（2） 此时调用getFront(Type &x)函数取得对头的元素；
（3） 出对时，按照先进先出原则，打印出队顺序。
六、 总结
1.模板机制
（1）模板的代码重用机制是基于C语言宏展开基础发展而来，宏展开的一套文本替换算法从预处理阶段搬移到编译阶段，结合函数重载中的一套类型匹配搜寻算法一起就诞生了模版的内在运作机制。
（2）函数模板和类模板提供了类型参数化的通用机制。函数模板的类参在函数的调用点根据实参的类型反演出来，形成重载函数，同时实参的数值作为入口又进行函数调用。
（3）类模板的类参一般由对象定义的方式显式给出，根据直接指定的类名或整型常数初始化模板类参形参表中的对应项目值，用这些具体的类名和常数替换模板中类参或形参，形成特定的类。
这些工作是编译器自动宏替换复制完成的，但比预处理的宏替换执行了更多的类型安全检查，而根据模板生成的代码具有明显的相近性质。
（4）需要注意形参与类参的区别，形参是运行时压入堆栈传递给函数的数据值，而类参是在函数调用点获得的实参的静态数据类型，数据类型是静态的，该数据类型在编译阶段确定。
（5）函数模板产生的函数是一系列形参个数相同，形参数据类型不同的重载函数，类模板产生的类是类名不同，结构相近的类。
（6）此外，类模板的不同实现是不同的类，此特定的类上的模板成员函数不同于彼模板类相应的成员函数版本。其间通过类域分辨符进行了清晰的分界，因此类模板提供一种类型安全的鉴别机制。
2.队列数据结构
（1）队列是一种采用先进先出（first in,first out FIFO）策略的对元素操作的动态集合。
（2）队列上的INSERT操作称为入队（ENQUEUE），DELETE操作称为出队（DEQUEUE）。
（3）队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有对头（head）和对尾（tail），当有一个元素入对时，它被放在队尾的位置，就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在对头的那个，就像排在队伍前面等待最久的那个顾客一样。

源代码：

/*******************************************************
* queue.h
*
* A simple queue implemented by C++ template class.
*
*******************************************************/

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include<stdlib.h>
#include<cstdlib>

using namespace std;

namespace itlab
{
/**
* Queue Node
**/
//#define QUEUE_INIT_SIZE 100 //队列初始化大小
//#define QUEUE_INCREMENT 10 //队列空间不够时一次申请大小

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> &q);
// Queue & operator=(const Queue<Type> &q);

inline bool isEmpty () const; //队列是否为空
inline void makeEmpty(); //清空队列
//inline bool isFull() const; //队列是否已满
//int size () const; //队列中元素的个数
inline void enqueue( const Type &x ); //插入一个元素
inline void dequeue( Type &x ); //弹出一个元素
inline void getFront( Type &x); //得到对头元素

private:
LinkNode<Type> *front;//指向头结点的指针,front->next->data 是队头的第一个元素
LinkNode<Type> *rear; //指向队尾（最后添加的一个元素）的指针

inline void handleUnderflow();

};

#include "queue-impl.h"
}
//namespace itlab

#endif
// QUEUE_H

//---------------------------------------------------------------------------------------------------------------------//---------------------------------------------------------------------------------------------------------------------

/*******************************************************
* queue-impl.h
*
* Implementation for Queue class.
*
*******************************************************/

/**
* constructors and destructor
**/
template <typename Type>
Queue<Type>::Queue():front(NULL), rear(NULL)
{

}

template <typename Type>
Queue<Type>::~Queue()
{
makeEmpty();
}

/**
* If the queue 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 the 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 am 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.
*
*******************************************************/
#include <iostream>
#include <string>
#include "queue.h"
#include <stdlib.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(int argc, char** argv) {
Student stu;
Queue<Student> q;
Student students [3] = {
Student(11, "ZhangMing", "Information"),
Student(12, "HuZhaoJun"),
Student(13, "ZhangYuYang", "AutoControl")
};

cout << "入队列顺序为:" << endl << endl;
for(int i=0; i<3; i++){
cout << " " << students[i].stuNum << "\t" << students[i].stuName << "\t"
<< students[i].department << endl;
q.enqueue( students[i] );
}

cout << "对首元素为:" << endl << endl;
q.getFront( stu );
cout << " " << stu.stuNum << "\t" << stu.stuName << "\t"
<< stu.department << endl;
cout << endl;

cout << "出队列顺序为:" << endl << 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 << endl;

cout << endl << endl;
return 0;
}