13518219792
/*
1、队列:一端进，另一端出；队列由两个参数决定，front(头),rear(尾)；
头指针指向头一个元素，尾指针指向指向最后一个元素的下一存储单元；若数组长度为n，当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。
出队：头指针往上移动，
入队：尾指针向上移动，故：静态队列只能是循环队列，不然出队的元素占用的空间
永远无法重复利用。
1）：队列的初始化:front,rear的值都是零、
2）：队列非空：front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元
3) ：队列空:front和rear的值相等，但不一定是零
4）：动态队列：链表实现
静态队列：数组实现
2、循环队列:
出队:f = (f+1) % 数组长度
入队：r = (r+1) % 数组长度
+++++++++++++++++++++
+ +
+ +<----r
+ +
+++++++++++++++++++++
+ +
+ c +
+ +
+++++++++++++++++++++
+ +
+ b +
+ +
+++++++++++++++++++++
+ +
f --->+ a +
+ +
+++++++++++++++++++++
如何判断循环队列是否为空: 如果f == r 就一定为空
如何判断队列已满：
1）增加一个标志n记录队列元素的个数，当n = 数组长度-1时，就满了。
2)if((r+1)%arr.length == f){
队列已满
}
通常使用第二种
队列的具体应用:
所有和时间有关的操作都有队列的影子。
*/
#include
#include
//静态循环队列(数组实现)程序演示
typedef struct Queue
{ int length;
int *pBase;
int front;
int rear;
}QUEUE,* PQUEUE;
//初始化队列
void init(PQUEUE pQ,int length);
//判断队列是否已满
bool is_full(PQUEUE pQ);
//判断队列是否为空
bool is_empty(PQUEUE pQ);
//遍历
void traverse(PQUEUE pQ);
//入队 r = (r+1) % 数组长度
bool en_queue(PQUEUE pQ,int val);
//出队 f = (f+1) % 数组长度
bool de_queue(PQUEUE pQ,int * val);
int main(void)
{
QUEUE q;
init(&q,6);
en_queue(&q,1);
en_queue(&q,2);
en_queue(&q,3);
en_queue(&q,4);
en_queue(&q,5);
traverse(&q);
int a = 0;
de_queue(&q,&a);
printf("出队的元素是:%d\n",a);
traverse(&q);
getchar();
return 0;
}
//初始化队列
void init(PQUEUE pQ,int length)
{ //分配内存
pQ->pBase =(int *) malloc(sizeof(int) * length);
pQ->length = length;
pQ->front = 0;
pQ->rear = 0; //下标的都是0
}
//判断队列是否已满
bool is_full(PQUEUE pQ)
{
if((pQ->rear + 1) % (pQ->length) == pQ->front)
{
return true;
}
else
{
return false;
}
}
//判断队列是否为空
bool is_empty(PQUEUE pQ)
{
if(pQ->front == pQ->rear)
{
return true;
}else
{
return false;
}
}
//入队
bool en_queue(PQUEUE pQ,int val)
{
if(is_full(pQ))
{
printf("队列已满\n");
return false;
}
pQ->pBase[pQ->rear] = val;
//入队，尾角标增加
pQ->rear = (pQ->rear+1)%(pQ->length);
return true;
}
//出队
bool de_queue(PQUEUE pQ,int * val)
{
if(is_empty(pQ)){
printf("队列已空");
return false;
}
*val = pQ->pBase[pQ->front];
pQ->front = (pQ->front + 1) % (pQ->length);
return true;
}
//遍历
void traverse(PQUEUE pQ)
{
int i = pQ->front;
while(i !=pQ->rear)
{
printf("%d\t",pQ->pBase[i]);
i = (i + 1) % (pQ->length);
}
}
