一、结构体定义
1.顺序队
typedef struct
{
int data[maxSize];
int front,rear;
}SqQueue;
2.链队
(1)队结点类型
typedef struct QNode
{
int data;
struct QNode *next;
}QNode;
(2)链队定义
typedef struct
{
QNode *front,*rear;
}LiQueue;
二、顺序队操作(循环队列)
1.队空
qu.rear==qu.front;
2.队满
(qu.rear+1)%maxSize==qu.front;
3.进队
int enQueue(SqQueue &qu,int x)
{
if((qu.rear+1)%maxSize==qu.front)
return 0;
qu.rear=(qu.rear+1)%maxSize;
qu.data[qu.rear]=x;
return 1;
}
4.出队
int deQueue(SqQueue &qu,int x)
{
if(qu.front==qu.rear)
return 0;
qu.front=(qu.front+1)%maxSize;
x=qu.data[qu.front];
return 1;
}
三、链队操作
1.队空
lqu->rear==NULL; //(或lqu->front==NULL)
2.队满
//不存在(假设内存无限大)
3.初始化
void initQueue(LiQueue *&lqu)
{
lqu=(Liqueue*)malloc(sizeof(LiQueue));
lqu->front=lqu->rear=NULL;
}
4.入队
void enQueue(LiQueue *lqu,int x)
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
p->data=x;
p->next=NULL;
if(lqu->rear==NULL) //若队列为空,新结点既是队首结点,又是队尾结点
lqu->front=lqu->rear=p;
else
{
lqu->rear->next=p;
lqu->rear=p;
}
}
5.出队
int deQueue(LiQueue *&lqu,int &x)
{
QNode *p; //仅用来释放空间
if(lqu->rear==NULL)
return 0;
p=lqu->front;
if(lqu->front==lqu->rear) //队列中只有一个结点时出队操作需要特殊处理
lqu->front=lqu->rear=NULL;
else
lqu->front=lqu->front->next;
x=p->data;
free(p);
return 1;
}
标签:qu,队列,lqu,int,front,QNode,rear
From: https://www.cnblogs.com/unravel-CAT/p/16631570.html