博客

循环队列
1.静态队列为什么必须是循环队列
因为不是循环队列，f只能增,会浪费存储空间

2.循环队列需要几个参数来确定
两个参数
font
rear

3.循环队列各个参数的含义
两个参数在不同场合意义不一样
1.对列初始化
font和rear的值都是0
2.队列非空
font是队列的第一个元素
rear是队列的最后一个有效元素
3.队列空
font和rear值相等，但不一定都是0

4.循环队列入队和出队的伪算法
入队：
1.将值存入rear指向的数组
2.rear = (rear+1)%数组长度 1%6 = 1；6%6 = 0；可以循环了

出队：
1.font = (font+1)%数组长度

5.如何判断循环队列是否为空
font和rear值相等,队列为空

6.如何判断循环队列是否为满
方法一：多一个标准参数
方式二：少用一个元素，满只有N-1个元素，f=(r+1)%数组长度表明已满

一、循环队列queue的初始化

思路图：这个图是循环队列的大致图，关于循环队列想着这个图来操作即可；

结构体QUEUE
    用pBase保存创建出来的数组名
    front和rear保存数组的角标（不是指针哦）
    这样一来 pBase[front]和pBase[rear]表示循环队列中数组的元素值；

代码：

void init(QUEUE * pQ){
	pQ->pBase = (int*)malloc(sizeof(int)*6);
	pQ->front = pQ->rear = 0;
	return;
}

二、入队

思路：
    1.先判断队列是否满，如果满了就不能入队，引入一个函数判断是否满
    2.没满就给数组赋值，然后角标rear后移，这里的后移不单单是rear=rear+1,要写出
        rear = (rear + 1)%数组长度，就可以实现循环
     

bool en_queue(QUEUE * pQ,int val){
	if(full_queue(pQ)){ 
		return false;
	}else{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1)%6;
		return true;
	}
}
bool full_queue(QUEUE * pQ){
	if(pQ->front == (pQ->rear +1)%6){
		return true;
	}
	else{
		return false;
	}
}

三、遍历

思路：
    1.由于循环队列的元素是用f数到r的，f和r没有固定的大小之别，所以用r保存f
    2.依次边输出每一个数组元素，边r后移即可
    

void traverse_queue(QUEUE * pQ){
	int r = pQ->front;
	while(r!=pQ->rear){
		printf("%d\t",pQ->pBase[r]);
		r=(r+1)%6;
	}
}  

四、出队

思路：
    1.先判断队列是否空，如果空了就不能出队，引入一个函数判断是否为空
    2.没空就给数组出列，先保存出列的数组值，再f后移即可
     

bool empty_queue(QUEUE * pQ){
	if(pQ->front == pQ->rear){
		return true;
	}else{
		return false;
	}
}
bool out_queue(QUEUE * pQ,int * pVal){
	if(empty_queue(pQ)){
		return false;
	}else{
		* pVal = pQ->pBase[pQ->front];
		pQ->front = (pQ->front + 1)%6;
		return true; 
	}
}

主函数代码：

#include <stdio.h> 
#include <malloc.h>
typedef struct Queue{
	int * pBase;
	int front;
	int rear;
}QUEUE;

void init(QUEUE *);
bool en_queue(QUEUE *,int );
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool empty_queue(QUEUE *);
bool out_queue(QUEUE *,int *);

int main(void){
	QUEUE Q;
	init(&Q);
	
	en_queue(&Q,1);
	en_queue(&Q,2);
	en_queue(&Q,3);
	en_queue(&Q,4);
	en_queue(&Q,5);
	en_queue(&Q,6);
	traverse_queue(&Q);
	
	int val;
	if(out_queue(&Q,&val)){
		printf("\n出对成功！出队元素是:%d\n",val); 
	}else{
		printf("队列为空，无法出队！"); 
	}
	traverse_queue(&Q);
	
	return 0;
} 

运行结果：