队列的链式存储结构

??? 队列也是一种特殊的线性表，只不过是一头进另一头出罢了。

?

??? 下面是队列的基本操作。

?

/* queue.h */#ifndef QUEUE_H#define QUEUE_H#include <iostream>#include <string.h>using namespace std;#define TYPE inttypedef struct _Node {    TYPE data;    struct _Node* next;} Node, *Pnode;class Queue {private:    Pnode front;    Pnode rear;public:    Queue();    ~Queue();    bool InitQueue();    void DestroyQueue();    void ClearQueue();    bool QueueEmpty();    int QueueLength();    bool GetHead(TYPE&);    bool EnQueue(TYPE);    bool DeQueue(TYPE&);    void QueueTraverse();};#endif

/* queue.cpp */#include "queue.h"Queue::Queue() {    cout<<"Constructor"<<endl;    front = NULL;    rear = NULL;}Queue::~Queue() {    cout<<"Destructor"<<endl;    DestroyQueue();}bool Queue::InitQueue() {    Pnode p = new Node;    if (!p) {        cout<<"Init Queue fail"<<endl;        return false;    }    front = p;    rear = p;    return true;}void Queue::DestroyQueue() {    if (!rear) {        return;    }    while (front) {        Pnode p = front;        front = front->next;        delete p;    }    rear = NULL;}void Queue::ClearQueue() {    if (!rear) {        cout<<"Queue not exist"<<endl;        return;    }    while (front != rear) {        Pnode p = front;        front = front->next;        delete p;    }    memset(front, 0, sizeof(Node));}bool Queue::QueueEmpty() {    if (!rear) {        cout<<"Queue not exist"<<endl;        return false;    }    if (front == rear) {        return true;    }    return false;}int Queue::QueueLength() {    if (!rear) {        cout<<"Queue not exist"<<endl;        return 0;    }    int n = 0;    Pnode p = front;    while (p != rear) {        n++;        p = p->next;    }    return n;}bool Queue::GetHead(TYPE& e) {    if (!rear) {        cout<<"Queue not exist"<<endl;        return false;    }    if (front == rear) {        return false;    }    e = front->next->data;    return true;}bool Queue::EnQueue(TYPE data) {    if (!rear) {        cout<<"Queue not exist"<<endl;        return false;    }    Pnode p = new Node;    if (!p) {        cout<<"EnQueue fail"<<endl;        return false;    }    p->data = data;    rear->next = p;    rear = p;    return true;}bool Queue::DeQueue(TYPE& e) {    if (!rear) {        cout<<"Queue not exist"<<endl;        return false;    }    if (front == rear) {        cout<<"debug empty"<<endl;        return false;    }    e = front->next->data;    Pnode p = front->next;    front->next = front->next->next;    if (p == rear) {        rear = front;    }    delete p;    return true;}void Queue::QueueTraverse() {    if (!rear) {        cout<<"Queue not exist"<<endl;        return;    }    Pnode p = front->next;    while (p) {        cout<<p->data<<" ";        p = p->next;    }    cout<<endl;}

?