C语言数据结构之队列的实现（链表实现）

深藏阁楼爱情的钟 2022-11-27 12:04 105阅读 0赞

## C语言数据结构之队列的实现（链表实现） ##

tips：前些天学习了链表和栈，今天来看看c语言数据结构之队列的实现以及队列的各种操作。

--------------------

**队列的特点是先进先出，后进后出，因此我们很容易就能够想到用单链表的尾插法，和头部删除法去实现队列的入队和出队的操作。**

--------------------

首先我们来看一下队列的各种操作的实现思路以及具体实现过程  
准备工作：

*  创建队列元素的结构体

//定义结点
    typedef struct tag
    {
        
    	int val;//队列(链表)的值
    	struct  tag *pNext;
    }Node,*pNode;

*  创建队列的结构体

//定义队列
    typedef struct tagQueue
    {
        
    	pNode phead, ptail;//队头队尾指针,分别指向头结点和尾结点
    }Queue,*pQueue;

*  准备队列的打印输出函数

//测试输出队列元素
    void print_queue(pQueue p)
    {
        
    	pNode pcur = p->phead;//定义工具人，保存当前结点信息
    
    	while (pcur!=NULL)
    	{
        
    		printf("%d\n", pcur->val);
    		pcur = pcur->pNext;
    	}
    	printf("------------------------------------------\n");
    }

--------------------

**1、入队（enQueue）**

思路：

*  为链表创建新的结点，并将其初始化；
 *  采用尾部插入法将新结点入队；

具体实现：

//入队
    void enQueue(pQueue p,int val)
    {
        
    	pNode pnew = (pNode)calloc(1,sizeof(Node));//为新结点申请空间并初始化
    
    	pnew->val = val;//插入的值
    
    	//入队
    	if (p->phead == NULL)//判断队列是否为空
    	{
        
    		//为空，头尾指针指向第一个结点
    		p->phead = pnew;
    		p->ptail = pnew;
    	}
    	else
    	{
        
    		//不为空，尾插法
    		p->ptail->pNext = pnew;//新结点放在原来尾结点后面
    		p->ptail = pnew;//新结点变成尾结点
    	}
    }

--------------------

**2、出队（deQueue）**

思路：

*  采用头部删除法，删除头结点（即队头元素），完成出队操作；
 *  出队后，释放出队元素所占用的空间；

具体实现：

//出队
    void deQueue(pQueue p)
    {
        
    	//出队，头部删除法
    
    	pNode pcur;//工具人，指向当前结点
    	pcur = p->phead;
    
    	if (p->phead == NULL)
    	{
        
    		//队列为空
    		printf("队列为空!\n");
    	}
    	else
    	{
        
    		//头部删除法
    
    		p->phead = p->phead->pNext;//头结点后移
    		//释放空间
    		free(pcur);
    	}
    }

--------------------

**3、判断队列是否为空（isEmpty）**

思路：

*  当队头指针为空时，队列即为空（当头指针=尾指针不为空时，就剩最后一个元素）；

总之判断方法很多，大家可以尽情发挥。

具体实现：

//判断队列是否为空
    int isEmpty(pQueue p)
    {
        
    	if (p->phead == NULL)
    		return 1;//为空
    	else
    		return 0;
    }

--------------------

至此队列的基本操作我们已经全部实现了，接下来我们在main()函数中测试一下：

int main()
    {
        
    	//定义一个队列,并初始化
    	//队列是先进先出，用尾插法和头部删除法实现进队和出队
    	Queue que;
    	int val;
    	char panduan;//判断是否出队(y/n)
    
    	memset(&que,0,sizeof(Queue));//memset主要是用来对空间初始化的
    
    	//循环入队
    	while (scanf("%d", &val) != EOF)
    	{
        
    		//入队
    		enQueue(&que, val);
    	}
    
    	//打印队列元素
    	printf("队列中的元素为：\n");
    	print_queue(&que);
    
    	//判断队列是否为空
    	if (isEmpty(&que))
    	{
        
    		printf("队列为空！\n");
    	}
    	else
    	{
        
    		printf("队列不为空！\n");
    	}
    
    	printf("------------------------------------------\n");
    
    	while (printf("是否出队？y/n："), scanf("%c", &panduan) != NULL)
    	{
        
    		if (panduan == 'y')
    		{
        
    			//出队
    			deQueue(&que);
    
    			//打印元素
    			print_queue(&que);
    
    			//判断队列是否为空
    			if (isEmpty(&que))
    			{
        
    				printf("队列为空！\n");
    			}
    			else
    			{
        
    				printf("队列不为空！\n");
    			}
    
    			printf("---------------------------------\n");
    		}
    		else if (panduan == 'n')
    		{
        
    			break;
    		}
    
    	}
    
    	return 0;
    
    
    }

实现结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]  
队列的操作到目前来说已经实现，希望对大家的学习能够有所帮助，加油！

--------------------

tips：为了不让生活留下遗憾和后悔，我们应该尽可能地抓住一切改变生活的机会。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/c4c66ef0b3c84f4db9efb0ee03be705f.png