链式队列的表示和实现
和栈相反，队列是一种先进先出的线性表，它只允许在表的一端删除元素，在表的另一段插入元素。和线性表相识，队列也有两种存储表示，用链表表示的队列叫链队列。
名词解释
队列
- 队列是一种先进先出的线性表，它只允许在表的一端删除元素，在表的另一段插入元素。
链式队列的存储结构
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
