队列 c语言实现

雨点打透心脏的1/2处 2022-08-04 10:51 184阅读 0赞

**1.导言**

栈和队列是两种常见的线性表，栈因为只能在表的一端进行插入和删除，这种结构决定了栈后进先出的特性，队列也是一种受限的线性表，队列只能在表的一端进行插入，在表的另一端进行删除。允许插入的一端叫做队尾（rear）,允许删除的一端被称之为队头（front）。这种结构决定了队列具有先进先出（FIFO）的特性.对队列来说，在我们日常生活中，随处可见。去食堂排队打饭，最早排队的人，最先拿着饭菜离开，典型的先进先出（当然了，对于插队这种事情，我也就呵呵了）、队列在程序设计中也经常出现，如实时系统中的事件处理，操作系统中的作业排队等。在我们学习数据结构过程中，对于任何一种数据结构我们必须从以下角度去考虑：数据与数据之间的逻辑关系，数据间的关系怎么表示，数据和数据间的关系怎么在计算机中表示。这也就是数据结构的逻辑结构，和物理结构（也叫数据的存储结构）。队列（queue）就逻辑结构而言，是一种一对一的线性关系，是受限的线性表，只能在表尾进行插入，在表头进行删除。而数据在计算机中存储，总共用两种方式，一种是顺序表,用一块连续的内存单位，来保存数据。这里数据间的关系是：逻辑结构相邻的数据，物理存储位置也相邻。另一种是链式存储，链式存储是把数据和指向数据关系的指针封装成一个节点，保存数据的叫做数据域，能体现数据间的关系的叫做指针域。

**2.队列的定义**  
队列（queue）是一种先进先出（first in first out）（FIFO）的线性表。它只允许在表的一端进行插入，在表的另一端、进行删除.允许插入的一端称之为队尾（rear）,允许删除的一端称之为队头（front）.

**3.队列的性质**  
队列只允许在表尾进行插入，在表头进行删除，所以，队列的这种结构决定了队列具有先进先出的性质，凡是具有先进先出特性的可以考虑用队列来实现。

**4.队列的链式表示**  
队列是一种受限的线性表，所以队列在计算机中也有两种表示和存储方式：（1）顺序表示（2）链式表示，这里用链式表示来存储。用链表表示的队列称为链队列。因为队列在表尾进行插入 ，在队头进行删除，所以一个队列显然需要一个指向队尾和队头的指针（分别称之为队尾指针，和队头指针）才能唯一确定。和单链表一样，为了操作方便，我们给链队列设置一个头节点，并令头指针指向了头节点，所以链队为空的判断条件是头指针和尾指针都指向了头节点。队列的插入和删除就是线性表的插入和删除的特需情况，只允许在表头进行删除，在表尾进行插入。

**5.实现代码**

//Queue.h
    #ifndef QUEUE_H
    #define QUEUE_H
    typedef int DataType;
    
    //-----------------------单链表队列节点（QNode）------------------------------//
    
    typedef struct QNode{
    	
    	DataType data;//存放数据的数据域
    	QNode *next;//存放数据间关系的指针域next 指向下一节点
    
    }QNode;
    
    //-----------------------单链表队列--------队列的链式存储结构----------------//
    typedef struct LinkQueue{
    	QNode *front;//队头指针指向队头
    	QNode *rear;//队尾指针，指向队尾
    	QNode *head;//队列头节点指针，数据域为空，指针域指向数据的第一个数据元素节点（首元节点），当队列为空时（front == rear == head）设置此节点为了方便队列的各种操作
    
    }LinkQueue;
    
    //-----------------------单链表队列的基本操作-----------为了插入方便设置了头节点------//
    //构造队列：init_queue(LinkQueue *queue):分配内存，初始化队列
    bool  init_queue(LinkQueue *queue);
    
    //队列判空：is_queue_empty(const LinkQueue * const queue):判断队列是否为空，front == rear == head;
    bool is_queue_empty(const LinkQueue * const queue);
    
    //队列长度：queue_length( const LinkQueue * const queue);
    int queue_length( const LinkQueue * const queue);
    
    //从队尾进行插入; queue_insert( LinkQueue *queue , const DataType data)
    bool queue_insert( LinkQueue *queue, const DataType data);
    
    //遍历队列,访问队列中的所有节点的数据域: bool queue_traverse(const LinkQueue * const queue)
    bool queue_traverse(const LinkQueue * const queue);
    
    
    //获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )
    DataType front_data( const  LinkQueue* const queue);
    
    //从队列中删除队头 delete_queue_front( LinkQueue *queue);
    bool delete_queue_front( LinkQueue *queue);
    
    //将队列清空 clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空
    bool clear_queue( LinkQueue *queue);
    
    //销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
    //bool destroy_queue(LinkQueue *queue);
     bool destroy_queue(LinkQueue *queue);
    
    #endif

//---------------------------队列基本操作算法描述(c语言实现)------------------//
    #include"Queue.h"
    #include<stdlib.h>
    #include<stdio.h>
    
    //--------------构造队列：init_queue(LinkQueue *queue):分配内存，初始化队列--------------//
    //功能：构造一个空队列queue
    //函数参数：queue 为指向队列的指针
    //返回值：构造成功 返回true(1),构造失败 返回false(0)
    //时间复杂度:O(1)
    //测试用例{queue == NULL ,queuef != NULL}
    
    bool  init_queue(LinkQueue *queue){
    
    	if( queue == NULL)//当参数为指针时要判空
    		exit(-1);//为空，进程结束，异常退出
    
    	//生成一个QNode 类型的头节点（此节点数据域data不包含任何数据，指针域next指向队列的第一个节点，
    	//当队列为空时（是指队列任何已经存在，但队列中没有任何数据）queue->rear == queue->front == head;
    	
    	queue->head =(QNode*)malloc(sizeof(QNode));//为队列生成一个头节点（方便插入和删除）
    	queue->head->data = 0;
    	queue->head->next = NULL;//节点必须初始化 
    
    	if( queue->head == NULL )//内存分配失败，进程异常退出
    		exit(-1);
    
    	else{
    		queue->front = queue->rear = queue -> head;//构造了一个空队列
    		return true;
    	}
    
    }
    
    
    
    //------------------队列判空：is_queue_empty(const LinkQueue * const queue):判断队列是否为空，front == rear == head;----------//
    //算法说明：判断队列是否为空，为空的条件是( queue->front == queue->head) && (queue->rear == queue ->head)
    //参数说明：queue 为LinkQueue类型的常指针，因为在判断过程中 ，不会修改队列
    //返回值：true(1)队列为空，false(0)队列不为空
    //时间复杂度：O（1）
    //测试用例,1.{queue == NULL} 2.queue != NULL 队列中元素的个数0，1，2，3....多个
    
    bool is_queue_empty(const LinkQueue * const queue){
    
    	if( queue == NULL)//当传入参数是指针时，必须判空
    		exit(-1);//返回给系统进程异常结束
    
    	if( (queue->front == queue->head) && (queue->rear == queue->head) )//队列为空
    		return true ;
    
    	else//队列非空
    		return false;
    
    
    }
    
    //---------------------队列长度：queue_length( const LinkQueue * const queue);-------------------//
    //函数说明：求取队列的长度，因为队列是以单链表的形式存在，并且在数据结构中，增加了头节点，所以队列的
    //长度是从头节点的下一节点开始计算 一直到队尾（包括队尾），终止条件是 遍历指针指向NULL
    //参数说明：因为求队列的长度只是对队列的遍历，没有改变队列的任何值，所以应该声明为const 指针
    //返回值：返回队列中的元素个数
    //时间复杂度：O（n），需要遍历整个队列
    //测试用例1.queue == NULL ,2.queue != NULL 队列中 有0，1，2，3....个数据元素
    int queue_length( const LinkQueue * const queue){
       
    	    if( queue == NULL)//当传入参数为指针，必须判空
    			exit(-1);//进程异常结束
    		unsigned int length = 0;
    
    		if( is_queue_empty(queue) == true )//队列为空，调用已有的函数来判断
    		{ 
    			length = 0;
    		
    		}
    		else
    		{        
    			QNode* search_node  = queue->head ->next;//定义一个遍历节点指针，用来遍历整个队列，
    			      while( search_node != NULL )       //因为头节点不包含任何数据成员，所以队列的长度
    				  {
    					  ++length;                        //应该从头节点下一结点开始算，直到节点为空   
    					  search_node = search_node->next;
    				  }             
    		}
    
    		return length;
    
    }
    
    
    //----------------------获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )-------------------------------//
    //函数说明：因为队列是从队头删除数据，在很多情况下，我们有必要知道出队的数据元素是什么
    //函数参数：因为只是取队头元素，而不是把队头元素从队列中删除（出队），此操作中队列并没有改变队列，所以应该用const 加以修饰
    //返回值：获取的队头元素 当队列为空时，异常退出
    //时间复杂度：O(1)头节点的下一节点的数据域就是队头数据元素了，并不要遍历整个队列
    //测试用例说明：queue == NULL, queue != NULL (1)队列为空（2）队列非空（有1，2，3....个数据元素）
    DataType front_data( const  LinkQueue* const queue){
    	//1.参数检测2.空队列 3.非空队列
    	if( queue == NULL)//当参数为指针类型时，得判空
    		exit(-1);//进程异常退出
    
    	if(is_queue_empty(queue))//队列为空，退出
    		exit(-2);
    	else       //队列非空，队首元素为头节点的下一结点的数据域中存储的元素
    	{
    		
    		return(queue->head->next->data);//头节点的下一结点的数据域中存储的元素
    	}
    
    }
    
    
    //-----------队尾进行插入（入队）; queue_insert( LinkQueue *queue , const DataType data)-------------//
    //函数说明：队列是只能在队头进行删除，在队尾进行插入，具有先进先出的特性，数据元素进入队列是从队尾进入的
    //参数说明：插入DataType 类型的数据 data ，因为要改变队列 所以队列queue不能用const修饰，而不能对数据data，
    //进行改变，所以数据data 要用const 修饰如果数据是用户自定义的结构体，为了效率可以考虑传指针的方式传递数据data
    //返回值：成功插入;返回true(1),插入失败 返回 false(0);
    //时间复杂度：O（1）因为是链式队列，且有队尾指针，并且是在队尾插入，所以时间复杂度为常数O（1）
    //测试用例：queue == NULL ,queue != NULL 时已经有0，1，2，3...个数据元素
    bool queue_insert( LinkQueue *queue, const DataType data){
    	//1.参数检测2.分配内存，3.封装4.插入4.有哪些改变
    	if( queue == NULL )//当传入参数为指针变量时，必须得判空
    		exit(-1); //异常退出
        QNode *new_node = (QNode*)malloc(sizeof(QNode));//为新节点分配内存
    	if( new_node == NULL )//内存分配失败，进程异常退出
    		exit(-1);
    	else
    	{ 
    		//将传入的数据封装为队列节点
    		new_node->data = data;//数据域 
    		new_node ->next = NULL;
    
    		if(is_queue_empty(queue) )//队列为空
    		{
    			new_node->next = queue->head->next;
    			queue->head->next = new_node;//队列为空时，头指针的next需要改变
    			queue->rear = new_node;//将尾指针指向新的尾部
    		}
    		else//队列不为空
    		{
    			new_node->next = queue->rear->next;
    			queue->rear->next = new_node;//将新的节点new_node 插入队尾
    			queue->rear = new_node;//尾指针rear指向新的尾部
    		}
    
    		return true;
    	}
    	
    }
    
    
    //-------访问节点的数据域,并显示在屏幕上void visit(const QNode * const node)—————————————————————---//
    //函数说明：访问队列节点中的数据域，并且在屏幕上显示数据域中的值
    //参数说明：传递一个QNode类型的指针变量，node 因为只是对节点进行访问，而并没有改变节点所以得用const修饰
    //返回值：void
    //时间复杂度;O(1)
    void visit(const QNode* const node){
    	//1.判空2.显示
    	if( node == NULL )//当参数为指针时，必须得判空
    		exit(-1);
    	DataType data = node->data;//声明一个DataType类型的变量 data 来保存节点node数据域中的数据
    	printf("%d  ",data);
    }
    
    //-----------遍历队列 bool queue_traverse(const LinkQueue * const queue)--------访问队列中的所有节点的数据域--------------//
    //函数说明：访问从头节点的下一结点（也就是队列的首员节点）的数据域
    //参数：因为没对队列进行改变，所有queue应该用const 修饰
    //返回值：成功返回 true(1)失败 返回false(0)
    //时间复杂度：O(n） 因为要对从头到尾访问队列中的每个节点
    bool queue_traverse(const LinkQueue * const queue){
    	//1.参数检测(空)2.目前节点3.遍历4.节点访问函数（尽量把功能和显示函数分离）
    	if( queue == NULL )//当传入参数为指针时，判空
    		exit(-1);//异常退出
    
    	if( is_queue_empty(queue))//队列为空，无法遍历
    		exit(-2);
    	else     //队列非空,从首元节点开始逐个访问
    	{
    
    	QNode *now_node = queue->head->next;//首元节点
    	while(now_node != NULL)
    	{
    		visit(now_node);
    		now_node = now_node->next;
    	}
    
    	return true;
    	}
    }
    
    
    
    //-------------------从队列中删除队头 delete_queue_front( LinkQueue *queue)------------------------//
    //函数说明：队列是一种只能在表尾进行插入（入队），在表头进行删除的（出队）线性表，所以队列进行删除时，队尾不需要改变，
    //当队列中只有一个数据元素时，队头和队尾都需要改变
    //参数说明：queue不能为空，当删除空队列时，进程异常退出 exit(-2)
    //返回值：成功删除队头（出队）返回true(1),否则返回false
    //时间复杂度：O(1)
    //测试用例 queue == NULL ,queue != NULL (1)队列为空，异常退出exit(-2)(2)队列只有一个数据元素rear ，head 都要改变（3）队列有多个数据元素 改变front ,尾指针rear不需要改变
    bool delete_queue_front( LinkQueue *queue){
    	//1.参数检测 2.队空 3.队非空（1.只有一个数据元素，2.有多个数据元素）4.释放节点所分配的内存
    	if( queue == NULL )
    		exit(-1);
    
    	if(is_queue_empty(queue))//队列为空，异常退出exit(-2)
    		exit(-2);
    	else           //队列非空
    	{
    		QNode *old_node = queue->head->next;//指向要出队的节点
    		if( (queue_length(queue) == 1) )//队列只有一个数据元素 front ,rear,head 都需改
    		{
    			queue->head->next == NULL;//队列为空，front == rear ==head
    			queue->front = queue->head;
    			queue->rear = queue->head;
    
    		}
    		else
    		{
    			queue->head->next = old_node->next;
    		}
    
    		free(old_node);//释放出队元素的所占有的内存，防止内存泄露
    		return true;
    	}
    }
    
    
    //将队列清空------------------clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空-----------//
    //函数说明：将队列的所有数据元素节点都释放 （也就是说，队列还存在，但已经为空）
    //参数：指向队列的指针queue,queue != NULL
    //返回值：当队列为空时 返回true(1)，否则为false(0) 
    //时间复杂度：O(n),得遍历整个队列
    //测试用例 queue == NULL ,queue ！= NULL 1.队列为空， 2.队列不为空
    bool clear_queue( LinkQueue *queue){
    	//1.判参 2.队列为空3队列不为空（遍历，删除节点，释放内存）
    	if( queue == NULL )//当参数为指针时，必须得判空
    		exit(-1);//进程结束 ，异常退出
    	
    	//队列非空时
    		while(is_queue_empty(queue) == false)//调用出队操作，清空队列
    			delete_queue_front( queue);//出队操作
    
    	//此时队列已经清空了（不管是当初是空队列，还是非空队列）
    		return true;	
    
    }
    
    //销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
    //函数说明：销毁队列，回收内存，通过调用clear_queue（queue）来实现
    //参数说明：queue != NULL
    //时间复杂度：O（n），必须释放队列中每个元素节点和头节点的内存空间
    //测试用例：queue == NULL ,queue != NULL
    bool destroy_queue(LinkQueue *queue){
    	//1.判空2.清空队列.3.释放头节点
       if( queue == NULL )//当传入参数为指针时，必须判空
    	   exit(-1);//进程异常退出
    
       clear_queue(queue);//清空队列
       free(queue->head);//这里注意了，free()只能释放malloc所分配的内存空，否则会引发错误
       return true;
    }

测试文件

//---------------------main.cpp----测试队列的基本操作---------------------------------//
    #include"Queue.h"
    #include<stdlib.h>
    #include<stdio.h>
    
    int main(void){
    
    	LinkQueue queue1;//声明一个LinkQueue 变量 queue1
    	LinkQueue *pqueue1 = &queue1;//声明一个LinkQueue 指针变量 指向queue1
    	LinkQueue *pqueue2 = NULL;
    	int data[4]={1,2,3,4};//测试数据 将要入队的数据
    
    
    //----------------------测试初始化函数init_queue(LinkQueue *queue):分配内存，初始化队列-----------------------//
    	//测试用例{queue == NULL, queue != NULL}
    
    	bool is_init = false;// 定义一个bool量，来判断队列初始化成功 true(1),失败 false 或异常退出
    	//is_init = init_queue(pqueue2);// queue == NULL 异常退出： Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
        is_init = init_queue(pqueue1);// queue == pqueue1 == &queue != NULL 
    	printf("队列已经初始化？%d\n",is_init);
    	printf("\n");
    
    
    //------------------测试队列判空函数：is_queue_empty(const LinkQueue * const queue);------------------------//
    //测试用例,1.{queue == NULL} 2.queue != NULL 队列中元素的个数0，1，2，3....多个
    
    	bool is_empty = false;//定义一个bool量，判断队列是否为空，为空 is_empty == true(1) ,不为空 is_empty == false(0)
    	//is_empty = is_queue_empty(pqueue2);//测试： queue == NULL 结果：Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 0 个 结果：is_empty == 1;
    	printf("队列为空吗：%d\n",is_empty);
    	printf("\n");
    
    	
    //---------------------测试队列长度：queue_length( const LinkQueue * const queue);-------------------//
    //测试用例1.queue == NULL ,2.queue != NULL 队列中 有0，1，2，3....个数据元素
    
    	unsigned int length;//定义一个无符号整形变量 length来记录队列的长度
    	//length = queue_length(pqueue2);//测试：queue == NULL 结果：程序“[5352] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有0个数据元素 结果：length == 0;
    	printf("队列长度为%d\n",length);
    	printf("\n");
    
    
    //----------------------测试获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )-------------------------------//
    //测试用例说明：queue == NULL, queue != NULL (1)队列为空（2）队列非空（有1，2，3....个数据元素）当数据入队时再测试
    	DataType queue_head ;//定义一个DataType类型变量 queue_head 来显示队头数据元素
    	//queue_head = front_data(pqueue2);//测试queue == NULL 结果为：程序异常退出：程序“[3108] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    	//queue_head = front_data(pqueue1);//测试queue != NULL （1）队列为空 结果为：程序异常退出 程序“[5592] Queue.exe: 本机”已退出，返回值为 -2 (0xfffffffe)。
    
    
    
    
    //---------------测试（入队）; queue_insert( LinkQueue *queue , const DataType data)-------------//
    //测试用例：queue == NULL ,queue != NULL 时已经有0，1，2，3...个数据元素
    	bool is_insert = false;//定义一个bool量来判断是否已经将数据入队
    	//is_insert = queue_insert(pqueue2,data[0]);//测试：queue == NULL 结果：程序“[2232] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    
    	//1入队
    	is_insert = queue_insert(pqueue1,data[0]);//测试：queue != NULL 队列为空，数据1入队
    	printf("%d 入队了吗? %d\n",data[0],is_insert);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 1个 结果：is_empty == 0;
    	printf("队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有0个数据元素 结果：length == 0;
    	printf("队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有1个数据 结果：
    	printf("这次的队头为:%d\n",queue_head);
    	printf("\n");
    
    
    	//2入队
    	is_insert = queue_insert(pqueue1,data[1]);//测试：queue != NULL 队列为空,数据2入队
    	printf("%d 入队了吗? %d\n",data[1],is_insert);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 2个 结果：is_empty == 0;
    	printf("队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 2;
    	printf("队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有2个数据 结果：
    	printf("这次的队头为:%d\n",queue_head);
    	printf("\n");
    
    
    	//3入队
    	is_insert = queue_insert(pqueue1,data[2]);//测试：queue != NULL 队列非空 数据3入队
    	printf("%d 入队了吗? %d\n",data[2],is_insert);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 3个 结果：is_empty == 0;
    	printf("队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有3个数据元素 结果：length == 3;
    	printf("队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有3个数据 结果：
    	printf("这次的队头为:%d\n",queue_head);
    	printf("\n");
    
    
    	//4入队
    	is_insert = queue_insert(pqueue1,data[3]);//测试：queue != NULL 队列非空，数据元素4入队
    	printf("%d 入队了吗? %d\n",data[3],is_insert);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("这次的队头为:%d\n",queue_head);
    	printf("\n");
    	printf("\n");
    	printf("\n");
    
    
    //---------测试---遍历队列 bool queue_traverse(const LinkQueue * const queue)--------访问队列中的所有节点的数据域--------------//
    //测试用例：queue == NULL, queue != NULL (1)队列为空（2）队列非空
    	int is_traverse = false;//用来判断是否遍历完队列 为 true（1）遍历完，否则为false
    	printf("队列中从头到尾的数据元素依次为：");
    	//is_traverse = queue_traverse(pqueue2);//测试：queue == NULL 结果：程序“[4872] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    	is_traverse = queue_traverse(pqueue1);//测试 queue != NULL (2)队列非空
    	printf("\n");
    	printf("队列是否遍历完？ %d\n",is_traverse);
    	printf("\n");
    	printf("\n");
    	printf("\n");
    
    	
    //---------测试将队列清空------------------clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空-----------//
    //测试用例 queue == NULL ,queue ！= NULL 1.队列为空， 2.队列不为空
        
    	bool is_clear = false;//当队列清空后为true(1),队列没有清空为false(0)
    	//clear_queue(pqueue2);//测试 queue == NULL,测试结果：程序“[1180] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    
    	//is_clear = clear_queue(pqueue1);//测试 queue != NULL 2.队列不为空
    	//printf("队列清空了吗？ %d\n",is_clear);
    
    	
    	//is_traverse = queue_traverse(pqueue1);//测试遍历 queue != NULL (2)队列为空 测试结果：程序“[4212] Queue.exe: 本机”已退出，返回值为 -2 (0xfffffffe)。
    	//printf("\n");
    
    
    //销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
    //测试用例：queue == NULL ,queue != NULL
    
          bool is_destroy = false;//队列销毁为true（1），否则为 false(0)
         // is_destroy =destroy_queue( pqueue2);;//测试 queue == NULL 测试结果：程序“[4044] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    
    	//  is_destroy  = destroy_queue(pqueue1);//测试queue != NULL，队列非空
    	
    //-------------------测试从队列中删除队头（出队） delete_queue_front( LinkQueue *queue)------------------------//
    //测试用例 queue == NULL ,queue != NULL (1)队列为空，异常退出exit(-2)(2)队列只有一个数据元素，出队后为空（3）队列有多个数据元素 
    
    	bool is_out = false;//定义一个bool 量is_out 判断队列是否出队，成功出队 返回true
    	//delete_queue_front(pqueue2);//测试 queue == NULL 结果：程序“[5284] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)
    
    	//1.队空 2.队长 3.队头元素 4.出队后 5.队头元素 6.队长7.队空
    	//1出队
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队前队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队前队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队前的队头为:%d\n",queue_head);
    
    	is_out = delete_queue_front(pqueue1);//出队
    	printf("出队成功？ %d\n",is_out);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队后的队头为:%d\n",queue_head);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队后队列长度为%d\n",length);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队后队列为空吗：%d\n",is_empty);
    
    	printf("\n");
    	printf("\n");
    
    
    	//2出队
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队前队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队前队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队前的队头为:%d\n",queue_head);
    
    	is_out = delete_queue_front(pqueue1);//出队
    	printf("出队成功？ %d\n",is_out);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队后的队头为:%d\n",queue_head);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队后队列长度为%d\n",length);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队后队列为空吗：%d\n",is_empty);
    
    	printf("\n");
    
    
    	//3出队
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队前队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队前队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队前的队头为:%d\n",queue_head);
    
    	is_out = delete_queue_front(pqueue1);//出队
    	printf("出队成功？ %d\n",is_out);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队后的队头为:%d\n",queue_head);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队后队列长度为%d\n",length);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队后队列为空吗：%d\n",is_empty);
    
    	printf("\n");
    
    	//4出队
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队前队列为空吗：%d\n",is_empty);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队前队列长度为%d\n",length);
    
    	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    	printf("出队前的队头为:%d\n",queue_head);
    
    	is_out = delete_queue_front(pqueue1);//出队
    	printf("出队成功？ %d\n",is_out);
    
    //	queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    //	printf("出队后的队头为:%d\n",queue_head);
    
    	length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    	printf("出队后队列长度为%d\n",length);
    
    	is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    	printf("出队后队列为空吗：%d\n",is_empty);
    
    	printf("\n");
    
    
    
    
    
    	is_destroy  = destroy_queue(pqueue1);//测试queue != NULL，队列为空
    	printf("队列，代表地球消灭你,嘿嘿！！！！\n");
    
    
    
    
    	return 0;
    }

6.实验结果与结论

**从上述代码和实验结果我们可以看出，队列是一种先进先出的线性表。凡是满足先进先出线性关系的，我们都可以用队列来进行描述。在算法中 我借用了c++的**

**const 关键字，目的是告诉其它程序员，算法是否会对原始数据进行修改。具体有关const的用法，大家可以参考《effective c++>>或者我前面的几篇博客，有详尽的描述。我们还得注意就是在出队操作的算法描述里，一般情况下，只要改变头节点的指针，但是当队列中最后一个元素也出队时，队尾指针也需修改。![Center][]![Center 1][]**

[Center]: https://img-blog.csdn.net/20150823141304337?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220731/e3e76086c32648229d0f0e75814b40ea.png