数据结构之链队（队列）

2018/3/20

数据结构

1.队列

队列是一种特殊的线性表，相较于栈来说，队列是后进先出的，而栈是后进后出的，队列的特点

是多了两个指针，一个是指向队头，一个指向队尾

2.对于队列相关操作的介绍和认识

part1：新建队列

实现队列的新建，只要把队列的队头指针和队尾指针都指向空

part2：判断队列是否为空

判断队头指针和队尾指针是否都为空，如果都为空，说明队列为空

part3：实现取得队首元素

前提条件：队列不为空，然后实现取得队头所在指针的数据域

part4：展示队列

遍历队列，将一个所创建的结点放在队首，遍历取数

part5：插入数字

前提条件：判断队列是否为空，判断队列如果只有一个元素的情况，将某个结点放在队尾处

（尾插法：将尾结点的后继给予，然后移动尾指针）

part6：出队

前提条件：判断队列是否为空·，判断队列只有一个元素的情况，然后将队首指针后移

释放待删除结点

//链队列的简单使用
//使用队首队尾指针的指向来表示队首元素和队尾元素

//头文件
struct Qnode//创建结点
{
	int data;//数据域
	struct Qnode* next;//指针域
};
struct Queue//创建前后指针
{
	struct Qnode*front;
	struct Qnode*rear;
};
//1.新建队列
struct Queue *init_queue(struct Queue *q)//使用指针进行操作
{
	//q = (struct Queue *)malloc(sizeof(struct Queue));
	q->front = NULL;
	q->rear = NULL;
	return q;
}
//2.判断是否为空，采用返回值1 0来判断
int IsNotEmpty(struct Queue *q)
{
	if ((q->front == NULL)&&(q->rear==NULL))
	{
		return 0;//为空
	}
	else
	{
		return 1;
	}
}
//3.取得队首元素

struct Queue*catch_Queue(struct Queue *q)
{
		if (IsNotEmpty(q)==0)
	{
			printf("取数错误");
	}
		else
	{
			printf("该队首元素为%2d", q->front->data);
	}
		return q;
}
//展示队列
int disp_queue(struct Queue *q)
{
	struct Qnode *p;
	p = q->front;//p为队首元素，被队首指针所指
	printf("\n[队列头]");
	//开始遍历
	while (p!= NULL)
	{
		printf("(%d)-->", p->data);
		p = p->next;
	}
	printf("[队列尾]\n");
	return 1;
}
//插入数操作
struct Queue *append_queue(struct Queue *q, int num)
{
	struct Qnode* p;//插入结点
	p = (struct Qnode*)malloc(sizeof(struct Qnode));
	p->data = num;
	p->next = NULL;
	//判断是否为一个结点的情况
	if (q->front==NULL)
	{
		q->front =p;
		q->rear = p;
	}
	//正常情况
	else
	{
		q->rear->next = p;//将尾指针的后继给了p（尾插法）
		q->rear = p;//移动尾指针
	}
	return q;
}
//出队操作
struct Queue* delete_queue(struct Queue *q)
{
	struct Qnode* p;
	//判断是否为空
	if (IsNotEmpty(q) == 0)
	{
		printf("队列为空\n");
		return q;
	}
	else
	{
		p = q->front;//将p放在队首的位置
		if (q->front == q->rear)//头指针等于尾指针，说明只有一个结点
		{
			q->front = NULL;
			q->rear = NULL;
		}
		else
		{
			q->front = p->next;//将头指针移动位置到队首
			
		}
		free(p);
		return q;
	}

}
//链队列的简单使用
//使用队首队尾指针的指向来表示队首元素和队尾元素

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct Qnode//创建结点
{
	int data;//数据域
	struct Qnode* next;//指针域
};
struct Queue//创建前后指针
{
	struct Qnode*front;
	struct Qnode*rear;
};
//1.新建队列
struct Queue *init_queue(struct Queue *q)//使用指针进行操作
{
	//q = (struct Queue *)malloc(sizeof(struct Queue));
	q->front = NULL;
	q->rear = NULL;
	return q;
}
//2.判断是否为空，采用返回值1 0来判断
int IsNotEmpty(struct Queue *q)
{
	if ((q->front == NULL)&&(q->rear==NULL))
	{
		return 0;//为空
	}
	else
	{
		return 1;
	}
}
//3.取得队首元素

struct Queue*catch_Queue(struct Queue *q)
{
		if (IsNotEmpty(q)==0)
	{
			printf("取数错误");
	}
		else
	{
			printf("该队首元素为%2d", q->front->data);
	}
		return q;
}
//展示队列
int disp_queue(struct Queue *q)
{
	struct Qnode *p;
	p = q->front;//p为队首元素，被队首指针所指
	printf("\n[队列头]");
	//开始遍历
	while (p!= NULL)
	{
		printf("(%d)-->", p->data);
		p = p->next;
	}
	printf("[队列尾]\n");
	return 1;
}
//插入数操作
struct Queue *append_queue(struct Queue *q, int num)
{
	struct Qnode* p;//插入结点
	p = (struct Qnode*)malloc(sizeof(struct Qnode));
	p->data = num;
	p->next = NULL;
	//判断是否为一个结点的情况
	if (q->front==NULL)
	{
		q->front =p;
		q->rear = p;
	}
	//正常情况
	else
	{
		q->rear->next = p;//将尾指针的后继给了p（尾插法）
		q->rear = p;//移动尾指针
	}
	return q;
}
//出队操作
struct Queue* delete_queue(struct Queue *q)
{
	struct Qnode* p;
	//判断是否为空
	if (IsNotEmpty(q) == 0)
	{
		printf("队列为空\n");
		return q;
	}
	else
	{
		p = q->front;//将p放在队首的位置
		if (q->front == q->rear)//头指针等于尾指针，说明只有一个结点
		{
			q->front = NULL;
			q->rear = NULL;
		}
		else
		{
			q->front = p->next;//将头指针移动位置到队首
			
		}
		free(p);
		return q;
	}

}