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

2023-10-23 14:52
文章标签 元素 数据结构 基本操作 队列 初始化 线性表 十一 双端 判空 存取 头部 尾部 出队 判满 入队 首队

本文主要是介绍【数据结构】线性表（十一）队列：双端队列及其基本操作（初始化、判空、判满、头部入队、尾部入队、头部出队、尾部出队、存取队首队尾元素），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 一、队列
    • 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.chinasem.cn/article/268558。

相关文章

SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法

JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法

《JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法》：本文主要介绍JavaScript中比较两个数组是否有相同元素(交集)的三种常用方法,每种方法结合实例代码给大家介绍的非常... 目录引言：为什么"相等"判断如此重要？方法1：使用some()+includes()（适合小数组）方法2
阅读更多...
RabbitMQ 延时队列插件安装与使用示例详解(基于 Delayed Message Plugin)

RabbitMQ 延时队列插件安装与使用示例详解(基于 Delayed Message Plugin)

《RabbitMQ延时队列插件安装与使用示例详解(基于DelayedMessagePlugin)》本文详解RabbitMQ通过安装rabbitmq_delayed_message_exchan... 目录 一、什么是 RabbitMQ 延时队列？ 二、安装前准备✅ RabbitMQ 环境要求 三、安装延时队
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
MyBatis的xml中字符串类型判空与非字符串类型判空处理方式(最新整理)

MyBatis的xml中字符串类型判空与非字符串类型判空处理方式(最新整理)

《MyBatis的xml中字符串类型判空与非字符串类型判空处理方式(最新整理)》本文给大家介绍MyBatis的xml中字符串类型判空与非字符串类型判空处理方式,本文给大家介绍的非常详细,对大家的学习或... 目录完整 Hutool 写法版本对比优化为什么status变成Long？为什么 price 没事？怎
阅读更多...
把Python列表中的元素移动到开头的三种方法

把Python列表中的元素移动到开头的三种方法

《把Python列表中的元素移动到开头的三种方法》在Python编程中,我们经常需要对列表（list）进行操作,有时,我们希望将列表中的某个元素移动到最前面,使其成为第一项,本文给大家介绍了把Pyth... 目录一、查找删除插入法1. 找到元素的索引2. 移除元素3. 插入到列表开头二、使用列表切片（Lis
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
Spring Bean初始化及@PostConstruc执行顺序示例详解

Spring Bean初始化及@PostConstruc执行顺序示例详解

《SpringBean初始化及@PostConstruc执行顺序示例详解》本文给大家介绍SpringBean初始化及@PostConstruc执行顺序,本文通过实例代码给大家介绍的非常详细,对大家的... 目录1. Bean初始化执行顺序2. 成员变量初始化顺序2.1 普通Java类（非Spring环境）(
阅读更多...
Apache Ignite缓存基本操作实例详解

Apache Ignite缓存基本操作实例详解

《ApacheIgnite缓存基本操作实例详解》文章介绍了ApacheIgnite中IgniteCache的基本操作,涵盖缓存获取、动态创建、销毁、原子及条件更新、异步执行,强调线程池注意事项,避免... 目录一、获取缓存实例（Getting an Instance of a Cache）示例代码：二、动态
阅读更多...
Olingo分析和实践之OData框架核心组件初始化(关键步骤)

Olingo分析和实践之OData框架核心组件初始化(关键步骤)

《Olingo分析和实践之OData框架核心组件初始化(关键步骤)》ODataSpringBootService通过初始化OData实例和服务元数据,构建框架核心能力与数据模型结构,实现序列化、URI... 目录概述第一步：OData实例创建1.1 OData.newInstance() 详细分析1.1.1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2