文章目录
一、队列
1、队列的定义
2、队列的顺序实现
2.1、初始化
//初始化
void InitQueue(SqQueue &Q){
Q.front=Q.rear=0;
}
//判断是否为空
bool QueueEmpty(SqQueue Q){
if(Q.front==Q.rear)
return false;
else
return true;
}
2.2、入队
队列已经满了的判断条件
队列已满的条件：rear==MaxSize ???
bool EnQueue(SqQueue &Q,int x){
//判断队列是否已满
if((Q.rear+1)%MaxSize==Q.front)
return false;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
return true;
}
形成循环队列
2.3、出队
bool BeQueue(SqQueue &Q,int &x){
if(Q.front==Q.rear)
return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
2.4、查找
bool GerHead(SqQueue Q,int &x){
if(Q.front==Q.rear)
return false;
x=Q.data[Q.front];
return true;
}
队列中的元素个数
(rear+MaxSize-front)%MaxSize
2.5、判断队列 满/空
定义一个size，满是size=MaxSize，空是size=0
定义一个tag，删除操作tag=0，插入操作tag=1，判断，
队满：front==rear&&tag==1,队空：front==rear&&tag==0
两种对尾指向的方式
牺牲一个空间，判断对满，还是队空
3、队列的链式实现
3.1、初始化
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front=NULL;
}
3.2、入队
void EnQueue(LinkQueue &Q,int x){
LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}
3.3、出队
4、双端队列
