一、队列的概念

操作受限的线性表，允许在队列的一端执行入队操作，另一端执行出队操作

先进先出(FIFO)

1.顺序队列

物理结构连续，依赖于数组实现

队列中有一个队头指针和队尾指针，队头指针保存每次要出队的元素，队尾指针保存每次要入队的位置

顺序队列存在假溢满现象：队列中仍然有位置入队元素，但是队尾指针已经走到了队满的条件

2.循环队列

循环队列用于解决假溢满现象

如果循环队列的每个位置都存入元素，队列的判空和判满是同一种条件：front==rear；

所以循环队列会人为的浪费掉一个空间，用作判满条件

二、功能

循环队列结构体

#ifndef __SEQ_QUEUE_H__
#define __SEQ_QUEUE_H__
#define MAX 8
#include <stdio.h>
#include <stdlib.h>

typedef int datatype;
typedef struct seq_que{
	datatype data[MAX];
	int front;
	int rear;
}queue,*queue_p;

//创建
queue_p creat_que();
//判空
int que_empty(queue_p S);
//判满
int que_full(queue_p S);
//入队
void push_queue(queue_p S,datatype data);
//出队
void pop_queue(queue_p S);
//打印
void out_put(queue_p S);
//销毁
void free_que(queue_p *S);

#endif

1.创建

//创建
queue_p creat_que(){
	queue_p S=(queue_p)malloc(sizeof(queue));
	if(S==NULL){
		printf("入参为空\n");
		return NULL;
	}
	S->front=0;
	S->front=S->rear;
	return S;
}

2.判空

//判空
int que_empty(queue_p S){
	if(S==NULL){
		printf("入参为空\n");
		return -1;
	}
return S->front==S->rear?1:0;

}

3.判满

int que_full(queue_p S){
	if(S==NULL){
		printf("入参为空\n");
		return -1;
	}
	return (S->rear+1)%MAX==S->front?1:0;
}

4.入队

//入队
void push_queue(queue_p S,datatype data){
	if(S==NULL){
		printf("入参为空\n");
		return;
	}
	if(que_full(S)){
		printf("队列已满\n");
		return;
}
S->data[S->rear]=data;
S->rear=(S->rear+1)%MAX;
}

5.出队

//出队
void pop_queue(queue_p S){
		if(S==NULL){
		printf("入参为空\n");
		return;
	}
		if(que_empty(S)){
			printf("队列为空\n");
			return;
		}
S->front=(S->front+1)%MAX;
}

6.打印

//打印
void out_put(queue_p S){
		if(S==NULL){
		printf("入参为空\n");
		return;
	}
		//符合队列的性质，从头开始打印
		//先保留一份队头元素的下标
		int temp=S->front;
		while(temp!=S->rear){
			printf("%d ",S->data[temp]);
			temp=(temp+1)%MAX;
		}
		putchar(10);
}

7.销毁

//销毁
void free_que(queue_p *S){
	if(S==NULL || *S==NULL){
		printf("入参为空\n");
		return; 
	}
	free(*S);
	*S=NULL;
}