队列的操作和使用详解

队列的操作和使用详解

引用

CSDN

1.

https://m.blog.csdn.net/ffncl/article/details/142703937

队列和栈一样，是线性表的一个特例。队列限定在一端进行插入操作，在另一端进行删除操作，插入端称为队尾，删除端称为队头，队列有先进先出的特点，而栈有后进先出的特点。

与栈类似，队列的常见操作有：创建空队列、判空、入队、出队、取队头元素等等。队列分为链队列和循环队列两类，下面分别介绍。

链队列

链队列即为采用链式存储的队列，队头指针指向链队列的第一个结点，队尾指针指向最后一个结点。

链队列类型定义

链队列首先需要定义链式存储的结点结构，包括数据域和指针域，以及队列的结构，即队头类型和队尾类型。

typedef int DataType;
struct Node {
    DataType data;
    struct Node *link;
};
typedef struct Node* PNode; // 链式结点类型

struct Queue {
    PNode f; // 队头
    PNode r; // 队尾
};
typedef struct Queue * LinkQueue; // 链队列类型

创建链式空队列

创建空队列需要申请Queue结构体空间，初始化队头和队尾指针为空。

LinkQueue SetNullQueue_Link() {
    LinkQueue lqueue = (LinkQueue)malloc(sizeof(struct Queue));
    if (lqueue == NULL)
        printf("FF Alloc failure!");
    else {
        lqueue->f = NULL;
        lqueue->r = NULL;
    }
    return lqueue;
}

链队列判空

检查队头指针是否为空即可，空返回1，否则返回0。

int IsNullQueue_Link(LinkQueue lqueue) {
    return (lqueue->f == NULL);
}

链队列入队

入队时需要申请结点空间，若申请成功，则为结点的数据域和指针域赋值。若队列为空，队头和队尾都指向入队的第一个结点，否则在队尾插入即可。

void EnQueue_Link(LinkQueue lqueue, DataType x) {
    PNode p = (PNode)malloc(sizeof(struct Node));
    if (p == NULL)
        printf("FF Alloc failure!");
    else {
        p->data = x;
        p->link = NULL;
        if (lqueue->f == NULL) {
            lqueue->f = p;
            lqueue->r = p;
        } else {
            lqueue->r->link = p; // 结点插入队尾，即改变最后一个结点的指针域
            lqueue->r = p; // 修改队列尾指针，即改变队列的尾结点
        }
    }
}

链队列出队

检查队列是否为空，若不为空，修改队头指针，释放队头结点。

void DeQueue_Link(LinkQueue lqueue) {
    PNode p;
    if (lqueue->f == NULL) {
        printf("It is empty queue!");
    } else {
        p = lqueue->f; // p指向队头结点，方便释放
        lqueue->f = lqueue->f->link; // 修改队头指针
        free(p); // 释放结点空间
    }
}

取链队列队头元素

首先判断队列是否为空，不为空返回队头。

DataType FrontQueue_Link(LinkQueue lqueue) {
    if (lqueue->f == NULL) {
        printf("It is empty queue!");
        return 0;
    } else {
        return (lqueue->f->data); // 返回队头结点数据域
    }
}

循环队列

循环队列采用顺序存储方式，能有效解决假溢出的问题。假设队头指针 f 和队尾指针 r 重合，形成闭环的循环队列。

循环队列类型定义

循环队列基于顺序存储方式实现，需要明确队列的空间最大值、队头、队尾指针以及队列的元素空间。

typedef int DataType;
struct Queue {
    int Max; // 队列空间最大值
    int f; // 队头指针
    int r; // 队尾指针
    DataType *elem;
};
typedef struct Queue * SeqQueue;

创建循环空队列

创建队列需要申请结构体空间，然后再申请一个数组空间，将队头和队尾设置为零。

SeqQueue SetNullQueue_Seq(int m) {
    SeqQueue squeue = (SeqQueue)malloc(sizeof(struct Queue));
    if (squeue == NULL) {
        printf("FF Alloc failure!");
        return 0;
    } else {
        squeue->elem = (int *)malloc(sizeof(DataType) * m);
        if (squeue->elem != NULL) {
            squeue->Max = m; // 设置循环队列最大值空间
            squeue->f = 0; // 队头初值
            squeue->r = 0; // 队尾初值
            return squeue;
        }
    }
}

循环队列判空

检查队头指针和队尾指针是否相等，相等则队列为空，返回1，否则返回0。

int IsNullQueue_seq(SeqQueue squeue) {
    return (squeue->f == squeue->r);
}

循环队列入队

先检查队列是否已经满了，若不满，则将元素插入队尾，再修改尾指针。

void EnQueue_Seq(SeqQueue squeue, DataType x) {
    if ((squeue->r + 1) % (squeue->Max) == squeue->f)
        printf("It is FULL Queue");
    else {
        squeue->elem[squeue->r] = x; // 元素插入队尾
        squeue->r = (squeue->r + 1) % (squeue->Max); // 尾指针+1
    }
}

循环队列出队

首先要判断队列是否为空，不为空则删除队头元素，修改队头指针。

void DeQueue_seq(SeqQueue squeue) {
    if (IsNullQueue_seq(squeue))
        printf("It is empty queue");
    else
        squeue->f = (squeue->f + 1) % (squeue->Max); // 队头指针+1
}

循环队列取队头元素

先检查队列是否为空，不为空返回队头元素。

DataType FrontQueue_Seq(SeqQueue squeue) {
    if (squeue->f == squeue->r)
        printf("It is empty queue!");
    else
        return (squeue->elem[squeue->f]);
}

总结

队列和栈一样，在解决数据结构的问题中常用到，例如迷宫问题的广度优先搜索、农夫过河问题、二叉树的遍历等。通过灵活运用队列，可以很好地解决问题。