一、队列 FIFO
特点:先进先出,后进后出
允许从一段插入数据,另一端删除数据的线性存储结构
队尾:插入数据 入队
队头:删除数据 出队
管道实质上也是一个队列。
用途:缓存数据(主要是避免两者速度不匹配的,数据存取速度不匹配。)
二、队列类型
2.1、顺序队列
顺序队列---------》假溢出-----------------》循环队列(如果用顺序队列里面,我们主要用的就是循环队列)
队列中的假溢出是指当队列的存储空间实际上还有空闲位置时,由于队列的访问限制导致无法插入新的元素,从而表现出“溢出”的假象。在循环队列中,这种情况尤为常见。
循环队列是一种使用数组存储数据元素的线性数据结构,它利用数组的环状特性来处理队列的入队和出队操作。在循环队列中,通常有两个指针front和rear分别指向队列的第一个元素和最后一个元素的下一个位置。队列的空和满的条件是相同的,都是(rear + 1) % queueSize == front,其中queueSize是队列的容量。因此,当队列满时,即使数组中有空间,也会因为队列的规则认为它已经满了,无法再添加新元素,这时如果尝试入队,就会产生假溢出。
解决假溢出的方法
为了避免假溢出,可以在定义循环队列的时候预留一个位置,通常在初始化队列时,将front和rear都设置为0,但在判断队列满的条件中加入一个额外的判断条件,比如rear == front时队列为空,而(rear + 1) % queueSize == front时队列为满。
2.2、链式队列
1、创造队列
Queue_t *create_queue()
{
Queue_t *queue = malloc(sizeof(Queue_t));
if(queue == NULL)
{
return NULL;
}
queue->pfront = NULL;
queue->prear = NULL;
queue->clen =0;
pthread_mutex_init(&(queue->mutex),NULL);
return queue;
}
2、入队
int push_queue(Queue_t *queue,QDataType data)
{
QNode_t *qnode = malloc(sizeof(QNode_t));
if(qnode == NULL)
{
perror("malloc fail");
return -1;
}
qnode->data = data;
qnode->pnext = NULL;
if(is_empty_queue(queue))
{
queue->prear = qnode;
queue->pfront = qnode;
}
queue->prear->pnext = qnode;
queue->prear = qnode;
queue->clen++;
return 0;
}
3、出队
int pop_queue(Queue_t *queue,QDataType *data)
{
if(is_empty_queue(queue))
{
return 0;
}
QNode_t *qnode = queue->pfront;
queue->pfront = qnode->pnext;
if(data != NULL)
{
*data = qnode->data;
}
free(qnode);
if(NULL == queue->pfront)
{
queue->prear = NULL;
}
queue->clen--;
return 0;
}
4、得到队头元素
int get_queue_front(Queue_t *queue,QDataType *data)
{
QNode_t *q = queue->pfront;
*data = q->data;
return 0;
}
5、清空队列
void clear_queue(Queue_t *queue)
{
while(!is_empty_queue(queue))
{
pop_queue(queue,NULL);
/*
QNode_t *qnode = queue->pfront;
queue->pfront = qnode->pnext;
free(qnode);
queue->clen--;*/
}
}
6、销毁队列
void destory_queue(Queue_t *queue)
{
clear_queue(queue);
free(queue);
}
标签:Queue,NULL,qnode,队列,queue,数据结构,data
From: https://blog.csdn.net/weixin_63722559/article/details/141963676