【数据结构】线性表（九）队列：链式队列及其基本操作（初始化、判空、入队、出队、存取队首元素）-CSDN博客

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

  堆栈Stack 和 队列Queue是两种非常重要的数据结构两者都是特殊的线性表

  • 对于堆栈所有的插入和删除以至几乎所有的存取都是在表的同一端进行
  • 对于队列所有的插入都是在表的一端进行所有的删除以至几乎所有的存取都是在表的另一端进行。

一、队列

1. 定义

  队列是一种操作受限的线性表对于它的所有插入都在表的一端进行所有的删除以至几乎所有的存取都在表的另一端进行且这些操作又都是按照先进先出FIFO的原则进行的。进行删除的一端称为队头front进行插入的一端称为队尾rear。没有元素的队列称为空队列简称空队。

在这里插入图片描述
  队列就像生活中排队购物新来的人只能加入队尾假设不允许插队购物结束后先离开的总是队头假设无人中途离队。也就是说先加入队列的成员总是先离开队列因此队列被称为先进先出First In First Out的线性表简称为FIFO表。如图在空队列中依次加入元素a1a2a3a4a5出队次序仍然是a1a2a3a4a5 .

2. 基本操作

  • 队列是受限的线性表其基本操作包括

    • IsEmpty() : 判断队列是否为空
    • isFull()判断队列是否为满
    • enqueue() 向队尾添加元素入队
    • dequeue() 删除队首元素出队
    • peek()获取队首的元素值存取

  • 同普通线性表一样队列也可以用顺序存储和链接存储两种方式来实现

二、顺序队列

  参考前文线性表八队列顺序队列及其基本操作初始化、判空、判满、入队、出队、存取队首元素

三、链式队列

  用链接存储方式实现的队列称为链式队列。队列的主要操作都在队首和队尾进行所以链式队列应包含两个指针队首指针front和队尾指针rear分别存放队首和队尾结点的地址信息。链式队列中没有哨位结点。 分析链式队列的结构不难看出当创建一个链式队列时队列的首尾指针均为NULL。

0. 链表

  参考前文线性表二单链表及其基本操作创建、插入、删除、修改、遍历打印

1. 头文件

#include <stdio.h>
#include <stdlib.h>
  • 两个头文件
    • stdio.h用于输入输出操作
    • stdlib.h用于内存分配和释放

2. 队列结构体

// 定义队列节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式队列
typedef struct Queue {
    Node* front; // 队头指针
    Node* rear;  // 队尾指针
} Queue;
  • Node 结构体表示队列的节点
    • 包含一个整数类型的数据成员 data以及一个指向下一个节点的指针 next。
  • Queue 结构体表示链式队列
    • 包含两个指针成员 front 和 rear分别指向队头和队尾节点。

3. 队列的初始化

void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

   将队头和队尾指针都设置为 NULL表示队列为空。

4. 判断队列是否为空

int isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

  如果队头指针为空即 front 为 NULL则队列为空返回值为 1否则返回值为 0。

5. 入队

void enqueue(Queue* queue, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (isQueueEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}
  • 创建一个新的节点并将数据存储在新节点的 data 成员中将新节点的 next 指针设置为 NULL。
  • 根据队列是否为空将新节点插入队列的末尾。
    • 如果队列为空即队头指针和队尾指针都为空那么将队头和队尾指针都指向新节点。
    • 如果队列不为空即队尾指针不为空则将队尾节点的 next 指针指向新节点并更新队尾指针为新节点。

6. 出队

int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }

    Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    free(temp);

    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    return data;
}

dequeue 函数用于将元素出队并返回出队的元素值。

  • 判断队列是否为空
    • 如果为空则打印错误信息并返回 -1。
    • 如果队列不为空则获取队头节点的数据值然后更新队头指针为下一个节点并释放原来的队头节点的内存空间。
  • 如果队头指针更新后为空则表示队列已经为空将队尾指针也设置为空。
  • 最后返回出队的数据值。

7. 存取队首元素

int peek(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }

    return queue->front->data;
}

   peek 函数用于获取队列的队首元素值但不进行出队操作。

  • 判断队列是否为空
    • 如果为空则打印错误信息并返回 -1。
    • 如果队列不为空则直接返回队头节点的数据值。

8. 主函数

int main() {
    Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Peek: %d\n", peek(&queue));

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));

    printf("Peek: %d\n", peek(&queue));

    enqueue(&queue, 40);
    printf("Peek: %d\n", peek(&queue));

    return 0;
}
  • 声明 Queue 类型的变量 queue并调用 initQueue 函数对其进行初始化
  • 使用 enqueue 函数将三个元素10、20、30依次入队
  • 使用 peek 函数获取队首元素并打印
  • 使用 dequeue 函数进行两次出队操作并使打印出队的元素值
  • 使用 peek 函数获取队首元素并打印
  • 使用 enqueue 函数将元素 40 入队
  • 使用 peek 函数获取队首元素并打印。

在这里插入图片描述

9. 代码整合

#include <stdio.h>
#include <stdlib.h>

// 定义队列节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式队列
typedef struct Queue {
    Node* front; // 队头指针
    Node* rear;  // 队尾指针
} Queue;

// 初始化链式队列
void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断链式队列是否为空
int isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 入队
void enqueue(Queue* queue, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (isQueueEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队
int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }

    Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    free(temp);

    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    return data;
}

// 获取队首元素
int peek(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }

    return queue->front->data;
}
int main() {
    Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Peek: %d\n", peek(&queue));

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));

    printf("Peek: %d\n", peek(&queue));

    enqueue(&queue, 40);
    printf("Peek: %d\n", peek(&queue));

    return 0;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：Java EE-使用Servlet搭建一个简单的前后端交互程序-CSDN博客

下一篇：【苍穹外卖 | 项目日记】第八天-CSDN博客

“【数据结构】线性表（九）队列：链式队列及其基本操作（初始化、判空、入队、出队、存取队首元素）-CSDN博客” 的相关文章

通信原理笔记—基带信号的功率谱1年前 (2023-02-02)
51单片机最强模块化封装(2)1年前 (2023-02-02)
面试之 Python 基础1年前 (2023-02-02)
【面向对象】构造函数与析构函数详解1年前 (2023-02-02)
在线客服系统源码编译Golang语言下go build命令构建二进制程序1年前 (2023-02-02)
[Android开发学iOS系列] ViewController1年前 (2023-02-02)
COM 进程注入技术1年前 (2023-02-02)
【Spring AOP】@Aspect结合案例详解（一）: @Pointcut使用@annotation + 五种通知Advice注解（已附源码）1年前 (2023-02-02)
缺陷修改实践——replace函数的运用|思考？1年前 (2023-02-02)
PowerShell 美化（oh-my-posh）1年前 (2023-02-02)

阿里云国际版