Skip to main content

队列

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

  • 空队列的时候,frontrear 都指向头结点。

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;
}