链队列的实现
头文件：
/*
*这部分文件实现我们之前所使用的queue类
*它主要的原理为 后进后出（LILO）
*/
#ifndef _Queue_h
#define _Queue_h
/*
*类型: Queue<ValueType>
*此类建立一个称为队列的线性结构，其中仅从一端添加和删除值。
*这个规定产生了一个（LILO）的行为，它是队列的定义特征。
*基本操作是enqueue（添加元素到尾部）和dequeue（把元素从头部删除）。
*/
template <typename ValueType>
class Queue{
public:
/*
*构造函数：Queue
*用法：Queue <ValueType> queue
*-----------------------------
*初始化一个空队列
*/
Queue();
//析构函数
~Queue();
/*
*方法：size（）
*用法：int n = queue.size();
*--------------------------
*返回队列中元素的个数
*/
int size();
/*
*方法：isEmpty（）
*用法：queue.isEmpty();
*--------------------------
*判断队列中元素是否为空
*/
bool isEmpty();
/*
*方法：clear（）
*用法：queue.clear();
*--------------------------
*清空队列中的所有元素
*/
void clear();
/*
*方法：enqueue（）
*用法：queue.enqueue();
*--------------------------
*向队尾插入一个元素
*/
void enqueue(ValueType elem);
/*
*方法：pop（）
*用法：queue.dequeue();
*--------------------------
*移除队头的一个元素,并返回其值，如果队空 则返回一个错误
*/
ValueType dequeue();
/*
*方法：peek（）
*用法：queue.peek();
*--------------------------
*返回队头的值，但是不移除，peek 偷看的意思,如果队空 则返回一个错误
*/
ValueType peek();
#include "queuepriv.h" //私有成员部分
};
#include "queueimpl.cpp" //将实现文件包含进来
#endif
隐藏头文件:queuepriv.h
/*
*这个文件保存的是Queue.h的私有部分
*我们这个时候用顺序队列。也就是用数组来实现我们的队列
*这样的队列我们称为顺序队列
*/
private:
/*队列的链式结构*/
struct Cell{
ValueType data;
Cell *link;
};
/*实例化变量*/
Cell *head; //头指针
Cell *tail; //尾指针
int count; //记录队列元素的总数
/* Make it illegal to copy queues */
Queue(const Queue & value) { }
const Queue & operator=(const Queue & rhs) { return *this; }
实现文件：queueimpl.cpp
#ifdef _Queue_h
#include "error.h"
/*构造函数,创建一个空队列*/
template<typename ValueType>
Queue<ValueType>::Queue(){
head = tail = NULL; //队空的条件
count = 0;
}
/*析构函数*/
template<typename ValueType>
Queue<ValueType>::~Queue(){
clear();
}
/*返回队列的长度*/
template<typename ValueType>
int Queue<ValueType>::size(){
return count;
}
/*判断队列是否为空*/
template<typename ValueType>
bool Queue<ValueType>::isEmpty(){
return count == 0;
}
/*清空队列操作*/
template<typename ValueType>
void Queue<ValueType>::clear(){
while (count > 0)
{
dequeue();
}
}
/*入队列操作
*分为两步：1. 新建节点，并赋值
2. 添加到队列中，考虑队列此时是否为空
*/
template<typename ValueType>
void Queue<ValueType>::enqueue(ValueType elem){
Cell *cell = new Cell;
cell -> data = elem; //赋值
cell -> link = NULL; //因为添加的是队尾，所以指向下一位的指针为空指针
/*考虑，如果此刻的队列为空队列，那么我们新建的节点理所应当成为我们的队列的头指针*/
if (head == NULL)
{
head = cell;
}else{
tail -> link = cell;
}
tail = cell; //将为指针的指向转向新建的尾节点
count++;
}
/*出队列操作
*分为三步：1.检测队列是否为空
2.建立临时指针指向要出队的节点
3.头指针指向后移，并删除临时指针
*/
template<typename ValueType>
ValueType Queue<ValueType>::dequeue(){
/*执行操作之前检测队列是否为空*/
if (isEmpty())
{
error("dequeue: Attempting to dequeue an empty queue");
}
/*出队操作*/
Cell *cell = head; //建立一个临时指针指向我们的头节点
ValueType result = cell -> data;//记录当前的数据信息
head = cell -> link;//头指针指向后移
if(head == NULL) tail = NULL;//当队列的头指针为空时，表明此刻的队列为空
count--;
delete cell;//删除临时节点
return result;
}
/*返回队头的值*/
template<typename ValueType>
ValueType Queue<ValueType>::peek(){
if (isEmpty())
{
error("Attempting to peek at an empty queue");
}
return head -> data;
}
测试文件：
#include <iostream>
#include "Queue.h"
using namespace std;
int main(){
Queue<int> myqueue;
for (int i = 0; i < 10; i++)
{
myqueue.enqueue(i);
}
cout << "队伍的长度为： " << myqueue.size();
cout << endl;
cout << "队头为： " << myqueue.peek() << endl;
myqueue.enqueue(10);
cout << "将10加入队列后，长度为：" <<myqueue.size() << endl;
myqueue.dequeue();
cout << "执行出队操作后的队头为：" << myqueue.peek() << endl;
return 0;
}
测试结果：
