[数据结构] 队列
队列的基本概念
队列(Queue),是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队,删除元素称为出队。其操作特性是先进先出
队列的常见操作:
函数名 | 功能 |
---|---|
InitQueue(*Q) | 初始化队列,构造一个空队列Q |
QueueEmpty(Q) | 判断队列空 |
EnQueue(*Q, x) | 入队,若队列未满,将x加入 |
DeQueue(*Q, *x) | 出队,若队列非空,删除队头元素 |
GetHead(*Q, *x) | 读队头元素 |
队列的顺序存储结构
队列的顺序存储
队列的顺序实现是分配一块连续的存储单元存放队列中的元素,并设置两个指针:队头指针front和队尾指针rear。
存储类型结构体如下:
#define MaxSize 50
typedef struct {
int data[MaxSize];
int front, rear;
}Queue;
初始时:Q->front = Q->rear = 0;(如下图1)
进队:队列不满时,先送值到队尾元素,再将队尾指针加一;(如下图2)
出队:队列非空时,先取队头元素值,再将队头指针加一。(如下图3)
我们能不能使用Q->rear == MaxSize作为队列满的条件呢?
答案是:不能!!
如下图4所示,队列中仅有一个元素时,仍满足该条件,但此时队列出现上溢出。
这种溢出不是真正的溢出,在data数组中仍然存在很多可以存放元素的空位置,是假溢出。
循环队列
为了解决上文提到的假溢出,我们引入了循环队列——把顺序队列的表从逻辑上视作一个环,当队首指针Q->front = MaxSize - 1后,再向前一个位置就自动回到0。
一些运算
初始时:Q->front = Q->rear = 0;
队首指针进1: Q->front = (Q->front + 1) % MaxSize;
队尾指针进1: Q->rear = (Q->rear + 1) % MaxSize;
队列长度: (Q->rear + MaxSize - Q->front) % MaxSize;
判空
显然队空的条件是Q->front == Q->rear;
那么,当入队元素的速度快于出队元素的速度,会发生什么呢?
===》队尾指针会很快赶上队首指针,如下图d1所示。
为了区分是队空还是队满,有三种处理方式:
-
如下图d2,牺牲一个单元来区分队空和队满,入队时少用一个队列单元,约定以”队头指针在队尾指针的下一个位置作为队满的标志“
队满条件:(Q->rear + 1) % MaxSize == Q->front;
队空条件: Q->front == Q->rear;
队列元素个数: (Q->rear - Q->front + MaxSize) % MaxSize
-
类型中增设一个size数据成员,用于表示元素个数。删除成功size减一,插入成功size加一。队空时,Q->size == 0;队满时, Q->size == MaxSize。
-
类型中增设一个tag数据成员,以区分是队空开始队满。删除成功置tag=0,若导致 Q->front == Q->rear,则队空;插入成功置1,若导致 Q->front == Q->rear,则队满。
接下来我们来看图,图示循环队列出入队:
代码
初始化
void InitQueue(Queue *Q) {
Q->rear = Q->front = 0;
}
判空
bool IsEmpty(Queue *Q) {
return Q->rear == Q->front;
}
入队
void EnQueue(Queue *Q, int x) {
if((Q->rear + 1) % MaxSize == Q->front)
return ;
Q->data[Q.rear] = x;
Q->dear = (Q->dear + 1) % MaxSize;
}
出队
void DeQueue(Queue *Q, int *x) {
if(IsEmpty(Q))
return ;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
}
队列的链式存储结构
队列的链式表示称为链队列,实际上是一个同时又队头指针和队尾指针的单链表。头指针指向队头节点,尾指针指向队尾节点。
结构体:
typedef struct LinkNode {
int data;
struct LinkNode *next;
}LinkNode;
typedef struct {
LinkNode *front, *rear;
}LinkQueue;
以上图源来自我的大佬同学,作者:Amαdeus,出处:https://www.cnblogs.com/MAKISE004/p/17063234.html
代码
初始化
void InitQUeue(LinkQueue *Q) {
Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
Q->front->next = NULL;
}
判空
bool IsEmpty(LinkQueue *Q) {
return Q->front == Q->rear;
}
入队
void EnQueue(LinkQueue *Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
}
出队
void DeQueue(LinkQueue *Q, int *x) {
if(IsEmpty(Q))
return ;
LinkNode *m = Q->front->next;
x = p->data;
Q->front->next = m->next;
if(Q->rear == m)
Q->rear = Q->front;
free(m);
}
写在最后
画图花了好长时间,果然昨天先写数组是一种正确的选择(经过一学期的最优化学习,我的LaTeX和markdown功底已经突飞猛进了(我的意思不是这学期的课只学会了LaTeX),敲代码总比画图快)。好了,开玩笑归开玩笑,还是希望学有所成的!
热门相关:唐朝小官人 总裁大人,又又又吻我了 娇妻如云 明朝败家子 资本大唐