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

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。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2