[数据结构] 队列

队列的基本概念

队列(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),敲代码总比画图快)。好了,开玩笑归开玩笑,还是希望学有所成的!

热门相关:唐朝小官人   总裁大人,又又又吻我了   娇妻如云   明朝败家子   资本大唐