链队列的基本操作C/C++代码实现

朴灿烈づ我的快乐病毒、 2023-02-14 15:54 8阅读 0赞

## 链队列的结构： ##

![在这里插入图片描述][20200603203521854.png]  
链队列与单链表相同但与链栈不同的是，链队列需要添加一个头结点，并让头指针始终指向头结点。

## 入队： ##

链队列也不需要判断队满。  
![在这里插入图片描述][20200603203912352.png]

## 出队： ##

链队列队空条件：Q.front==Q.rear （与循环队列形式相同）  
![在这里插入图片描述][20200603204147610.png]  
需要特别注意的是：需要判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值， 指向头结点。 （否则尾指针将丢失）

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXQSIZE 100
    typedef int QElemType;
    
    //链队列的结构
    typedef struct QNode
    {
        
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct
    {
        
    	QueuePtr front;			//头指针
    	QueuePtr rear;			//尾指针
    }LinkQueue;
    
    //初始化
    void InitQueue(LinkQueue &Q)
    {
        
    	Q.front = new QNode;		//创建一个头结点
    	Q.rear = Q.front;			//头尾指针都指向头结点
    	Q.front->next = NULL;		
    }
    
    //入队
    int EnQueue(LinkQueue &Q,QElemType e)
    {
        
    	//链队列不需要判断队满
    
    	QNode *p = new QNode;
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return 1;
    }
    
    //出队
    int DeQueue(LinkQueue &Q, QElemType &e)
    {
        
    	if (Q.rear == Q.front) return 0;   //队空
    
    	QNode *p = Q.front->next;
    	e = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p) Q.rear = Q.front;		//注意：最后一个元素被删， 队尾指针也要指向头结点 
    	delete p;
    	return 1;
    }
    
    //取队头元素
    QElemType GetHead(LinkQueue Q)
    {
        
    	if (Q.front != Q.rear)			//非空时 取值
    		return Q.front->next->data;
    }
    
    //遍历输出队列
    void printQueue(LinkQueue Q)
    {
        
    	printf("队头->");
    	QNode *p =Q.front->next;
    	while (p)
    	{
        
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("<-队尾\n");
    }
    
    
    int main()
    {
        
    	LinkQueue Q;
    	int e;
    	InitQueue(Q);
    	printf("请输入一个要入队的元素（-1表示结束）：");
    	scanf("%d", &e);
    	while (e != -1)
    	{
        
    		EnQueue(Q, e);
    		printf("请输入一个要入队的元素（-1表示结束）：");
    		scanf("%d", &e);
    	}
    	printQueue(Q);
    	printf("出队测试：");
    	DeQueue(Q, e);
    	printQueue(Q);
    
    	printf("取队头元素测试：");
    	e = GetHead(Q);
    	printf("取出的队头元素为：%d\n", e);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200603203521854.png]: https://img-blog.csdnimg.cn/20200603203521854.png
[20200603203912352.png]: https://img-blog.csdnimg.cn/20200603203912352.png
[20200603204147610.png]: https://img-blog.csdnimg.cn/20200603204147610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603204651903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70