【数据结构】线性表（十一）队列：双端队列及其基本操作（初始化、判空、判满、头部入队、尾部入队、头部出队、尾部出队、存取队首队尾元素）

文章目录

  • 一、队列
    • 1. 定义
    • 2. 基本操作
  • 二、顺序队列
  • 三、链式队列
  • 双端队列
    • 0. 头文件
    • 1. 队列结构体
    • 2. 初始化
    • 3. 判断队列是否为空
    • 4. 判断队列是否已满
    • 5. 头部入队
    • 6. 尾部入队
    • 7. 头部出队
    • 8. 尾部出队
    • 9. 存取队列头部的元素
    • 10. 存取队列尾部的元素
    • 11. 释放队列内存
    • 12. 主函数
    • 13. 代码整合

一、队列

1. 定义

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

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

2. 基本操作

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

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

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

二、顺序队列

  参考前文：【数据结构】线性表（八）队列：顺序队列及其基本操作（初始化、判空、判满、入队、出队、存取队首元素）

三、链式队列

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

双端队列

  双端队列（Double-ended Queue，简称Deque）可以在队列的头部和尾部进行元素的插入和删除操作，因此可以看作是一种特殊的队列和栈的结合。

双端队列的操作包括：

  • 在队列头部插入元素（头部入队）；
  • 在队列尾部插入元素（尾部入队）；
  • 在队列头部删除元素（头部出队），并返回该元素；
  • 在队列尾部删除元素（尾部出队），并返回该元素；
  • 获取队列头部的元素，但不删除它；
  • 获取队列尾部的元素，但不删除它；
  • 判断队列是否为空。

  双端队列可以用于解决一些特定的问题，例如实现滑动窗口最大值、字符串处理等。它的灵活性使得在某些场景下比普通队列更加方便和高效。
图片来源于网络，侵删

0. 头文件

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

1. 队列结构体

typedef struct {
    int* elements;  // 存储队列元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int size;       // 队列的最大容量
} Deque;

2. 初始化

void initDeque(Deque* deque, int capacity) {
    deque->elements = (int*)malloc(capacity * sizeof(int));
    deque->front = -1;
    deque->rear = -1;
    deque->size = capacity;
}
  • 使用动态内存分配函数 malloc 分配了一个大小为 capacity * sizeof(int) 的整型数组，并将其地址赋值给 deque->elements。
  • 将 deque->front 和 deque->rear 初始化为 -1，表示队列为空。
  • 将 deque->size 设置为传入的容量值。

3. 判断队列是否为空

int isEmpty(Deque* deque) {
    return deque->front == -1;
}

  通过检查队列的头部索引是否为-1来判断队列是否为空。

4. 判断队列是否已满

int isFull(Deque* deque) {
    return deque->rear == deque->size - 1;
}

  通过检查队列的尾部索引是否等于队列的最大容量减1来判断队列是否已满。

5. 头部入队

void insertFront(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->front == 0) {
        deque->front = deque->size - 1;
    } else {
        deque->front--;
    }
    deque->elements[deque->front] = element;
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则将队列头部和尾部索引都设置为 0。
  • 否则，如果队列头部索引为 0，则将其设置为队列的最大容量减 1，否则将其递减 1。
  • 将元素 element 存储到队列头部索引对应的位置。

6. 尾部入队

void insertRear(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->rear == deque->size - 1) {
        deque->rear = 0;
    } else {
        deque->rear++;
    }
    deque->elements[deque->rear] = element;
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则将队列头部和尾部索引都设置为 0。
  • 否则，如果队列尾部索引等于队列的最大容量减 1，则将其设置为 0，否则将其递增 1。
  • 将元素 element 存储到队列尾部索引对应的位置。

7. 头部出队

void deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->front == deque->size - 1) {
        deque->front = 0;
    } else {
        deque->front++;
    }
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则直接返回，不进行任何操作。
  • 否则，如果队列头部索引等于队列尾部索引，表示队列中只有一个元素，将队列头部和尾部索引都设置为 -1。
  • 否则，如果队列头部索引等于队列的最大容量减 1，则将其设置为 0，否则将其递增 1。

8. 尾部出队

void deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->rear == 0) {
        deque->rear = deque->size - 1;
    } else {
        deque->rear--;
    }
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则直接返回，不进行任何操作。
  • 否则，如果队列尾部索引等于队列头部索引，表示队列中只有一个元素，将队列头部和尾部索引都设置为 -1。
  • 否则，如果队列尾部索引等于 0，则将其设置为队列的最大容量减 1，否则将其递减 1。

9. 存取队列头部的元素

int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->front];
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则返回一个特定的值（这里是 -1），表示队列为空。
  • 否则，返回队列头部索引对应的元素。

10. 存取队列尾部的元素

int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->rear];
}
  • 如果队列为空（即 isEmpty(deque) 返回真），则返回一个特定的值（这里是 -1），表示队列为空。
  • 否则，返回队列尾部索引对应的元素。

11. 释放队列内存

void freeDeque(Deque* deque) {
    free(deque->elements);
}

  使用 free 函数释放 deque->elements 指向的动态内存。

12. 主函数

int main() {
    Deque deque;
    int capacity = 5;  // 设置队列的容量

    // 初始化双端队列
    initDeque(&deque, capacity);

    // 在队列头部插入元素
    insertFront(&deque, 1);
    insertFront(&deque, 2);

    // 在队列尾部插入元素
    insertRear(&deque, 3);
    insertRear(&deque, 4);

    // 获取队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 在队列头部删除元素
    deleteFront(&deque);

    // 在队列尾部删除元素
    deleteRear(&deque);

    // 获取更新后的队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 释放队列内存
    freeDeque(&deque);

    return 0;
}

在这里插入图片描述

13. 代码整合

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

typedef struct {
    int* elements;  // 存储队列元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int size;       // 队列的最大容量
} Deque;

void initDeque(Deque* deque, int capacity) {
    deque->elements = (int*)malloc(capacity * sizeof(int));
    deque->front = -1;
    deque->rear = -1;
    deque->size = capacity;
}

int isEmpty(Deque* deque) {
    return deque->front == -1;
}

int isFull(Deque* deque) {
    return deque->rear == deque->size - 1;
}

void insertFront(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->front == 0) {
        deque->front = deque->size - 1;
    } else {
        deque->front--;
    }
    deque->elements[deque->front] = element;
}

void insertRear(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->rear == deque->size - 1) {
        deque->rear = 0;
    } else {
        deque->rear++;
    }
    deque->elements[deque->rear] = element;
}

void deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->front == deque->size - 1) {
        deque->front = 0;
    } else {
        deque->front++;
    }
}

void deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->rear == 0) {
        deque->rear = deque->size - 1;
    } else {
        deque->rear--;
    }
}

int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->front];
}

int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->rear];
}

void freeDeque(Deque* deque) {
    free(deque->elements);
}

int main() {
    Deque deque;
    int capacity = 5;  // 设置队列的容量

    // 初始化双端队列
    initDeque(&deque, capacity);

    // 在队列头部插入元素
    insertFront(&deque, 1);
    insertFront(&deque, 2);

    // 在队列尾部插入元素
    insertRear(&deque, 3);
    insertRear(&deque, 4);

    // 获取队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 在队列头部删除元素
    deleteFront(&deque);

    // 在队列尾部删除元素
    deleteRear(&deque);

    // 获取更新后的队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 释放队列内存
    freeDeque(&deque);

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/103836.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

已更新!宝藏教程！MYSQL-第六章节多表查询(一对一，多对多，一对多)，连接查询（内，外连接），联合查询，子查询 代码例题详解这一篇就够了（附数据准备代码）

已更新!宝藏教程！MYSQL-第六章节多表查询(一对一，多对多，一对多)，连接查询（内，外连接），联合查询，子查询 代码例题详解这一篇就够了（附数据准备代码）

c知识点合集已经完成欢迎前往主页查看&#xff0c;点点赞点点关注不迷路哦 点我进入c第一章知识点合集 MYSQL第一章节DDL数据定义语言的操作----点我进入 MYSQL第二章节DDL-数据库操作语言 DQL-数据查询语言----点我进入 MYSQL第三章节DCL-管理用户&#xff0c;控制权限----点我…
阅读更多...
28、Flink 的SQL之DROP 、ALTER 、INSERT 、ANALYZE 语句

28、Flink 的SQL之DROP 、ALTER 、INSERT 、ANALYZE 语句

Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…
阅读更多...
笔记/日记应用 memos

笔记/日记应用 memos

memos &#xff0c;一款很惊艳的笔记应用&#xff0c;UI很漂亮&#xff0c;交互体验也很好&#xff0c;还有其他的小伙伴基于memos开发了不同平台的客户端。 图源-Gihub页 可以说这个是私人笔记系统的天花板&#xff0c;推荐给大家。
阅读更多...
vue重修之Vuex【上部】

vue重修之Vuex【上部】

文章目录 版权声明Vuex 概述Vuex 的主要概念和组件 vuex的使用状态 &#xff08;state&#xff09;Vuex特点 访问vuex中数据$store访问mapState辅助函数访问 开启严格模式及Vuex的单项数据流突变&#xff08;mutations&#xff09;mutations初识带参 mutations辅助函数 mapMuta…
阅读更多...
N——＞BatchSize 数据维度理解和处理(chun, cat, squeeze, unsqueeze)

N——＞BatchSize 数据维度理解和处理(chun, cat, squeeze, unsqueeze)

数据处理之N——>BatchSize N——>batch_size train_data TensorDataset(torch.Tensor(x_train).double(), torch.Tensor(y_train).double()) train_loader DataLoader(train_data, batch_sizeargs.bs, shuffleTrue, drop_lastTrue) for batch_idx, (inputs, results…
阅读更多...
自动化测试07Selenium01

自动化测试07Selenium01

目录 什么是自动化测试 Selenium介绍 Selenium是什么 Selenium特点 工作原理 SeleniumJava环境搭建 Selenium常用的API使用 定位元素findElement CSS选择语法 id选择器&#xff1a;#id 类选择 .class 标签选择器 标签名 后代选择器 父级选择器 自己选择器 xpath …
阅读更多...
Django实现音乐网站 (22)

Django实现音乐网站 (22)

使用Python Django框架做一个音乐网站&#xff0c; 本篇音乐播放器功能完善&#xff1a;顺序播放、设置播放数、歌词滚动等功能。 目录 顺序播放 设置顺序播放 单曲播放数 添加路由 视图处理 模板处理 歌词滚动 视图内容返回修改 样式设置 模板内容 歌词滚动脚本 歌…
阅读更多...
【C++代码】安排行程，N皇后，解数独--代码随想录

【C++代码】安排行程，N皇后，解数独--代码随想录

题目&#xff1a;重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必…
阅读更多...
[Docker]二.Docker 镜像,仓库,容器介绍以及详解

[Docker]二.Docker 镜像,仓库,容器介绍以及详解

一.Docker 镜像,容器,仓库的简单介绍 通俗来讲:镜像相当于VM虚拟机中的ios文件,容器相当于虚拟机系统,仓库相当于系统中的进程或者执行文件,容器是通过镜像创建的 1.镜像 Docker 镜像就是一个 Linux 的文件系统&#xff08; Root FileSystem &#xff09;&#xff0c;这个文…
阅读更多...
一百九十五、MySQL——MySQL数据库创建只读权限的账号（附流程截图）

一百九十五、MySQL——MySQL数据库创建只读权限的账号（附流程截图）

一、目的 在团队开发过程中&#xff0c;为了实现数据共享以及避免其他团队修改库表数据&#xff0c;需要提供数据库只读权限的账号&#xff0c;因此以MySQL数据库为例&#xff0c;创建MySQL数据库只读权限的账号 二、实施步骤 &#xff08;一&#xff09;第一步&#xff0c;…
阅读更多...
栈（Stack）的概念+MyStack的实现+栈的应用

栈（Stack）的概念+MyStack的实现+栈的应用

文章目录 栈&#xff08;Stack&#xff09;一、 栈的概念1.栈的方法2.源码分析 二、MyStack的实现1.MyStack的成员变量2.push方法3.isEmpty方法和pop方法4.peek方法 三、栈的应用1.将递归转化为循环1.调用递归打印2.通过栈逆序打印链表 栈&#xff08;Stack&#xff09; 一、 栈…
阅读更多...
Nginx动静分离

Nginx动静分离

为了加快网站的解析速度&#xff0c;可以把动态页面和静态页面由不同的服务器来解析&#xff0c;加快解析速度。降低原来单个服务器的压力。 在动静分离的tomcat的时候比较明显&#xff0c;因为tomcat解析静态很慢&#xff0c;其实这些原理的话都很好理解&#xff0c;简单来说&…
阅读更多...
T113-S3-buildroot文件系统tar解压缩gz文件

T113-S3-buildroot文件系统tar解压缩gz文件

目录 前言 一、现象描述 二、解决方案 三、tar解压缩.gz文件 总结 前言 本文主要介绍全志T113-S3平台官方SDK&#xff0c;buildroot文件系统tar不支持.gz文件解压缩的问题以及如何配置buildroot文件系统解决该问题的方法介绍。 一、现象描述 在buildroot文件系统中&#xff…
阅读更多...
Doceker-compose——容器群集编排管理工具

Doceker-compose——容器群集编排管理工具

目录 Docker-compose 1、Docker-compose 的三大概念 2、YAML文件格式及编写注意事项 1&#xff09;使用 YAML 时需要注意下面事项 2&#xff09;ymal文件格式 3&#xff09;json格式 3、Docker Compose配置常用字段 4、Docker-compose的四种重启策略 5、Docker Compos…
阅读更多...
强劲升级，太极2.x你值得拥有！

强劲升级，太极2.x你值得拥有！

嗨&#xff0c;大家好&#xff0c;最近桃桃没顾得上给大家分享好用好玩的软件。 还记得前段时间给大家分享的太极1.0软件&#xff1f; 最近大佬对软件进行了全新升级&#xff0c;升级后的功能更强更稳定&#xff0c;轻度用户使用基本功能就已经足够了&#xff0c;壕无人性的同学…
阅读更多...
Openssl数据安全传输平台004：Socket C-API封装为C++类 / 服务端及客户端代码框架和实现

Openssl数据安全传输平台004：Socket C-API封装为C++类 / 服务端及客户端代码框架和实现

文章目录 0. 代码仓库1. 客户端C API2. 客户端C API的封装分析2.1 sckClient_init()和sckClient_destroy()2.2 sckClient_connect2.3 sckClient_closeconn()2.4 sckClient_send()2.5 sckClient_rev()2.6 sck_FreeMem 3. 客户端C API4. 服务端C API5. 服务端C6. 客户端和服务端代…
阅读更多...
Ubuntu 安装 npm 和 node

Ubuntu 安装 npm 和 node

前言 最近学习VUE&#xff0c;在ubuntu 2204 上配置开发环境&#xff0c;涉及到npm node nodejs vue-Cli脚手架等内容&#xff0c;做以记录。 一、node nodejs npm nvm 区别 &#xff1f; node 是框架&#xff0c;类似python的解释器。nodejs 是编程语言&#xff0c;是js语言的…
阅读更多...
题目 1053: 二级C语言-平均值计算（python详解）——练气三层初期

题目 1053: 二级C语言-平均值计算（python详解）——练气三层初期

✨博主&#xff1a;命运之光 &#x1f984;专栏&#xff1a;算法修炼之练气篇&#xff08;C\C版&#xff09; &#x1f353;专栏&#xff1a;算法修炼之筑基篇&#xff08;C\C版&#xff09; &#x1f352;专栏&#xff1a;算法修炼之练气篇&#xff08;Python版&#xff09; ✨…
阅读更多...
外网nat+nat server，内网做路由过滤，以及ppp CHAR认证 企业网搭建

外网nat+nat server，内网做路由过滤，以及ppp CHAR认证 企业网搭建

作业 网络拓扑图如下所示&#xff1a; 要求&#xff1a;做适当的截图&#xff0c;表示完成相应的操作。 按照网络拓扑要求搭建网络结构&#xff0c;按照个人学号配置每个节点的IP地址&#xff0c;其中X为班级号&#xff0c;Y为学号末尾2位&#xff1b;Y1为学号末尾2位1&#…
阅读更多...
uniapp接入萤石微信小程序插件

uniapp接入萤石微信小程序插件

萤石官方提供了一些适用于uniapp / 小程序的方案 如 小程序半屏 hls rtmp 等 都TM有坑 文档写的依托答辩 本文参考了uniapp小程序插件 以及 萤石微信小程序插件接入文档 效果如下 1. 插件申请 登录您的小程序微信公众平台&#xff0c;点击左侧菜单栏&#xff0c;进入设置页…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站