跳到主要内容

队列

1. 基本概念​

  • 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

  • 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许插入的一端称为队头。

ZhzlF1.png

  • 同样是线性表，队列也有类似线性表的各种操作，不同的是插入操作只能在队尾进行，删除数据只能在队头进行。

  • 队列也有顺序存储和链式存储两种结构。

2. 队列的线性存储结构​

采用线性存储的队列，我们叫做顺序队列(Sequence Queue)，它其实就是用数组实现的。 但是如果用数组来实现队列的话，入栈和出栈操作都会使队首和队尾往后走，这样队首和队尾很快就会走到数组的边界，且数组的空间没有被充分利用。如图所示:

Zhz2zb.png

为了解决顺序队列没有合理利用数组空间的问题，我们摒弃队首在前面队尾在后面的这种按顺序的设 计，而是用变量 front 和变量 rear 来保存队首和队尾的下标，当队尾或队首走到最后一个元素后，再往后走就自动跳转到第一个元素，形成一个循环。这种队列称为循环队列(Circle Queue)。

ZhzMiK.png

2.1 循环队列结构设计​

#define QUEUE_SIZE 10

typedef int datatype;

struct seq_queue 	//循环队列结构设计
{
	datatype queue[QUEUE_SIZE];
	int front;		// 队首的下标
	int rear;		// 队尾的下标
	int size;		// 队列元素数量
};

2.2 循环队列初始化​

struct seq_queue *queue_init(void)
{
	struct seq_queue *q = malloc(sizeof(struct seq_queue));
	if(q != NULL)
	{
		q->front = 0;
		q->rear = 0;
		q->size = 0;
		return q;
	}
	return NULL;
}

2.3 判断队空和队满​

//空队
bool queue_empty(struct seq_queue *q)
{
	return q->front == q->rear && q->size == 0;
}
//满队
bool queue_full(struct seq_queue *q)
{
	return q->front == q->rear && q->size > 0;
}

2.4 循环队列入队操作​

void en_queue(struct seq_queue *q, datatype data)
{
	//1. 判断队是否满
	if(queue_full(q))
	{
		printf("队满了\n");
		return ;
	}
	//2. 把元素入队
	q->queue[q->rear] = data;
	q->size++;
	q->rear = (q->rear+1) % QUEUE_SIZE;
}

2.5 循环队列出队操作​

datatype de_queue(struct seq_queue *q)
{
	// 1. 出队
	datatype data = q->queue[q->front];
	q->size--;
	q->front = (q->front+1) % QUEUE_SIZE;
	
	return data;
}

2.5 循环队列的销毁​

void destory_queue(struct seq_queue **q)
{
	free(*q);
	*q = NULL;
}

3. 队列的链式存储结构​

队列的链式存储结构，其实就是线性表的单链表，只不过这个单链表只能尾进头出，简称为链队列。

  • 为了操作上的方便，会将队头指针指向链队列的头结点，而队尾指针指向终端结点。

ZhDTcS.png

  • 空队列的时候，front 和 rear 都指向头结点。

ZhDbQb.png

3.1 链式队列的结构设计​

typedef int datatype;

struct queue_node				//队列节点设计
{
	datatype data;
	struct queue_node *next;
};

struct queue					//队列管理结构
{
	struct queue_node *front;	//队头
	struct queue_node *rear;	//队尾
	int size;					//队列尺寸
};

3.2 链式队列的初始化​

struct queue *queue_init(void)
{
	struct queue *q = malloc(sizeof(struct queue));
	if(q != NULL)
	{
		//队头队尾默认为空
		q->front = NULL;
		q->rear = NULL;
		q->size = 0;
		return q;
	}
	return NULL;
}

3.3 判断队空​

bool queue_empty(struct queue *q)
{
	return q->size == 0;
}

3.4 链式队列的入队操作​

入队操作其实就是在链表尾部插入结点。

ZhDlyo.png

void en_queue(struct queue *q, datatype data)
{
	// 1. 创建节点
	struct queue_node *new = malloc(sizeof(struct queue_node));
	if(new == NULL)
	{
		printf("节点创建失败\n");
		return ;
	}
	new->data = data;
	
	//2. 判断链表是否为空
	if(queue_empty(q))
	{
		q->front = new;
		q->rear = new;
		q->size++;
		
		return ;
	}
	
	//3. 在队尾后边添加一个节点，并且把队尾更新到最新的节点
	q->rear->next = new;
	q->rear = new;
	q->size++;
}

3.5 链式队列的出队操作​

出队操作就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩下一个元素时，则需将 rear 指向头结点。

ZhD2JD.png

datatype de_queue(struct queue *q)
{
	//1. 出队
	struct queue_node *tmp = q->front;
	datatype data = tmp->data;	//临时存一下数据
	
	q->front = q->front->next; 
	q->size--;
	free(tmp);		
	//如果这个队列元素已经全部出队，那么需要让队尾指向空
	if(q->front == NULL)
		q->rear = NULL;
	
	return data;
}

3.6 链式队列的销毁​

void destory_queue(struct queue *q)
{
	//释放节点的所有空间
	struct queue_node *tmp = q->front;
	while(q->front != NULL)
	{
		q->front = q->front->next;
		free(tmp);
		tmp = q->front;
	}
	//把队列管理的成员全部重置
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
0%