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

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。

相关文章

CSS实现元素撑满剩余空间的五种方法

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中，我们经常需要让某个元素占据容器的剩余空间，本文将介绍5种不同的方法来实现这个需求，并分析各种方法的优缺点，感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中，我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
Java中常见队列举例详解(非线程安全)

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,：本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
C++ RabbitMq消息队列组件详解

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》：本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A
阅读更多...
Python程序的文件头部声明小结

Python程序的文件头部声明小结

《Python程序的文件头部声明小结》在Python文件的顶部声明编码通常是必须的,尤其是在处理非ASCII字符时,下面就来介绍一下两种头部文件声明,具有一定的参考价值,感兴趣的可以了解一下... 目录一、# coding=utf-8二、#!/usr/bin/env python三、运行Python程序四、
阅读更多...
golang实现延迟队列(delay queue)的两种实现

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列：邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版：go自带的time
阅读更多...
C++类和对象之初始化列表的使用方式

C++类和对象之初始化列表的使用方式

《C++类和对象之初始化列表的使用方式》：本文主要介绍C++类和对象之初始化列表的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C++初始化列表详解：性能优化与正确实践什么是初始化列表？初始化列表的三大核心作用1. 性能优化：避免不必要的赋值操作2. 强
阅读更多...
SpringIOC容器Bean初始化和销毁回调方式

SpringIOC容器Bean初始化和销毁回调方式

《SpringIOC容器Bean初始化和销毁回调方式》：本文主要介绍SpringIOC容器Bean初始化和销毁回调方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录前言1.@Bean指定初始化和销毁方法2.实现接口3.使用jsR250总结前言Spring Bea
阅读更多...
Spring实现Bean的初始化和销毁的方式

Spring实现Bean的初始化和销毁的方式

《Spring实现Bean的初始化和销毁的方式》：本文主要介绍Spring实现Bean的初始化和销毁的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Bean的初始化二、Bean的销毁总结在前面的章节当中介绍完毕了ApplicationContext，也就
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2