环形队列-基于队头指针和队列中元素的个数的另一种实现
程序员文章站
2022-06-06 20:55:59
...
由队头指针和元素个数进行如下计算:
已知front、rear,求队中元素个数:
count=(rear-front+MaxSize)%MaxSize
已知front、count,求rear:
rear=(front+rear)%MaxSize
已知rear、count,求front:
front=(rear-count+MaxSize)%MaxSize
环形队列的基本操作:
队空条件:count=0
队满条件:count=MaxSize
进队e操作:rear=(rear+1)%MaxSize; 将e放在rear处
出队操作:front=(front+1)%MaxSize;取出front处元素e;
这样的环形队列中最多可放置MaxSize个元素。
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int front; //队头指针
int count; //队列中元素个数
} QuType;
void InitQueue(QuType *&qu) //初始化队运算算法
{ qu=(QuType *)malloc(sizeof(QuType));
qu->front=0;
qu->count=0;
}
void DestroyQueue(QuType *&qu)
{
free(qu);
}
bool EnQueue(QuType *&qu,ElemType x) //进队运算算法
{ int rear; //临时队尾指针
if (qu->count==MaxSize) //队满上溢出
return false;
else
{ rear=(qu->front+qu->count)%MaxSize; //求队尾位置
rear=(rear+1)%MaxSize; //队尾循环增1
qu->data[rear]=x;
qu->count++; //元素个数增1
return true;
}
}
bool DeQueue(QuType *&qu,ElemType &x) //出队运算算法
{ if (qu->count==0) //队空下溢出
return false;
else
{ qu->front=(qu->front+1)%MaxSize; //队头循环增1
x=qu->data[qu->front];
qu->count--; //元素个数减1
return true;
}
}
bool QueueEmpty(QuType *qu) //判队空运算算法
{
return(qu->count==0);
}
void main()
{
QuType *q;
ElemType e;
InitQueue(q);
EnQueue(q,1);
EnQueue(q,2);
EnQueue(q,3);
EnQueue(q,4);
printf("出队顺序:");
while (!QueueEmpty(q))
{
DeQueue(q,e);
printf("%d ",e);
}
printf("\n");
DestroyQueue(q);
}
上一篇: 看图说话之二叉排序树
下一篇: 双队列的一种实现