线性表：链式队列算法实现

àì夳堔傛蜴生んèń 2022-05-31 13:11 146阅读 0赞

# 链式队列介绍 #

**队列是一种受限制的线性表，有先进先出的特性**。那么既然是线性表那肯定对应有2种不同的存储结构咯。**链式队列呢，就是采用链式存储结构构成的队列**。所以呢本次**编写链队列呢 采用以前写的企业级单链表形式编写。不知道企业级单链表？请看[数据结构与算法：企业级链表实现（超详细）][Link 1]，感觉这种思想超赞，你值得拥有。**

# 链队列相关算法接口 #

**同样采用LinkQueue类型也就是void\*类型返回给用户，对用户隐藏底层实现。**

#pragma once
    #ifndef __LINKQUEUE_H__
    #define __LINKQUEUE_H__
    typedef void* LinkQueue;
    typedef enum { FALSE ,TRUE } Boolean;
    
    //初始化
    LinkQueue Init_LinkQueue();
    
    //入队
    Boolean Push_LinkQueue(LinkQueue queue, void* data);
    
    //出队
    void* Pop_LinkQueue(LinkQueue queue);
    
    //返回队头元素
    void* Front_LinkQueue(LinkQueue queue);
    
    //返回队尾元素
    void* Rear_LinkQueue(LinkQueue queue);
    
    //返回队元素个数
    int Size_LinkQueue(LinkQueue queue);
    
    //返回队是否为空
    int IsEmpty_LinkQueue(LinkQueue queue);
    
    //销毁队列
    void Destroy_LinkQueue(LinkQueue queue);
    #endif

# 链队列相关算法实现 #

**代码没有什么难的，但是有一点尤其要注意：我们初始化队列的时候，队尾rear指针指向头结点，这样是为了让入队列操作是能通用。那么当我们出队列时候，要判断当前队列是否为空，为空的话，我门的尾指针重新指向头结点。**

#include "LinkQueue.h"
    #include <stdlib.h>
    
    typedef struct QueueNode
    {
    	struct QueueNode * next;
    }QueueNode;
    
    typedef struct LQueue
    {
    	QueueNode front;
    	QueueNode* rear;
    	int size;
    }LQueue;
    
    //初始化
    LinkQueue Init_LinkQueue()
    {
    	LQueue* queue = malloc(sizeof(LQueue));
    	queue->size = 0;
    	queue->front.next = NULL;
    	queue->rear = &queue->front;
    	return queue;
    }
    //入队 从队尾入队
    Boolean Push_LinkQueue(LinkQueue queue, void* data)
    {
    	if (queue == NULL || data == NULL)
    	{
    		return FALSE;
    	}
    	QueueNode* node = data;
    	LQueue* myQueue = queue;
    	myQueue->rear->next = node;
    	node->next = NULL;
    	myQueue->rear = node;
    	myQueue->size++;
    	return TRUE;
    }
    
    //出队 从队头出队
    void* Pop_LinkQueue(LinkQueue queue)
    {
    	LQueue* myQueue = queue;
    	if (queue == NULL || myQueue->size == 0)
    	{
    		return NULL;
    	}
    	QueueNode* del = myQueue->front.next;
    	myQueue->front.next = del->next;
    	if (del->next == NULL)
    	{
    		myQueue->rear = &myQueue->front;
    	}
    	myQueue->size--;
    	return del;
    }
    
    //返回队头元素
    void* Front_LinkQueue(LinkQueue queue)
    {
    	LQueue* myQueue = queue;
    	if (queue == NULL || myQueue->size == 0)
    	{
    		return NULL;
    	}
    	QueueNode* front = myQueue->front.next;
    
    	return front;
    	
    }
    
    //返回队尾元素
    void* Rear_LinkQueue(LinkQueue queue)
    {
    	LQueue* myQueue = queue;
    	if (queue == NULL || myQueue->size == 0)
    	{
    		return NULL;
    	}
    	return myQueue->rear;
    }
    
    //返回队元素个数
    int Size_LinkQueue(LinkQueue queue)
    {
    	LQueue* myQueue = queue;
    	if (queue == NULL)
    	{
    		return 0;
    	}
    	return myQueue->size;
    }
    
    //返回队是否为空
    Boolean IsEmpty_LinkQueue(LinkQueue queue)
    {
    	if (Size_LinkQueue(queue) == 0)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }
    
    //销毁队列
    void Destroy_LinkQueue(LinkQueue queue)
    {
    	LQueue* myQueue = queue;
    	if (queue == NULL)
    	{
    		return;
    	}
    	free(queue);
    }

# 代码运行检测 #

## Main.c测试代码 ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkQueue.h"
    //测试 数据
    typedef struct Person
    {
    	void* node;
    	char name[64];
    	int age;
    }Person;
    
    int main(int argc, char *argv[])
    {
    	Person p1 = {NULL,"Lily",11 };
    	Person p2 = {NULL,"Laymond",21 };
    	Person p3 = {NULL,"John",31 };
    	Person p4 = {NULL,"Leo",41 };
    	Person p5 = {NULL,"Zeo",51 };
    	LinkQueue queue = Init_LinkQueue();
    	Push_LinkQueue(queue, &p1);
    	Push_LinkQueue(queue, &p2);
    	Push_LinkQueue(queue, &p3);
    	Push_LinkQueue(queue, &p4);
    	Push_LinkQueue(queue, &p5);
    	printf("队头元素:name=%s,age=%d\n", ((Person*)Front_LinkQueue(queue))->name, ((Person*)Front_LinkQueue(queue))->age);
    	printf("队尾元素:name=%s,age=%d\n", ((Person*)Rear_LinkQueue(queue))->name, ((Person*)Rear_LinkQueue(queue))->age);
    	printf("队列的元素个数:%d\n", Size_LinkQueue(queue));
    	Person* p = NULL;
    	printf("将队列的元素依次出队\n");
    	while (!IsEmpty_LinkQueue(queue))
    	{
    		p = Pop_LinkQueue(queue);
    		printf("name=%s,age=%d\n", p->name, p->age);
    	}
    	printf("队列的元素个数:%d\n", Size_LinkQueue(queue));
    	Destroy_LinkQueue(queue);
    	return 0;
    }

## 运行结果 ##

![20180225232924718][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79342970
[20180225232924718]: /images/20220531/46a740b13e024a0383759f15971d3e40.png