【数据结构】队列(C++)

队列

队列是一种受限的线性表，它允许在一段进行删除操作，在另一端进行插入操作。

可以用数组实现，也可以用链表实现。

数组实现(顺序存储)

设立一个队头指针front,一个队尾指针rear，分别指向队头元素和队尾元素，rear-front为元素个数。

(数组实现中，其实就是下标。)

#define MAX_SIZE 10
typedef int DataType;

typedef struct Queue
{
	DataType queue[MAX_SIZE];
	int front;
	int rear;
}SeqQueue;

//初始化
void initQueue(SeqQueue* SQ)
{
	if (!SQ)//如果传递进来的是个空指针的话
	{
		return;
	}
	SQ->front = SQ->rear = 0;
}
//判断队列是否满了
bool isFull(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}

	if (SQ->rear == MAX_SIZE)
	{
		return true;
	}
	return false;
}
//判断队列是否为空
bool isEmpty(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	if (SQ->rear == SQ->front)
	{
		return true;
	}
	return false;
}
//入队
bool pushQueue(SeqQueue* SQ,DataType data)
{
	if (!SQ)
	{
		return false;
	}
	if (isFull(SQ))
	{
		return false;
	}
	SQ->queue[SQ->rear] = data;
	SQ->rear++;//队尾指针后移,插入之后rear"指向"当前位置的下一个位置。
	return true;
}
//输出
void printQueue(SeqQueue* SQ)
{
	if (isEmpty(SQ))
	{
		return;
	}
	int i = SQ->front;
	while (i < SQ->rear)
	{
		cout << SQ->queue[i]<<" ";
		i++;
	}
	cout << endl;
}

//出队-从表头开始删除
bool popQueue(SeqQueue* SQ)
{
	//就是删除第一个元素
	if (!SQ || isEmpty(SQ))
	{
		return false;
	}
	for (int i = SQ->front; i < SQ->rear; i++)
	{
		SQ->queue[i] = SQ->queue[i+1];
	}
	SQ->rear--;
	//直接对front进行操作的话空间会越来越小
	return false;
}
//获取队列首元素
DataType getFront(SeqQueue* SQ)
{
	if (!SQ)
	{
		return -1;
	}
	return SQ->queue[SQ->front];
}
//清空队列
bool destoryQueue(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	SQ->front = SQ->rear = 0;
	return true;
}
//获取长度-元素个数
int getElemsNum(SeqQueue* SQ)
{
	if (!SQ)
	{
		return 0;
	}
	return SQ->rear-SQ->front;//返回SQ->rear也一样，数组下标从0开始
}

链表实现(链式存储)

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

就是简化了单链表，加了些条件限制(一边进，一边出。)

typedef int DataType;
 
#define MAX_SIZE 100


//结点结构
typedef struct Qnode
{
	DataType data;
	struct Qnode* next;

}Qnode;


typedef Qnode* QueuePtr;

//用数组实现的队列rear指向的是最后一个的下一个，而用链表实现的队列rear指向的是最后一个

//队列的结构
typedef struct Queue
{
	int length;
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;

//初始化队列
bool initLinkQueue(LinkQueue* LQ)
{
	if (!LQ)
	{
		cout << "S";
		return false;
	}
	LQ->length = 0;
	LQ->front = LQ->rear = NULL;//把队头和队尾指针同时置空
	//初始化的置空可以想象成是有个“头结点”,判断队列中是否有元素就看front是否指向的是NULL
	//其实就是有个头结点，开始就已经new出来了
	return true;
}

//判断队列是否为空
bool isEmpty(LinkQueue* LQ)
{
	if (!LQ)
	{
		return false;
	}
	if (!LQ->front)
	{
		return true;
	}
	return false;
}
//判断队列是否满了
bool isFull(LinkQueue* LQ)
{
	if (!LQ)
	{
		return false;
	}
	if (LQ->length == MAX_SIZE)
	{
		return true;
	}
	return false;
}
//入队-从尾部
bool pushQueue(LinkQueue* LQ, DataType num)
{
	if (!LQ)
	{
		return false;
	}
	Qnode* node = new Qnode;
	node->data = num;
	node->next = NULL;

	if (isEmpty(LQ))
	{
		LQ->front = LQ->rear = node;
	}
	else
	{
		LQ->rear->next = node;
		LQ->rear = node;//定位到新的末尾结点
	}
	LQ->length++;
	return true;
}
//出队-从头部
bool popQueue(LinkQueue* LQ)
{
	if (!LQ || isEmpty(LQ))
	{
		return false;
	}
	Qnode* tempnode = LQ->front;
	LQ->front = LQ->front->next;
	delete tempnode;
	LQ->length--;
	//如果出了这个元素后为空，需要将rear也置空
	if (!LQ->front)
	{
		LQ->rear = NULL;
	}
	return true;
}
//打印输出
void printQueue(LinkQueue* LQ)
{
	if (!LQ || isEmpty(LQ))
	{
		return;
	}
	Qnode* tempnode = NULL;
	tempnode = LQ->front;
	while (tempnode)
	{
		cout << tempnode->data<<" ";
		tempnode = tempnode->next;
	}
	cout << endl;
}
//清空队列
bool clearQueue(LinkQueue* LQ)
{
	if (!LQ)
	{
		return false;
	}
	Qnode* tempnode = NULL;
	while (LQ->front)
	{
		tempnode = LQ->front->next;
		delete LQ->front;
		LQ->front = tempnode;
	}
	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
	return true;
}
//获取队列的首元素
bool getFront(LinkQueue* LQ, DataType* recv)
{
	if (!LQ || isEmpty(LQ))
	{
		return false;
	}
	if (!recv)
	{
		return false;
	}
	*recv = LQ->front->data;
	return false;
}
//获取队列元素个数
int getNums(LinkQueue* LQ)
{
	if (!LQ)
	{
		return 0;
	}
	return LQ->length;
}

实际应用

线程池中的任务队列

线程池——由一个任务队列和一组处理队列的线程组成。一旦工作进程需要处理某个可能“阻塞”的 操作，不用自己操作，将其作为一个任务放到线程池的队列，接着会被某个空闲线程提取处理。

循环队列

与数组实现队列中，出队方式相关，直接移动front(假溢出)，front前的元素全部抛弃，认为是空，下次直接覆盖上去。

判断是否满了,rear+1是否等于front

用模运算来循环

typedef int DataType;

#define MAX_SIZE 10

typedef struct Queue
{
	DataType queue[MAX_SIZE];
	int front;
	int rear;//rear一直在追front
}SeqQueue;

//初始化队列
bool initQueue(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	SQ->front = SQ->rear = 0;

	return 0;
}
//是否为满了
bool isFull(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	if ((SQ->rear + 1) % MAX_SIZE == SQ->front)//因为rear要指向front前的一个空的位置，所以真正只可以push进MAX_SIZE-1个
	{
		return true;
	}
	return false;
}
//是否为空
bool isEmpty(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	if (SQ->front == SQ->rear)
	{
		return true;
	}
	return false;
}
//入队
bool pushQueue(SeqQueue* SQ, DataType m_data)
{
	if (!SQ || isFull(SQ))
	{
		return false;
	}
	SQ->queue[SQ->rear] = m_data;
	//移动队尾指针
	SQ->rear = (SQ->rear + 1) % MAX_SIZE;
	return true;
}
//出队
bool popQueue(SeqQueue* SQ)
{
	if (!SQ || isEmpty(SQ))
	{
		return false;
	}
	//队首指针后移
	SQ->front = (SQ->front + 1) % MAX_SIZE;
	return true;
}
//打印输出
//从第一个位置之后，rear都指向一个空的位置
bool printQueue(SeqQueue* SQ)
{
	if (!SQ)
	{
		return false;
	}
	int index = SQ->front;
	while (index != SQ->rear)
	{
		cout << SQ->queue[index] << " ";
		index = (index + 1) % MAX_SIZE;
	}
	cout << endl;
	return false;
}
//计算元素个数
int getElemsNum(SeqQueue* SQ)
{
	if (!SQ)
	{
		return 0;
	}
	return (SQ->rear - SQ->front + MAX_SIZE) % MAX_SIZE;
}

优先队列

它的入队顺序没有变化，但是出队的顺序是根据优先级的高低来决定的，优先级高的先出。

还是要对比顺序存储和链式存储rear指向位置。

顺序存储rear指向最后一个的下一个位置

链式存储rear指向最后一个

using namespace std;

#define MAX_SIZE 10

typedef int DataType;

typedef struct Qnode//结点结构
{
	int priority;//优先级
	DataType data;
	struct Qnode* next;
}Qnode;

typedef struct Queue//队列结构
{
	int length;
	Qnode* front;
	Qnode* rear;
}Queue;

//初始化
bool initQueue(Queue* Q)
{
	if (!Q)
	{
		return false;
	}
	Q->front = Q->rear = NULL;
	Q->length = 0;
	return true;

}
//是否为空
bool isEmpty(Queue* Q)
{
	if (!Q)
	{
		return false;
	}
	if (Q->front == NULL)//空的，返回真，不空返回假，if(isEmprt(Q) != NULL)就是： 真的就直接return 
	{
		return true;
	}
	return false;
}
//是否满了
bool isFull(Queue* Q)
{
	if (!Q)
	{
		return false;
	}
	if (isEmpty(Q))
	{
		return false;
	}
	if (Q->length == MAX_SIZE)
	{
		return true;
	}
	return false;
}
//入队
bool pushQueue(Queue* Q, DataType _data, int _priority)
{
	if (!Q)
	{
		return false;
	}
	if (isFull(Q))
	{
		return false;	
	}

	Qnode* _node = new Qnode;
	_node->priority = _priority;
	_node->data = _data;
	_node->next = NULL;
	
	//空队列
	if (isEmpty(Q))
	{
		Q->front = Q->rear = _node;
	}
	else
	{
		Q->rear->next = _node;
		Q->rear = _node;//定位到新的结尾
	}
	Q->length++;

	return true;
}
//出队列——按照优先级
bool popQueue(Queue* Q)
{
	if (!Q || isEmpty(Q))
	{
		return false;
	}
	
	Qnode* recvPrev = NULL;//存储要删除结点的前一个结点
	Qnode* start = NULL;
	Qnode* startNext = NULL;
	Qnode* deleteTmp = NULL;

	start = Q->front;
	startNext = start->next;

	recvPrev = start;//默认要删除的是第二个,所以存的是第一个结点

	//特殊情况1，当前队列中就一个结点
	if (!startNext)
	{
		delete start;
		Q->front = Q->rear = NULL;
		Q->length--;
		return true;
	}

	//正常情况,完整的遍历一遍
	while (startNext)
	{
		if (startNext->priority > start->priority)
		{
			recvPrev = start;
		}
		start = startNext;
		startNext = startNext->next;		
	}

	//特殊情况2，第一个结点是优先级最高的
	//这样得到的recvPrev是第一个结点了，也有可能是为了删除第二个结点
	//所以要进行一下验证,验证是否要删除的是第一个结点
	Qnode* difFandS = NULL;
	difFandS = Q->front->next;
	if (recvPrev->priority > difFandS->priority)
	{
		//如果第一个结点的优先级大于第二个结点
		delete recvPrev;
		Q->front = difFandS;
		Q->length--;
		return true;
	}

	//出来后recvPrev就是要删除结点的前一个结点
	deleteTmp = recvPrev->next;
	recvPrev->next = deleteTmp->next;
	delete deleteTmp;

	Q->length--;
	return true;
}
//打印
bool printQueue(Queue* Q)
{
	if (!Q)
	{
		return false;
	}
	//补充提示注意:根据具体的返回内容来书写判断语句条件
	if (isEmpty(Q))//空的，返回真，不空返回假，if(isEmprt(Q))就是： 返回了真的就直接return 
	{
		cout << "空的，别打印了" << endl;
		return false;
	}
	Qnode* tempnode = Q->front;
	while (tempnode)
	{
		cout << "<" << tempnode->data << "," << tempnode->priority << ">" << " ";
		tempnode = tempnode->next;
	}
	cout << endl;
	return true;
}
//清空整个队列
bool clearQueue(Queue* Q)
{
	if (!Q)
	{
		return false;
	}
	
	Qnode* tempnode = NULL;
	while (Q->front)
	{
		tempnode = Q->front->next;
		delete Q->front;
		Q->front = tempnode;
	}
	
	Q->front = Q->rear = NULL;
	Q->length = 0;
	return false;
	
}

动态顺序队列

使用链式存储(链表)实现的队列即为动态顺序队列，前面已经实现过，不再重复。

高并发WEB服务器队列的应用

在高并发 HTTP 反向代理服务器 Nginx 中，存在着一个跟性能息息相关的模块 ——文件缓存。

经常访问到的文件会被 Nginx 从磁盘缓存到内存，这样可以极大的提高 Nginx 的并发能力，不过因为 内存的限制，

当缓存的文件数达到一定程度的时候就会采取淘汰机制，

优先淘汰进入时间比较久或是最近访问很少(LRU)的队列文件。

具体实现方案：

使用双向循环队列保存缓存的文件节点，这样可以实现多种淘汰策略：

比如：如果采用淘汰进入时间比较久的策略，就可以使用队列的特性，先进先出

如果要采用按照 LRU(进入时间 or 最近访问较少)，就遍历链表，找到节点删除。