【数据结构】之队列的链式存储结构及实现（C语言）

「爱情、让人受尽委屈。」 2023-02-16 01:43 20阅读 0赞

### 文章目录 ###

*   *  概念
     *   *  入队操作
         *  出队操作
     *  总结
     *  测试代码

## 概念 ##

**队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把他简称为链队列。**  
为了操作方便，我们将队的头指针指向链队列的头结点，而队尾指针指向终端结点。  
![在这里插入图片描述][20200607105331460.png]  
空队列时，front和rear都指向头结点。  
![在这里插入图片描述][2020060710543894.png]  
链队列的结构为：

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

### 入队操作 ###

入队操作就是在链表尾部插入结点。  
![在这里插入图片描述][20200607110200932.png]

//插入元素e为Q的新的队尾元素
    Status EnQueue(LinkQueue *Q,QElemType e)
    {
        
    	QueuePtr =s(QueuePtr)malloc(sizeof(QNode));
    	if(!s)   //存储分配失败
    		exit(OVERFLOW)；
    	s->data =e;
    	s->data=e;
    	s->next= NULL;
    	Q->rear->next=s;  //把拥有元素e新结点s赋值给原队尾结点的后继
    	Q->rear=s;      //把当前的s设置为队尾结点，rear指向s。
    	return OK;
    }

### 出队操作 ###

出队操作时，就是头结点的后继结点出队，将头结点的后继改为他后面的结点，若链表除头结点外只剩下一个元素时，组需要将rear指向头结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]

//若队列不为空，删除Q的队头元素，用e返回其值，并返回OK
    Status DeQueue(LinkQueue *Q,QElemType *e)
    {
        
    	QueuePtr p;
    	if(Q->front == Q->rear)
    		return ERROR;
    	p=Q->front->next;   //将要删除的队头结点暂存给p
    	*e=p->data;         //将要删除的对头结点的值赋值给e
    	Q->front->next = p->next;   //将原队头结点后继p->next赋值非头结点后继
    	if(Q->rear ==p)            //若队头是队尾，则删除后将rear指向头结点
    		Q->rear = Q->front;
    	free(p)；
    	return OK;
    	
    }

## 总结 ##

对于循环队列和链队列的比较，可以从两方面考虑，从时间上，其实他们的基本操作都是常数时间，即都为O(1),不过循环队列的事先申请好空间，使用期间不释放，则链队列，每次申请和释放结点也会存在一定的时间开销。如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列要有固定的长度，所以有了存储元素个数和浪费空间的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但是也可以接受。所以在空间上，链队列更加灵活。

## 测试代码 ##

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20 /* 存储空间初始分配量 */
    
    typedef int Status; 
    
    typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
    
    typedef struct QNode	/* 结点结构 */
    {
        
       QElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    {
        
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;
    
    Status visit(QElemType c)
    {
        
    	printf("%d ",c);
    	return OK;
    }
    
    /* 构造一个空队列Q */
    Status InitQueue(LinkQueue *Q)
    {
         
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    	if(!Q->front)
    		exit(OVERFLOW);
    	Q->front->next=NULL;
    	return OK;
    }
    
    /* 销毁队列Q */
    Status DestroyQueue(LinkQueue *Q)
    {
        
    	while(Q->front)
    	{
        
    		 Q->rear=Q->front->next;
    		 free(Q->front);
    		 Q->front=Q->rear;
    	}
    	return OK;
    }
    
    /* 将Q清为空队列 */
    Status ClearQueue(LinkQueue *Q)
    {
        
    	QueuePtr p,q;
    	Q->rear=Q->front;
    	p=Q->front->next;
    	Q->front->next=NULL;
    	while(p)
    	{
        
    		 q=p;
    		 p=p->next;
    		 free(q);
    	}
    	return OK;
    }
    
    /* 若Q为空队列,则返回TRUE,否则返回FALSE */
    Status QueueEmpty(LinkQueue Q)
    {
         
    	if(Q.front==Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    /* 求队列的长度 */
    int QueueLength(LinkQueue Q)
    {
         
    	int i=0;
    	QueuePtr p;
    	p=Q.front;
    	while(Q.rear!=p)
    	{
        
    		 i++;
    		 p=p->next;
    	}
    	return i;
    }
    
    /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
    Status GetHead(LinkQueue Q,QElemType *e)
    {
         
    	QueuePtr p;
    	if(Q.front==Q.rear)
    		return ERROR;
    	p=Q.front->next;
    	*e=p->data;
    	return OK;
    }
    
    
    /* 插入元素e为Q的新的队尾元素 */
    Status EnQueue(LinkQueue *Q,QElemType e)
    {
         
    	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    	if(!s) /* 存储分配失败 */
    		exit(OVERFLOW);
    	s->data=e;
    	s->next=NULL;
    	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
    	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
    	return OK;
    }
    
    /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
    Status DeQueue(LinkQueue *Q,QElemType *e)
    {
        
    	QueuePtr p;
    	if(Q->front==Q->rear)
    		return ERROR;
    	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
    	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
    	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
    		Q->rear=Q->front;
    	free(p);
    	return OK;
    }
    
    /* 从队头到队尾依次对队列Q中每个元素输出 */
    Status QueueTraverse(LinkQueue Q)
    {
        
    	QueuePtr p;
    	p=Q.front->next;
    	while(p)
    	{
        
    		 visit(p->data);
    		 p=p->next;
    	}
    	printf("\n");
    	return OK;
    }
    
    int main()
    {
        
    	int i;
    	QElemType d;
    	LinkQueue q;
    	i=InitQueue(&q);
    	if(i)
    		printf("成功地构造了一个空队列!\n");
    	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
    	printf("队列的长度为%d\n",QueueLength(q));
    	EnQueue(&q,-5);
    	EnQueue(&q,5);
    	EnQueue(&q,10);
    	printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));
    	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
    	printf("队列的元素依次为：");
    	QueueTraverse(q);
    	i=GetHead(q,&d);
    	if(i==OK)
    	 printf("队头元素是：%d\n",d);
    	DeQueue(&q,&d);
    	printf("删除了队头元素%d\n",d);
    	i=GetHead(q,&d);
    	if(i==OK)
    		printf("新的队头元素是：%d\n",d);
    	ClearQueue(&q);
    	printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
    	DestroyQueue(&q);
    	printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);
    	
    	return 0;
    }

[20200607105331460.png]: https://img-blog.csdnimg.cn/20200607105331460.png
[2020060710543894.png]: https://img-blog.csdnimg.cn/2020060710543894.png?
[20200607110200932.png]: https://img-blog.csdnimg.cn/20200607110200932.png?
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200607111339602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70