队列的链式存储结构

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

 

    下面是队列的基本操作。

 

/* queue.h */

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <string.h>
using namespace std;

#define TYPE int

typedef 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;
}