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

半生瓜的blog

发布于 2023-05-13 13:29:27

53600

代码可运行

文章被收录于专栏：半生瓜のblog半生瓜のblog

运行总次数：0

代码可运行

队列

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

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

数组实现(顺序存储)

设立一个队头指针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)的队列文件。