队列

t1k

2021-04-03

数据结构 › C

C, 数据结构

·本篇:1.5k字大约需要: 6分钟

前言

队列的实现及相关操作

编程语言: C

顺序存储结构

队列

队列的抽象数据类型

队列的定义

队列是一种先进先出(First In First Out)的线性表，简称FIFO。

允许插入的一端称为队尾，允许删除的一端称为队头

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

循环队列

队列顺序存储的不足

假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，数组下标为0的一端即是对头

那么入队列操作其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度是O(1)

但是队列元素的出列是在队头，即下标为0的位置，所以当一个元素出列时，队列中的所有元素都得向前移动，以保证队头的位置不为空，此时时间复杂度为O(n)

当然，队头不需要一定在下标为0的位置，可以引入两个指针，front指针指向头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列为空

但是这样就会产生“假溢出”的问题

为了解决这些问题，所以有了循环队列

循环队列的定义

把队列的头尾相接的顺序存储结构称为循环队列

新的问题

刚才front等于rear时队列为空，但循环队列满时也是front等于rear，那么应该如何判断此时的队列究竟是空还是满呢?

方法一是设置一个标志变量flag，当front == rear，且flag == 0时为队列空，当front == rear，且flag == 1时为队列满

方法二是当队列空时，条件就是front == rear，当队列满时，修改其条件，保留一个元素空间，也就是说，队列满时，数组中还有一个空闲单元。

由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能相差整整一圈，所以若队列的最大长度是QueueSize，那么队列满的条件就是(rear + 1) % QueueSize == front

通用的计算队列长度公式为：(rear - front + QueueSize) % QueueSize

代码实现

结构代码

#include<stdio.h>
#include<stdlib.h>
#define sf scanf
#define pf printf
#define MAXSIZE 100

typedef struct
{
    int data[MAXSIZE];
    int front;
    int rear;
} SqQueue;

初始化一个空队列

void InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
}

入队

void EnQueue(SqQueue *Q, int target)
{
    if((Q->rear + 1) % MAXSIZE == Q->front)
        pf("队列已满\n");
    else
    {
        Q->data[Q->rear] = target;
        Q->rear = (Q->rear + 1) % MAXSIZE;
    }
}

队头元素出队

void DeQueue(SqQueue *Q, int *target)
{
    if(Q->front == Q->rear)
        pf("队列为空\n");
    else
    {
        *target = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAXSIZE;
    }
}

返回队列元素个数

int QueueLength(SqQueue *Q)
{
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

判断队列是否为空

bool Empty(SqQueue *Q)
{
    return Q->rear == Q->front;
}

返回队头元素

int GetHead(SqQueue *Q)
{
    int target = -1;
    if(EmPty(Q))
        pf("队列为空\n");
    else
        target = Q->data[Q->front];
    return target;
}

遍历队列

void Display(SqQueue *Q)
{
    if(Empty(Q))
        pf("队列为空\n");
    else
    {
        for(int i = Q->front; i != Q->rear; i = (i + 1) % MAXSIZE)
            pf("%d ", Q->data[i]);
        pf("\n");
    }
}

队列的链式存储结构

代码实现

结构代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define sf scanf
#define pf printf

typedef struct QNode
{
    int data;
    struct QNode *next;
} QNode;

typedef struct
{
    QNode *front, *rear;
} LinkQueue;

初始化一个空队列

void InitLinkQueue(LinkQueue *L)
{
    L->front = (QNode *) malloc(sizeof(QNode));
    L->front->next = NULL;
    L->rear = L->front;
}

向队列中添加一个元素

void EnQueue(LinkQueue *L, int target)
{
    QNode *p = (QNode *) malloc(sizeof(QNode));
    if(!p)
        exit(0);
    p->data = target;
    p->next = NULL;
    L->rear->next = p;
    L->rear = p;
}

队头元素出列

void DeQueue(LinkQueue *L, int *target)
{
    QNode *p;
    if(LinkQueueEmpty(L))
        pf("队列为空\n");
    else
    {
//        p = L->front->next;
//        *target = p->data;
//        L->front->next = p->next;
//        if(p == L->rear)
//            L->rear = L->front;
        p = L->front;
        *target = p->next->data;
        L->front = p->next;
        L->front->data = 0;
        free(p);
        p = NULL;
    }
}

采用移动头结点的方式，即将要出列的那个元素结点设置为新的头结点，这样可以避免判断出列的元素是否是最后一个元素，不必再移动尾指针

遍历

void Display(LinkQueue *L)
{
    QNode *p = L->front->next;
    if(L->front == L->rear)
        pf("队列为空\n");
    else
    {
        while(p)
        {
            pf("%d ", p->data);
            p = p->next;
        }
        pf("\n");
    }
}

循环队列和链队列的比较

时间上

它们的基本操作都是常数时间，即都为O(1)

不过循环队列是事先申请好空间，使用期间不释放

而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差别

空间上

循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题

而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受

所以在空间上，链队列更加灵活

总结

在可以确定队列长度最大值时，建议用循环队列，无法预估队列长度时，则用链队列