队列

认识队列

和栈一样,队列是操作受限的线性表,只允许再一端删除,在一端插入,正因如此,队列是一种先进先出的数据结构。

规定: 允许插入的一端,叫做队尾;允许删除的一端叫做队头

队就和平常排队打饭是一样的,先到先打饭,不允许插队。

队列的基本操作

队列和栈的操作基本类似,常用的如下

  1. InitQueue(&Q)

    初始化队列 ,构造一个空的队列。

  2. DestoryQueue(&Q)

    销毁队列,让其不存在

  3. ClearQueue(&Q)

    清空队列,让他为空队列

  4. QueueEmpty(Q)

    判断Q是否为空

  5. GetHead(Q,&e)

    用e带回 Q的队头元素

  6. EnQueue(&Q,e) 入队

    插入元素e,使他成为新的队尾的元素

  7. DeQueue(&Q,&e) 出队

    产出队头元素,用e带回删除数据

  8. QueueLength(Q)

    返回队列长度

双端队列

双端队列也是操作首先的线性表,插入和删除只能两端进行。这两端成为端点,分别称为 端点1和端点2 。

这样双端队列有如下变种:

  1. 端点1 可以删除和插入 ,端点2只能删除 输出受限的双端队列
  2. 端点1 可以删除和插入 ,端点2只能插入 输入受限的双端队列

那么双端队列可以看作 两个栈底相接的结构

队列的链式实现---链队列

存储结构就两种,链式OR顺序。现在探讨队列的链式(带头节点)实现,这里我在提醒一下,如果不带投结点的情况,请务必多考虑删除第一个元素和在一个位置上插入元素特殊情况,当然对于队列,我们操作的就是两端,故而我们使用带头节点的单链表。

定义

如果我们链表头作为队头,链表尾作为队尾,如果在队头删除元素还好说,那么在队尾删除元素(出队),就需要遍历到最后一个结点,这段就多造成一个时间复杂度为 O(n)的循环。当然即使我们反过来,队头在表尾,但是插入元素的时候还是需要遍历。但是这样的问题,也好解决,使用 一个指针存储表尾的结点。

//链式存储的结点
typedef struct QNode {
    ElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

//队列的定义
typedef struct
{
    QueuePtr front,rear;//队头,队尾
}LinkQueue;

那么其实 Q.front 其实就头指针(L)指向头节点,首元素就是Q.front->next;

image-20210323182009491

初始化InitQueue

构造一个空的队列,队列何时为空? 当然是 队头和队尾指向同一个节点!其他的操作和链表没有差区别了,如果还有疑问,方可复习数据结构 第二章 线性表2:单链表

Status InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//分配头节点空间
    if(!Q.front)
        exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;
}

销毁队列DestoryQueue

销毁队列和销毁单链表并无差异。while遍历节点即可,负责扫描的指针使用 rear即可。

Status DestoryQueue(LinkQueue &Q)
{
    while(Q.front)
    {
        Q.rear=Q.front->next;
        free(front);
        Q.front=Q.rear;
    }
    return OK;
}

入队EnQueue

入队和出队是队列的核心操作。

入队要考虑队列是否满了,由于我们采用的是动态链表,也就无需担心这一点了,我们只需把插入到表尾即可。

Status EnQueue(LinkQueue& Q,Elemtype e)
{
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e;
    p->next=NULL;
    Q.rear.next=p;
    Q.rear=p;
    return OK;
}

出队DeQueue

出队就是在表头删除数据,那么 Q.front->next=Q.front->next->next即可 ?

我们还需要注意如下几点 ,

  • 如果队列已经空了,就不要删除了 。 判定队列是否为空 Q.front==Q.real
  • 如果删除了最后一个元素,那么队列就该为空了,需修改Q.real=Q.front,否则Q.real 指针悬空
Status DeQueue(LinkQueue& Q,ElemType e)
{
    if(Q.front==Q.real)
        return ERROR;
    QueuePtr p==Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.real==p)//如果删除的是最后一个元素
        Q.real=Q.front;
    free(p);
    return OK;
}

总结

链表实现队列,一般队列不会满的。如果掌握了链表,那么实现队列就是否简单了。

其他的操作就十分简单了,不在论述。

如果我们经常需要知道队列的长度,如果每次都需要while去遍历,那是时间复杂度是高居不下的,我们使用一个int变量来保存本信息。千万别把数据结构教条化

队列顺序实现--循环队列

和链式存储实现一样,需要两个指针来标记队尾和队头,但是如果采用静态顺序表来存储,我们就不可避免的遇到了一个问题---队列满了。动态的和上述链表实现大同小异,不在论述。

为了方便后面论述,规定:静态顺序表表头为 队头,表尾为队尾。

定义

#define MaxQSize 100//队列的最大长度
typedef struct {
    ElemType *base;
    int front;
    int rear;
}SqQueue;

初始化 InitQueue

初始化一个空栈,分配空间,定义队列为空栈:Q.front=Q.rear=0;

我们可以把 Q.front==Q.rear 最为队列为空的标志

Status InitQueue(SqQueue &Q)
{
    Q.base=(ElemType*)(MaxQSize*sizeof(ElemType);
    if(!Q.base)exit(OVERFLOW);
    Q.front=Q.real=0;
    return OK;
}

入队 EnQueue

插入数据, 其实和栈填入数据一样,e填入到 Q.rear表尾中,然后后移动一位,始终让Q.rear 指向没有使用过的内存空间。

Q.data[Q.rear]=e;
Q.rear++;

但是本问题还没有结束!

由于是静态顺序表的原因,容量有限,我们需要判断 队列是否满,如果满了就return ERROR; 如果没有满,才可以插入。

如何判断队列是否满?

如下图:

image-20210323192617618

本图是,MaxQsize为10的情况,此时队列已经满了,Q.rear=10, Q.rear理应最大为9,此时已经越界。那么是否可以把 Q.rear==MaXQSize当作队列满判断条件呢?看下图:

image-20210323193118396

如果此时出队3个元素,也就是 front++; 那么 data[0--2]的空间是没有使用的,所以Q.rear==MaXQSize,是不够完善的。

那如何将rear指针重新指向0这个位置呢?

image-20210323193808336

取模操作就可以完美解决这个问题!

Q.rear++ 换成 Q.rear=(Q.rear+1)%MaxQSize; (加1的原因非常简单,就是为了移动到下一个位置)

现在 Q.rear=9 ,如果在存储一个数据之后,Q.rear++,就要越界了 Q.rear=(9+1)%10=0 , Q.rear又指向回 data[0] ;

取模运算就是将无限的整数域映射到有限的整数域上 ,这样 Q.rear就锁死在0--9之中了,不会出现越界问题,反而形成了一个循环!所以静态顺序表实现的队列叫循环队列

那么又该如何判断队列是否满了呢

if( (Q.rear+1)%MaxQSize==Q.front) //队列满

其实我们使用本方法牺牲了一个存储空间,还是前面的前提条件,当rear=9的时候 ,如果继续存储, rear会重新和Q.front相等

但是 Q.rear==Q.front又是 队列为空的判断条件,有了矛盾,所以我们就牺牲了最后一个存储空间。

Status EnQueue(SqQueue &Q,ElemType e)
{
   if( (Q.rear+1)%MaxQSize==Q.front) //队列满
       return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxQSize;
    return OK;
}

出队DeQueue

出队,先判断队列是否为空,为空返回错误;不为空再让Q.front向后移动一位,当然我们也需要给ta取模,让他也转着圈圈。

Status DeQueue(SqQueue &Q,ElemType &e)
{
    if(Q.rear==Q.front)
        return Error;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MaxQSize;
    return ok;
}

如果非要不牺牲那一个空间

如果就需要重新设计判断队列是否为满的情况。

  • 方案一:

    添加一个变量length存储当前队列的长度,入队那么就length++,出队就length--,那么 可以将 length==Maxsize 为队满判断条件,length==

    0为空的判断条件

  • 方案二:

    队列满的时候一定入队造成的,队列为空一定是出队造成的。

    那么设计一个flag保存上一次是出队还是入队,出队 flag=0,入队flag为1;那么``flag==1&& Q.rear==Q.front作为队满的判断条件,flag==0&& Q.rear==Q.front` 作为队空的判断条件

总结

循环队列的实现,基本难点就再这里了,其他的操作非常简单,不在论述了。
如果要求当前队列的长度,其实也不难 (Q.rear-Q.front+MaxQSize)%MaxQSize 即可

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://yingwiki.top/2021/03/23/queue
最后更新于:  10  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟