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

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。

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
C++从序列容器中删除元素的四种方法

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque
阅读更多...
C++常见容器获取头元素的方法大全

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素（即第一个元素）是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa
阅读更多...
Spring组件初始化扩展点BeanPostProcessor的作用详解

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB
阅读更多...
Spring Boot整合消息队列RabbitMQ的实现示例

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
CSS3中使用flex和grid实现等高元素布局的示例代码

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》：本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法，通过简单的两列实现、每行放置3列以及全部代码的展示，展示了这两种布局方式的实现细节和效果，详细内容请阅读本文，希望能对你有所帮助... 过往的实现方法是使用浮动加
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2