链式队列的表示和实现

和栈相反，队列是一种先进先出的线性表，它只允许在表的一端删除元素，在表的另一段插入元素。和线性表相识，队列也有两种存储表示，用链表表示的队列叫链队列。

名词解释

队列

• 队列是一种先进先出的线性表，它只允许在表的一端删除元素，在表的另一段插入元素。

链式队列的存储结构

typedef struct QNode {
    
    ElemType data;
    struct QNode *next;
} QNode;

typedef struct {
    
    QNode *front;   //队列头指针
    QNode *rear;    //队列尾指针
}LinkQueue;

基本操作

• Status InitLinkQueue(LinkQueue *linkQueue);

• Status DestoryQueue(LinkQueue *linkQueue);

• Status ClearQueue(LinkQueue *linkQueue);

• Status AppendElemToQueue(LinkQueue *linkQueue, ElemType elem);

• int LengthOfQueue(LinkQueue linkQueue);

• int IsEmptyQueue(LinkQueue linkQueue);

• Status GetHeadElemFromQueue(LinkQueue linkQueue, ElemType *elem);

• Status DeleteElemFromQueue(LinkQueue *linkQueue);

• Status TraverseQueue(LinkQueue linkQueue);

基本操作实现

初始化

Status InitLinkQueue(LinkQueue *linkQueue) {

    linkQueue->front = (QNode *)malloc(sizeof(QNode));
    if (!linkQueue) {
        
        return OVERFLOW;
    }
    linkQueue->rear = linkQueue->front;
    linkQueue->front->next = NULL;
    return OK;
}

因为初始化的时候就开辟了一个结点的内存，但是没有实际的值。因此队列存在的时候，队列的尾端始终保持着一个值域和指针域都为空的结点

清除队列

Status ClearQueue(LinkQueue *linkQueue) {
    
    while (linkQueue->front != linkQueue->rear) {
        
        QNode *freeNode = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(freeNode);
    }
    return OK;
}

注意：清除队列之后此队列依然可以使用，判断清除的完成的条件是linkQueue->front != linkQueue->rear而不是linkQueue->front->net == NULL这和初始化的时候有关

插入元素

Status AppendElemToQueue(LinkQueue *linkQueue, ElemType elem) {

    QNode *newNode = (QNode *)malloc(sizeof(QNode));
    if (!newNode) {
        
        return OVERFLOW;
    }
    linkQueue->rear->data = elem;
    linkQueue->rear->next = newNode;
    linkQueue->rear = newNode;
    return OK;
}

注意：因为初始化的时候创建了一个空的结点，所以插入的时候，值直接复制给linkQueue->rear所指结点的值域，linkQueue->rear所指结点的指针域指向新创建的结点，保持队列的对端是一个空的结点

销毁队列

Status DestoryQueue(LinkQueue *linkQueue) {
    
    ClearQueue(linkQueue);
    free(linkQueue->front);
    linkQueue->front = NULL;
    linkQueue->rear = NULL;
    linkQueue = NULL;
    return OK;
}

因为在清除队列的时候，保留了队列最后一个空的结点，因此在清除队列之后在释放最后一个结点的内存即可

求队列的长度

int LengthOfQueue(LinkQueue linkQueue) {

    int length = 0;
    while (linkQueue.front != linkQueue.rear) {
        
        length++;
        linkQueue.front = linkQueue.front->next;
    }
    return length;
}

注意：与上面所需注意点一样，队列最后一个结点为空结点，因此最后一个结点不能算入队列的长度

是否为空队列

int IsEmptyQueue(LinkQueue linkQueue) {

    if (linkQueue.front == linkQueue.rear) {
        
        return 1;
    } else {
        
        return 0;
    }
}

得到队列的头元素

Status GetHeadElemFromQueue(LinkQueue linkQueue, ElemType *elem) {
    
    int isEmpty = IsEmptyQueue(linkQueue);
    if (isEmpty == 1) {
        
        return ERROR;
    } else {
        
        *elem = linkQueue.front->data;
        return OK;
    }
}

删除元素

Status DeleteElemFromQueue(LinkQueue *linkQueue) {
    
    int isEmpty = IsEmptyQueue(*linkQueue);
    if (isEmpty) {
        
        return ERROR;
    } else {
        
        QNode *freeNode = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(freeNode);
        return OK;
    }
}

注意：因为队列的特殊性，所以删除元素只能删除头元素

输出元素

Status TraverseQueue(LinkQueue linkQueue) {
    
    while (linkQueue.front != linkQueue.rear) {
        
        printf("elem is %d \n", linkQueue.front->data);
        linkQueue.front = linkQueue.front->next;
    }
    return OK;
}

小结

队列在软件设计方面应用非常广泛，比如按顺序发送网络请求，数据包或者下载等操作

欢迎讨论

Email:huliuworld@yahoo.com

Github:https://github.com/LHCoder2016/DataStructure