队列是一种先进先出的数据结构，因和平常生活中的排队流程一样因此被称为队列。操作逻辑和栈刚好相反。

常用操作：

• enqueue: 元素入队
• dequeue: 首元素出队
• size: 返回队列中元素的个数
• empty: 判断队列是否为空
• front: 返回队首元素

它有两个指针分别指向队列开头和结尾，出队和入队的流程为：

队列的实现方式多样，也可以和栈一样通过数组、vector等方式实现，这里就采用最常用的链式节点实现。

一、队列节点

typedef unsigned int uint;

template <typename T>
class CQueueNode {
public:
    CQueueNode();
    CQueueNode(T data, CQueueNode<T>* next = 0);
    ~CQueueNode();
    T getData() const;
    CQueueNode<T>* getNext() const;
    void setData(T data);
    void setNext(CQueueNode<T>* next);
private:
    T data;
    CQueueNode<T>* next;
};

template <typename T>
CQueueNode<T>::CQueueNode() {
    next = 0;
}

template <typename T>
CQueueNode<T>::CQueueNode(T data, CQueueNode<T>* next) : data(data), next(next) {
}

template <typename T>
CQueueNode<T>::~CQueueNode() {
    // 如果需要删除节点时把后面的所有节点都删除可以添加下面语句
    //if (next) delete next;
    next = 0;
}

template <typename T>
T CQueueNode<T>::getData() const {
    return data;
}

template <typename T>
CQueueNode<T>* CQueueNode<T>::getNext() const {
    return next;
}

template <typename T>
void CQueueNode<T>::setData(T data) {
    this->data = data;
}

template <typename T>
void CQueueNode<T>::setNext(CQueueNode<T>* next) {
    this->next = next;
}

二、队列

#include "node.h"

template <typename T>
class CQueue {
public:
    CQueue();
    ~CQueue();
    T enqueue(const T data);
    T dequeue();
    uint size() const;
    bool empty() const;
    T front() const;
private:
    CQueueNode<T> *head, *tail;
    uint len;
};

template <typename T>
CQueue<T>::CQueue() : len(0), tail(0), head(0) {
}

// 入队操作
template <typename T>
T CQueue<T>::enqueue(const T data) {
    CQueueNode<T>* temp = new CQueueNode<T>(data);

    // 判断队列是否为空
    if (!tail)  head = tail = temp;
    else {
        tail->setNext(temp);
        tail = temp;
    }

    len++;
    return temp->getData();
}

// 析构函数
template <typename T>
CQueue<T>::~CQueue() {
    CQueueNode<T>* p = head, *q;
    // 删除所有的节点
    while (p) {
        q = p->getNext();
        delete p;
        p = q;
    }

    head = 0, tail = 0, len = 0;
}

// 出队操作
// 出队时，应先通过empty()判断队列是否为空然后再操作
template <typename T>
T CQueue<T>::dequeue() {
    // 实际不应有这一句，应该主动避免该问题
    // 因为当T是string时且head==0时，程序会崩溃
    if (!head) return 0;
    T data = head->getData();
    CQueueNode<T>* dNode = head;

    if (head == tail) 
        // 只有一个元素
        head = tail = 0;
    else // 有多个元素
        head = dNode->getNext();

    delete dNode;
    len--;
    return data;
}

template <typename T>
uint CQueue<T>::size() const {
    return len;
}

template <typename T>
bool CQueue<T>::empty() const {
    return len == 0;
}

// 返回第一个元素
template <typename T>
T CQueue<T>::front() const {
    // 和出队操作一样，此处应该主观避免head为空的情况
    return head ? head->getData() : 0;
}