队列------- 算法笔记012

「爱情、让人受尽委屈。」 2023-07-04 08:45 26阅读 0赞

## 队列的概念 ##

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

> 队列和栈的不同在于，队列是先进先出的结构，而栈是先进后出的结构。所以我们在定义队列的数据结构的时候要定义一个前指针指向队列的头数据，和一个后指针指向队列的尾数据。

### 队列的数据结构 ###

typedef char ElemType; //定义队列的数据类型
    typedef struct QNode{ 
    	ElemType data;
    	struct QNode *next; //指向下一个队列的指针
    }QNode,*QueueL;
    
    typedef struct { 
    	QueueL first,last;//定义前后指针用来指向一个队列的头和尾
    }LinkQueue;

#### 初始化队列 ####

LinkQueue * InitQue(void){ 
    	
    	LinkQueue * initQue=(LinkQueue *)malloc(sizeof(LinkQueue));
    	if(!initQue){ 
    		return NULL; 
    	}
    	
    	initQue->first=initQue->last=NULL;
    	return initQue; 
    }

#### 写数据到队列中 ####

Status InsertQue(LinkQueue * linkQue,ElemType e){ 
    	
    	//队列为空 
    	if(linkQue->first==NULL&&linkQue->last==NULL){ 
    		QNode * p=(QNode *)malloc(sizeof(QNode));
    		if(!p){ 
    			return error;
    		}
    		p->data=e;
    		p->next=NULL;
    		linkQue->first=linkQue->last=p;
    		return ok;
    	}
    	
    	QNode *pp=(QNode *)malloc(sizeof(QNode));
    	if(!pp){ 
    			return error;
    	}
    	pp->data=e;
    	pp->next=NULL;
    	linkQue->last->next=pp;
    	linkQue->last=pp;
    	
    	return ok;
    	
    	
    }

#### 从队列中读出数据 ####

Status OutQue(LinkQueue * linkQue,ElemType *e){ 
    		
    	//队列为空 
    	if(linkQue->first==NULL&&linkQue->last==NULL){ 
    		return error;	
    	}
    
    	//队列中只剩一个数据 
    	if(linkQue->first->next==NULL){ 
    		 *e=linkQue->first->data;
    		linkQue->first=linkQue->first->next;
    		 free(linkQue->last);
    		 linkQue->last=NULL;
    		  return ok;
    	} 
    	 
        *e=linkQue->first->data;
    	QNode *p=linkQue->first;
    	linkQue->first=linkQue->first->next;
    	free(p);
    	return ok;	
    
    }

> 如此我们就实现了队列的核心功能，存储数据以队列的方式。另外我们还可以编写一些函数，如判断队列是否为空，在队列的第几个插入位置等等。说白了队列就是一个特殊的单链表，只不过队列的存储数据的特点是线性的。

### 工程代码 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define error 0
    #define ok 1
    
    
    typedef char ElemType;
    
    typedef int Status;
    
    typedef struct QNode{ 
    	ElemType data;
    	struct QNode *next;
    }QNode,*QueueL;
    
    typedef struct { 
    	QueueL first,last;
    }LinkQueue; 
    
    LinkQueue * InitQue(void){ 
    	
    	LinkQueue * initQue=(LinkQueue *)malloc(sizeof(LinkQueue));
    	if(!initQue){ 
    		return NULL; 
    	}
    	
    	initQue->first=initQue->last=NULL;
    	return initQue; 
    }
    
    
    Status InsertQue(LinkQueue * linkQue,ElemType e){ 
    	
    	//队列为空 
    	if(linkQue->first==NULL&&linkQue->last==NULL){ 
    		QNode * p=(QNode *)malloc(sizeof(QNode));
    		if(!p){ 
    			return error;
    		}
    		p->data=e;
    		p->next=NULL;
    		linkQue->first=linkQue->last=p;
    		return ok;
    	}
    	
    	QNode *pp=(QNode *)malloc(sizeof(QNode));
    	if(!pp){ 
    			return error;
    	}
    	pp->data=e;
    	pp->next=NULL;
    	linkQue->last->next=pp;
    	linkQue->last=pp;
    	
    	return ok;
    	
    	
    }
    
    Status OutQue(LinkQueue * linkQue,ElemType *e){ 
    		
    	//队列为空 
    	if(linkQue->first==NULL&&linkQue->last==NULL){ 
    		return error;	
    	}
    
    	//队列中只剩一个数据 
    	if(linkQue->first->next==NULL){ 
    		 *e=linkQue->first->data;
    		linkQue->first=linkQue->first->next;
    		 free(linkQue->last);
    		 linkQue->last=NULL;
    		  return ok;
    	} 
    	 
        *e=linkQue->first->data;
    	QNode *p=linkQue->first;
    	linkQue->first=linkQue->first->next;
    	free(p);
    	return ok;	
    
    }
    
    
    int main(int argc, char *argv[]) { 
    	
    	LinkQueue * Q=InitQue();
    	
    	InsertQue(Q,'C');
    	InsertQue(Q,'h');
    	InsertQue(Q,'a');
    	InsertQue(Q,'n');
    	InsertQue(Q,'g');
    	InsertQue(Q,'l');
    	InsertQue(Q,'o');
    	InsertQue(Q,'n');
    	
    	printf("%p %p\n",Q->first,Q->last);
    	
    	ElemType e;
    	while(OutQue(Q,&e)){ 
    		printf("%c",e);
    	}
    	printf(" ");
    	InsertQue(Q,'l');
    	InsertQue(Q,'o');
    	InsertQue(Q,'v');
    	InsertQue(Q,'e');
    	InsertQue(Q,' ');
    	InsertQue(Q,'y');
    	InsertQue(Q,'o');
    	InsertQue(Q,'u');
    	
    	while(OutQue(Q,&e)){ 
    		printf("%c",e);
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200209175120186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70