数据结构——线性结构（7）——链队列的实现

链队列的实现

头文件：

/*
 *这部分文件实现我们之前所使用的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;
}

测试结果：