数据结构：链队

一、定义两个结构体

定义两个结构体,一个结构体是结点的结构体，一个结构体是保留指向对头结点和队尾结点指针的结构体

#ifndef __LINK_QUEUE_H__
#define __LINK_QUEUE_H__
#include <stdio.h>
#include <stdlib.h>
 
typedef struct link_node{
	int data;
	struct link_node *next;
}link_node,*node_p;
typedef struct queue{
	node_p front;
	node_p rear;
}queue,*que_p;
 
 
//创建头、尾指针
que_p creat_queue();
//申请链队
node_p creat_link(int data);
//判空
int empty(que_p Q);
//入队
void push_que(que_p Q,int data);
//出队
void pop_que(que_p Q);
//打印
void out_put(que_p Q);
//销毁
void free_Q(que_p *Q);
#endif

二、功能

1.创建头、尾指针

//创建头、尾指针
que_p creat_queue(){
	que_p Q=(que_p)malloc(sizeof(queue));
	if(Q==NULL){
		printf("申请空间失败\n");
		return NULL;
	}
	Q->front=Q->rear=NULL;
	return Q;
}

2.申请链队

//申请链队
node_p creat_link(int data){
	node_p new=(node_p)malloc(sizeof(link_node));
	if(new==NULL){
		printf("申请空间失败\n");
		return NULL;
	}
	new->data=data;
	new->next=NULL;
	return new;
}

3.判空

//判空
int empty(que_p Q){
	if(Q==NULL){
		printf("申请空间失败\n");
		return -1;
	}
	return Q->front==NULL?1:0;
}

4.入队

//入队
void push_que(que_p Q,int data){
	if(Q==NULL){
		printf("申请空间失败\n");
		return;
	}
	node_p new=creat_link(data);
	if(empty(Q)){  //如果是入队的第一个元素
		Q->front=new;
		Q->rear=new;
		return;
	}else{
	Q->rear->next=new;
	Q->rear=new;
	}
 
}

5.出队

void pop_que(que_p Q){
	if(Q==NULL){
		printf("申请空间失败\n");
		return;
	}
	if(empty(Q)){
		printf("链队为空\n");
		return;
	}
	node_p del=Q->front;
	printf("出队的值为：%d\n",Q->front->data);
	Q->front=Q->front->next;
	free(del);
}

6.打印

//打印
void out_put(que_p Q){
	if(Q==NULL){
		printf("申请空间失败\n");
		return;
	}
	if(empty(Q)){
		printf("链队为空\n");
		return;
	}
	node_p p=Q->front;
	while(p!=NULL){
		printf("%d->",p->data);
		p=p->next;
	}
	putchar(10);
}

7.销毁

//销毁
void free_Q(que_p *Q){
	if(Q==NULL || *Q==NULL){
		return;
	}
	
	node_p p=(*Q)-front; //进行降级操作，实际就是要取链队的首指针
	while(p!=NULL){
		node_p q=p->next;
		free(p);
		p=q;
	}
	free(*Q);
	*Q=NULL;
}