数据结构-队列之链式队列

今天药忘吃喽~ 2022-05-04 00:26 388阅读 0赞

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点，即单链表的最后一个节点。  
当q.front==NULL且q.rear==NULL时，链式队列为空。  
出队时，首先判断队列是否为空，如果不为空，则取出队头元素，将其从链表中删除，并让q.front指向下一个节点（若该节点为最后一个节点，则置q.front和q.rear都为null）。  
入队时，建立一个新节点，将新节点插入到链表的尾部，并改让q.rear指向这个新插入的节点（若原队列为空队，则令q.front也指向该节点）。  
不难看出，不设头结点的链式队列在操作上往往比较麻烦，因此，通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了，如图所示  
![70][]  
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外，加入程序中要使用多个队列，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。

//队列之链式队列
    
    #include "stdafx.h"
    #include "stdlib.h"
    
    #define ElementType int
    //链式队列的节点
    typedef struct {
    	ElementType data;//数据域
    	LinkNode *next;//节点指针域
    }LinkNode;
    
    //链式队列
    typedef struct {
    	LinkNode *front, *rear;//队列的头指针和尾指针
    }LinkQueue;
    
    /*
    链式队列初始化
    1.建立头结点，且队列的头指针和尾指针都指向该头结点
    2.头指针的指针域为null
    */
    void InitQueue(LinkQueue &q) {
    	q.front = q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    	q.front->next = NULL;
    }
    /*
    判断链式队列是否为空
    1.因为我们采用的是带头结点的链式队列，所以头指针始终是指向头结点的，当队列为空时，让尾指针也指向头结点
    2.所以当头指针和尾指针相等时即队列为空
    */
    bool QueueEmpty(LinkQueue q) {
    	if (q.front == q.rear) {
    		return true;
    	}
    	return false;
    }
    /*
    入队操作
    */
    void EnQueue(LinkQueue &q, ElementType e) {
    	//开辟新节点空间
    	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    	s->data = e;//数据域
    	q.rear->next = s;//尾指针指针域指向新节点
    	q.rear = s;//尾指针节点位置移动
    }
    /*
    出队操作
    */
    ElementType Dequeue(LinkQueue &q) {
    	//是否为空
    	if (QueueEmpty) {
    		return NULL;
    	}
    	LinkNode *s = q.front->next;//获取需要出队的节点
    	int e = s->data;//数据域赋值
    	q.front->next = s->next;//将需要出队节点的指针域赋值给头指针的指针域
    	if (s == q.rear) {
    		//判读是否该链式队列中只有一个节点了，如果是则将头指针和尾指针都指向头结点即空队列
    		//头指针始终是指向头结点的
    		q.rear = q.front;
    	}
    	free(s);
    	return e;
    }
    /*
    销毁一个链式队列
    */
    void DestoryQueue(LinkQueue &q) {
    	while (q.front->next)
    	{
    		LinkNode *s = q.front->next;
    		q.front->next = s->next;
    		free(s);
    	}
    }

[70]: /images/20220504/f01bd0d6f9824c55bce73f86ff9921e9.png