队列的链式存储实现

l链式队列的形式如下:

front->Data1->Data2->Data3->...->DataN(rear)

front存储队头数据节点的前一个节点地址，rear存储队尾数据节点的地址

队列结构如下:

#define OK        1
#define ERROR     0
#define OVERFLOW -1

typedef int Status;
typedef int QElemType;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode;
typedef struct
{
    QNode *front;//指向队头的前一个指针
    QNode *rear;//指向队尾
}LinkQueue;

具体实现如下:

void InitQueue(LinkQueue *Q)
{
    assert(Q);

    Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
    if (!Q->front)
        exit(OVERFLOW);
    Q->rear->next = NULL;
}

void DestroyQueue(LinkQueue *Q)
{
    assert(Q);
    QNode *tmp;

    tmp = Q->front;
    while (tmp)
    {
        Q->front = tmp->next;
        free(tmp);
        tmp = Q->front;
    }
    //Q->front已经为NULL了
    Q->rear = NULL;
}

Status QueueEmpty(LinkQueue *Q)
{
    assert(Q);

    return Q->rear == Q->front;
}

void EnQueue(LinkQueue *Q, QElemType e)
{
    assert(Q);
    QNode *tmp;

    tmp = (QNode *)malloc(sizeof(QNode));
    if (!tmp)
        exit(OVERFLOW);
    tmp->data = e;
    tmp->next = NULL;
    Q->rear->next = tmp;
    Q->rear = tmp;
}

Status DeQueue(LinkQueue *Q, QElemType *e)
{
    assert(Q);
    QNode *tmp;

    if (QueueEmpty(Q))
        return ERROR;
    
    tmp = Q->front;
    //因为front存储队头的前一个节点
    //所以要Q->front=tmp->next得到队头节点
    Q->front = tmp->next;
    free(tmp);
    if (e)
        *e = Q->front->data;

    return OK;
}

Status GetHead(LinkQueue *Q, QElemType *e)
{
    assert(Q&&e);

    if (QueueEmpty(Q))
        return ERROR;
    *e = Q->front->next->data;
    return OK;
}

void QueueTraverse(LinkQueue *Q, void(*visit)(QElemType *))
{
    assert(Q&&visit);
    QNode *tmp;

    tmp = Q->front->next;
    while (tmp)
    {
        visit(&tmp->data);
        tmp = tmp->next;
    }
}

队列的链式存储实现

相关推荐