数据结构——队列编程实现

定义：队列简称队，是一种运算受限的线性表。

把进行插入的一端叫做队尾(rear)
把进行删除的一端叫做对头(front)
插入称为进队或者入队 删除称为出队或者离队
顺序队的结构体定义：

#define Maxsize 10
typedef struct{
	ElemType data[Maxsize];
	int front,rear;
}sqQueue;
1
2
3
4
5

顺序队的四要素：初始时：front=rear=-1;
队空条件：front=rear;
队满条件：rear=Maxsize-1
元素e进队：rear++，data[rear]=e
元素1出队：front++,data[front]=e

1.初始化initsQueue(q)

void initsQueue(sqQueue *&q){
	q=(sqQueue *)mallo(sizeof(sqQueue)){
	q->front=q->reae=-1;
}
1
2
3
4

}
2.销毁队列DestroyQueue()

void DestroyQueue(sqQueue *&q){
	free(q);
}
1
2
3

3.判断队列是否为空QueueEpty(q)

bool QueueEmpty(sqQueue *q){
	return(q->front==q->rear);
}
1
2
3

4.进队列enQueue(q,e)

bool enQueue(sqQueue *&q,ElemType e){
	if(q->rear==Maxsize-1) return false;
	q->rear++;
	q->data[rear]=e;
	return true;
}
1
2
3
4
5
6

5.出队列deQueue(q,e)

bool deQueue(sqQueue *&q,ElemType &e){
	if(q->front==q->rear) return false;
	q->front++;
	e=q->data[q->front]
	return true;
}
1
2
3
4
5
6

循环队列四要素：
队空条件：rear=front
队满条件：(rear+1)%Maxsize=front
进队e操作：rear=(rear+1)%Maxsize
出队操作：front=(front+1)%Maxsize

//重点：
已知front,rear,求队中元素的个数count;
count=(rear-front+Maxsize)%Maxsize
已知front,count,求rear
rear=(front+count)%Maxsize
已知rear，count,求front
front=(rear-count+Maxsize)%Maxsize

//循环队列的结构体定义

typedef struct{
	ElemType data[Maxsize]
	int front;
	int count;
}QuType;
1
2
3
4
5

四要素：
队空：count=0
队满条件：count=Maxsize
进队e操作：rear=(rear+1)%Maxsize
出队操作:front=(front+1)%Maxsize