跳至正文
View Categories

1 min read

主要内容 #

  1. 链式队列的基本实现
  2. 入队和出队
  3. 参考代码

1. 链式队列的基本实现 #

链式队列，简称”链队列”，即使用链表实现的队列存储结构。
链式队列的实现思想同顺序队列类似，创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如下图所示：

上图所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。
由此，我们可以编写出创建链式队列的 C 语言实现代码为：

//链表中的节点结构
typedef struct qnode{
    int data;
    struct qnode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}

2. 入队和出队 #

链式队列数据入队
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

  1. 将该数据元素用节点包裹，例如新节点名称为 elem；
  2. 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
  3. 最后移动 rear 指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。
例如，在上图的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如下图所示：

我们将链表的头部作为队列的队头，将链表的尾部作为队列的队尾。当然，也可以反过来，将链表的头部（尾部）作为队列的队尾（队头），两种存储方式都可以。
数据元素入链式队列的 C 语言实现代码为：

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

链式队列数据出队
当链式队列中有元素需要出队时，按照 “先进先出” 的原则，需要先将在它之前入队的元素依次出队，然后该目标元素才能出队。
我们知道，队列中的元素只能从队头出队。在图 2 中，队列的队头位于链表的头部。因此队列中元素出队的过程，其实是链表中摘除首元结点的过程，需要做以下 3 步操作：

  1. 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
  2. 将 top 所指结点的 next 指针，指向 p 结点的直接后继结点；
  3. 释放节点 p 占用的内存空间；

例如，在图b)的基础上，我们将元素 1 和 2 出队，则操作过程下图所示：

链式队列中队头元素出队的 C 语言实现代码为：

QNode* DeQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}

将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。此外，程序中要判断被摘除的目标结点是否是 rear 队头队尾，如果是的话，要及时更新 rear 指针的指向。

3. 参考代码 #

这里给出链式队列入队和出队的完整 C 语言代码为：

#include<stdio.h>
#include<stdlib.h>
//链表中的节点结构
typedef struct qnode {
    int data;
    struct qnode* next;
}QNode;
//创建链式队列的函数
QNode* initQueue() {
    //创建一个头节点
    QNode* queue = (QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next = NULL;
    return queue;
}

QNode* enQueue(QNode* rear, int data) {
    //1、用节点包裹入队元素
    QNode* enElem = (QNode*)malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next = enElem;
    //3、rear指向新节点
    rear = enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

QNode* deQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}

int main() {
    QNode* queue = NULL, * top = NULL, * rear = NULL;
    queue = top = rear = initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear = enQueue(rear, 1);
    rear = enQueue(rear, 2);
    rear = enQueue(rear, 3);
    rear = enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    return 0;
}
What are your Feelings