越行勤‘s Blog

数据结构 队列基本概念和实现

队列

认识队列

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

规定： 允许插入的一端，叫做队尾；允许删除的一端叫做队头。

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

队列的基本操作

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

  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 即可

努力成长的程序员

Code happily

© 2024 越行勤‘s Blog