数据结构（队列Queue）

一、队列

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; 
} 

1
2
3
4
5
6
7
8
9
10
11
12

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;
}
1
2
3
4
5
6
7
8

形成循环队列

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;
} 
1
2
3
4
5
6
7

2.4、查找

bool GerHead(SqQueue Q,int &x){
	if(Q.front==Q.rear)
		return false;
	x=Q.data[Q.front];
	return true;
} 
1
2
3
4
5
6

队列中的元素个数
(rear+MaxSize-front)%MaxSize

2.5、判断队列 满/空

定义一个size，满是size=MaxSize，空是size=0

定义一个tag，删除操作tag=0，插入操作tag=1，判断，

队满：front==rear&&tag==1,队空：front==rear&&tag==0
1

两种对尾指向的方式

牺牲一个空间，判断对满，还是队空

3、队列的链式实现

3.1、初始化

void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front=NULL;
} 
1
2
3
4

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; 
}
1
2
3
4
5
6
7

3.3、出队

4、双端队列