线性表之链队列（C语言实现）

迈不过友情╰ 2022-03-27 04:26 255阅读 0赞

一、**链队列**

1、队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

2、为了操作上的方便，我们增加一个队头结点，一个队头指针，一个队尾指针。

3、空队列时，front和rear指针都指向头结点，如图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70][]

4、非空队列时，对头指针指向队头结点，队尾指针指向终端结点，如图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 1][]

二、链队列数据结构

typedef int QElemType;//QElemType根据实际情况而定，这里假设为int
    typedef struct Qnode
    {
    	QElemType data;
    	struct Qnode *next;
    }Qnode,*QueuePtr;
    
    typedef struct //队列的链表结构
    {
    	QueuePtr front,rear;//队头、队尾指针
    }LinkQueue,*LinkQueuePtr;

三、基本操作

1、队列创建

bool CreateQueue(LinkQueue *Q)
    {
    	if(!Q)
    	{
    		return false;
    	}
    
    	Q->front = Q->rear = (QueuePtr)malloc(sizeof(Qnode));
    	if(!Q->front)
    	{
    		return false;
    	}
    
    	Q->front->next = NULL;// 队头节点指向NULL
    
    	return true;
    }

2、入队

bool Enqueue(LinkQueue *Q, QElemType e)
    {
    	QueuePtr s = (QueuePtr)malloc(sizeof(Qnode));
    	if(!s)
    		return false;
    
    	s->data = e;
    	s->next = NULL;
    
    	Q->rear->next = s;//把拥有元素e新结点s赋值给队尾指针的后继
    	Q->rear = s;//把当前的s设置为队尾结点，rear指向s
    
    	return true;
    }

3、出队

//注意出队分为两种情况
    bool Dequeue(LinkQueue *Q, QElemType *e)
    {
    	QueuePtr p = NULL;
    
    	if(!Q)
    		return false;	
    
    	if(Q->front == Q->rear)
    		return false;
    
    	p = Q->front->next;
    	*e = p->data;
    	Q->front->next = p->next;
    
    	if(Q->rear == p)//只有一个结点的情况(不含头结点)
    		Q->rear = Q->front;//使尾结点指向头结点
    
    	free(p);
    
    	return true;
    }

4、队列是否空

bool QueueEmpty(LinkQueue *Q) {
    	if(!Q)
    		return false;
    
        // 头指针和尾指针位置相等，队列为空
        if (Q->front == Q->rear) {
            return true;
        } else {
            return false;
        }
    }

5、遍历队列

bool visit(QElemType e) {
        printf("%d ", e);
        return true;
    }
    
    bool QueueTravel(LinkQueue *Q) {
        QueuePtr p; // 用于遍历队列中的节点
    	
    	if(!Q)
    		return false;
    
        p = Q->front->next; // p指向头节点
    
        printf("遍历队列，队中的元素是:\n");
        // 当队列中还有元素
        while (p) {
            visit(p->data); // 打印当前节点的值
            p = p->next; // p移动到队列下一个位置
        }
    	printf("\n");
        return true;
    }

6、获取队列长度

int QueueLength(LinkQueue *Q)
    {
    	if(!Q)return -1;
    
    	QueuePtr p = Q->front;
    	int count = 0;
    
    	while(p->next)
    	{
    		count++;
    		p = p->next;
    	}
    
    	return count;
    }

7、获取队列头

bool GetHead(LinkQueue *Q, QElemType *e) {
        QueuePtr p;
    
    	if(!Q)
    		return false;
    
        // 队列为空，获取失败
        if (Q->front == Q->rear) {
            return false;
        }
    
        p = Q->front->next; // p指向队列的第一个元素
        *e = p->data; // 将队列头元素的值赋值给e元素
        return true;
    }

8、清空队列

bool ClearQueue(LinkQueue *Q) {
        QueuePtr p, q; // p用来遍历队列节点，q用来指向被删除的节点
    
    	if(!Q)return true;
    		printf("空队列\n");
    
    	printf("清空队列\n");
        Q->rear = Q->front; // 队尾指针指向队头指针
        p = Q->front->next; // p指向队头指针的下一个节点
        Q->front->next = NULL; // 队头指针的下一个节点指向NULL（表示删除之后的所有元素）
    
        // 当队列中还有元素，释放头节点之后的所有节点
        while (p) {
            q = p; // q节点指向被删除节点
            p = p->next; // p指向队列的下一个节点
            free(q); // 释放q节点
        }
        return true;
    }

9、销毁队列

bool DestroyQueue(LinkQueue *Q)
    {
    	if(!Q)return false;
    
    	printf("销毁队列\n");
    	while (Q->front) 
    	{
            Q->rear = Q->front->next;// 队尾指针指向队头指针的下一个元素
            free(Q->front); // 释放队头指针所在节点
            Q->front = Q->rear; // 队头指针指向队尾指针（即原来的下一个元素）
        }
    
    	return true;
    }

四、测试代码 及测试结果

#include<stdio.h>
    #include<stdlib.h>
    #include"malloc.h"
    
    
    void main(void)
    {	
    	LinkQueue Lqueue;
    	CreateQueue(&Lqueue);
    
    	QElemType i;
    	for(i = 0;i < 10;i++)
    	{
    		if(false == Enqueue(&Lqueue,i)) break;
    		else
    			printf("依次入队元素：%d\n",i);
    	}
    	int len = QueueLength(&Lqueue);
    	printf("===========len：%d===========\n",len);
    	QueueTravel(&Lqueue);
    
    	QElemType e;
    
    	GetHead(&Lqueue,&e);
    	printf("链表头为：%d\n",e);
    
    	for(i = 0;i < 5;i++)
    	{
    		if(false == Dequeue(&Lqueue,&e)) break;
    		else
    			printf("依次出队元素：%d\n",e);
    	}
    	QueueTravel(&Lqueue);
    
    	ClearQueue(&Lqueue);
    	QueueEmpty(&Lqueue);
    
    	DestroyQueue(&Lqueue);
    
    	system("pause");
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70]: /images/20220327/f615b450c2e546d18a6294821532c507.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 1]: /images/20220327/493167e699384ff3807da27234b7c784.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 2]: /images/20220327/9876e56791544665923817c94e010c22.png