重点(先进先出)
队满:(rear+1)%m== rear 循环队
队空:front==rear
循环队列((Q->rear+1)%M):rear:为队尾
M:为队列可存数据的最大值
队列的应用:模拟服务前台的排队现象、模拟打印机缓冲区
队列的简单实现(顺序存储)
一:队的结构体元素
typedef struct{
QElemType *base;//初始化的动态分配储存空间
int rear;//队尾指针,指向队尾元素的下一位置
int front;//队头指针,指向对头元素
}SqQueue;
二:入队(重要代码)
if((Q->rear+1)%MAXQSIZE==Q->front) return 0;
//数据入队
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXQSIZE;
//先入队在移队尾指针
三:出队(重要代码)
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
四:完整源代码
#include <stdio.h>
#include <stdlib.h>
#define MAXQSIZE 100//最大队列长度
typedef int QElemType;
typedef struct{
QElemType *base;//初始化的动态分配储存空间
int rear;//队尾指针,指向队尾元素的下一位置
int front;//队头指针,指向对头元素
}SqQueue;
//初始化队列:1,分配空间 2,设置front、 rear
int InitSqQueue(SqQueue *Q)
{
//分配空间
Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(Q->base==NULL) return 0;
Q->front=Q->rear=0;//此时是空队
return 1;
}
//入队:在队尾rear指示的位置插入元素
int EnSqQueue(SqQueue *Q,QElemType e)
{
//队满判断
if((Q->rear+1)%MAXQSIZE==Q->front) return 0;
//数据入队
Q->base[Q->rear]=e;
//新队尾位置
Q->rear=(Q->rear+1)%MAXQSIZE;
return 1;
}
//显示对列中的已有数据
void display(SqQueue *Q)
{
QElemType tmp;
tmp=Q->front;
while(tmp<=Q->rear-1)
{
printf("%d ",Q->base[tmp]);
tmp++;
}
}
//出队
int OutSqQueue(SqQueue *Q,QElemType *e)
{
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
return 1;
}
int main()
{
SqQueue Q;
int flag;
QElemType e;
flag=InitSqQueue(&Q);
if(flag==0)
printf("分配队列空间失败\n");
else
{
printf("分配队列空间成功\n");
}
EnSqQueue(&Q,10);
EnSqQueue(&Q,30);
EnSqQueue(&Q,20);
display(&Q);
OutSqQueue(&Q,&e);
printf("\n出队的是%d\n",e);
return 0;
}
网友评论