c++实现queue

方法

使用链表实现，采用了双向队列。双向队列的时间复杂度非常的小。出队列和进队列的复杂度都是O(1)

实现

#ifndef QUEUE_H1
#define QUEUE_H1
#include<iostream>
using namespace std;
template<typename T>
class Queue
{
public:
    Queue();
    ~Queue();
    bool empty() const;
    int size() const;
    void clear();
    void push(const T & node);
    void pop();
    T&  front();
    T   front() const;
private:       //也可以直接用来链表list直接构造
    struct  QueueNode
    {
        T data;
        QueueNode* next;
        QueueNode(const T& Newdata, QueueNode* nextnode=NULL) :data(Newdata), next(nextnode)
        { }
       // QueueNode() = default;
    };
    QueueNode * Front;  //队头指针
    QueueNode * rear;  // 队尾指针
    int count;
};
//此处不设头节点
template<typename T>
Queue<T>::Queue() :Front (NULL),  rear (NULL), count(0)
{}
template<typename T>
Queue<T>::~Queue()
{
    clear();
}
template<typename T>
void Queue<T>::push(const T & node)
{
    if(Front==NULL)
        Front=rear=new QueueNode(node);
    else
    {
     QueueNode * newqueuenode = new QueueNode(node);
    rear->next = newqueuenode;
    rear = newqueuenode;
    }
    count++;
}
template<typename T>
bool Queue<T>::empty() const
{
    return Front==NULL;
}

template<typename T>
int Queue<T>::size() const
{
    return count;
}

template<typename T>
void Queue<T>::clear()
{
    while (Front)
    {
        QueueNode * FrontofQueue = Front;
        Front = Front->next;
        delete FrontofQueue;
    }
    count = 0;
}

template<typename T>
void Queue<T>::pop()
{
    if (empty())
    {
        cerr << "Error, queue is empty!";
    }
    QueueNode * FrontofQueue = Front;
    Front = Front->next;
    delete FrontofQueue;
    count--;
}

template<typename T>
T& Queue<T>::front()
{
    if (empty())
    {
        cerr << "Error, queue is empty!";
    }
    return Front->data;
}

template<typename T>
T Queue<T>::front() const
{
    if (empty())
    {
        cerr << "Error, queue is empty!";
    }
    return Front->data;
}
#endif // QUEUE_H1