一，双端队列
双端队列（Deque，Double-Ended Queue）
双端队列（Deque）是一种允许从队列的两端（头部和尾部）进行插入和删除操作的数据结构。与常规队列（Queue）只能在一端进行插入（入队）和另一端进行删除（出队）不同，双端队列既可以在前端插入或删除元素，也可以在后端插入或删除元素。
双端队列的特点
- 双端操作：可以在队列的两端执行插入、删除和访问操作。
- 支持的操作：
push_front(x)：将元素x插入到队列的前端。push_back(x)：将元素x插入到队列的后端。pop_front()：删除并返回队列前端的元素。pop_back()：删除并返回队列后端的元素。front()：返回队列前端的元素，但不删除它。back()：返回队列后端的元素，但不删除它。empty()：检查队列是否为空。size()：返回队列中元素的数量。
双端队列的应用
双端队列因其高效的两端操作而在一些特定场景中非常有用：
- 滑动窗口问题：在计算连续子数组的最大值或最小值时，双端队列能有效地存储窗口中的元素，并快速访问队列的两端。
- 任务调度和缓存管理：双端队列适用于需要快速访问任务的两端或者缓存的管理。
- 双向链表替代：在一些场景中，双端队列可以作为双向链表的替代，用于实现高效的插入和删除操作。
C++ STL 中的 deque 类
在 C++ 中，双端队列由标准库中的 std::deque 提供，它是一种可以在两端进行高效插入和删除操作的容器。
示例代码：C++ 中的双端队列
#include <iostream>
#include <deque>using namespace std;int main() {// 创建一个双端队列deque<int> dq;// 从尾部插入元素dq.push_back(10);dq.push_back(20);dq.push_back(30);// 从头部插入元素dq.push_front(5);dq.push_front(0);// 输出双端队列的内容cout << "Deque elements: ";for (int i : dq) {cout << i << " ";}cout << endl;// 删除尾部元素dq.pop_back();// 删除头部元素dq.pop_front();// 输出删除后的内容cout << "Deque after pop operations: ";for (int i : dq) {cout << i << " ";}cout << endl;// 获取头部和尾部元素cout << "Front element: " << dq.front() << endl;cout << "Back element: " << dq.back() << endl;return 0;
}
二，代码实现
1，链表实现
1）一代
错误：
代码：
#include<iostream>using namespace std;struct Node
{int value;Node* last;Node* next;Node(int x) : value(x) { last = NULL; next = NULL; };};class Dequeue
{private:Node* head = NULL, * tail = NULL;
public:void head_insert(int x){if (head == NULL || tail == NULL){Node* p = new Node(x);head = tail = p;}else{Node* p = new Node(x);head->last = p;p->next = head;head = p;}}void tail_insert(int x){if (head == NULL || tail == NULL){Node* p = new Node(x);head = tail = p;}else{Node* p = new Node(x);tail->next = p;p->last = tail;tail = p;}}int head_pop(){if (head == NULL){cout << "the dequeue is empty !" << endl;return -1;}int result = head->value;if (head->next == NULL){Node* temp = head;delete temp;head = NULL;return result;}head = head->next;delete head->last;//if dont judge if the next of head is NULL,the line code will go wrong. return result;}int tail_pop(){if (tail == NULL){cout << "the dequeue is empty !" << endl;return -1;}int result = tail->value;if (tail->last == NULL){Node* temp = tail;delete temp;tail = NULL;return result;}tail = tail->last;delete tail->next;return result;}//I am too lazy to code both of head and tail top // So I decide to combine themint top(int n){if (head == NULL || tail == NULL){cout << "the dequeue is empty !" << endl;return -1;}if (n == 0) return head->value;else if (n == 1) return tail->value;else{cout << "please enter the right parameter !" << endl;return -1;}}//head ->tail
};int main()
{Dequeue dequeue;for (int i = 0; i < 5; i++){dequeue.head_insert(i);cout<<"the head value is "<<dequeue.top(0)<<endl;dequeue.head_pop();}cout<<dequeue.head_pop()<<endl;return 0;}改进：
3. 重复的空指针检查
head_insert() 和 tail_insert() 中的空指针检查相似，您可以将其提取成一个公共函数来减少代码重复。
4. 函数命名改进
head_insert 和 tail_insert 可以改成更直观的命名，比如 push_front 和 push_back，这些是常见的数据结构术语。
5. Node 构造函数简化
在 Node 结构体的构造函数中，您已经通过初始化列表为 last 和 next 指针赋了 NULL 值。可以在构造函数内直接给默认值，而无需在构造函数体内做额外的赋值操作。
6. 潜在的内存泄漏
在 head_pop() 和 tail_pop() 中，您虽然删除了节点，但是并没有及时清除其他指针指向的节点。因此，在删除节点时需要小心，确保没有其他指针依赖于被删除的节点。
我发现一个非常严重的错误：
修改：
2，数组实现
1）原理
环形数组，左右边界变量head和tail，存入的数据个数size。
2）代码展示
a，第一次尝试
错误：
class Dequeue
{
private:int head = 0, tail = 0, size = 0;int* arr;public:Dequeue(int n) arr = new int[n];};企图省略函数体括号
在 C++ 中，当一个函数或控制结构（如 if、for、while）只有一行代码时，可以省略大括号 {}，但仅限于控制结构。对于函数，即使是只有一行代码，也需要使用大括号。这意味着您不能省略函数体的 {}。
补充：成员变量的初始化
在 C++ 中，构造函数的成员变量可以通过两种方式初始化：初始化列表 和 构造函数体内赋值。不过，不同类型的成员变量和不同的场景可能更倾向于使用其中的一种方式。下面我将详细说明这两种方式以及何时使用它们。
1. 初始化列表
初始化列表是在构造函数的参数列表后面的一对冒号和花括号之前的部分，用于初始化类的成员变量。它在对象构造时执行，并且在构造函数体内执行任何代码之前，优先执行。
优点：
- 更高效：通过初始化列表直接初始化成员变量，避免了成员变量先进行默认初始化再赋值的过程。
- 适用于常量和引用类型：某些成员变量（例如常量
const或引用类型&）必须在初始化时赋值，不能在构造函数体内进行赋值。 - 动态内存分配：像指针等动态分配内存的成员变量，通常在初始化列表中进行内存分配。
示例：
class MyClass {
private:int x;const int y;int* arr;public:// 初始化列表：直接初始化成员变量MyClass(int a, int b) : x(a), y(b), arr(new int[10]) {// 构造函数体，其他逻辑}~MyClass() {delete[] arr; // 释放动态分配的内存}
};
2. 构造函数体内赋值
构造函数体内也可以对成员变量进行赋值操作。不过，这不是直接初始化，而是先执行默认构造，再赋值。这种方式的效率较低，尤其是对于内置类型或对象类型（如 int、double 等），因为它们会先进行默认初始化（通常是零初始化），然后再被赋予新值。
示例：
class MyClass {
private:int x;int* arr;public:MyClass(int a) {x = a; // 先默认初始化，再赋值arr = new int[10]; // 在构造函数体内分配内存}~MyClass() {delete[] arr; // 释放内存}
};
3. 什么时候使用初始化列表 vs. 构造函数体内赋值
-
初始化列表适用场景：
- 常量（
const）成员变量：常量成员变量必须在初始化列表中初始化，因为它们不能在构造函数体内赋值。 - 引用类型成员变量：引用类型也必须在初始化列表中初始化。
- 需要高效初始化的类型：对于基本数据类型（如
int、float等）和复杂数据类型（如std::vector、std::string等），通过初始化列表初始化更加高效，因为它避免了不必要的默认初始化和赋值。 - 动态内存分配：如果成员是指针，且需要在构造时进行动态内存分配（如
new），通常会在初始化列表中进行。
- 常量（
-
构造函数体内赋值适用场景：
- 对于不需要立即初始化的成员变量，可以在构造函数体内赋值。虽然效率较低，但对于一些简单的类型，可能并不会显著影响性能。
- 如果成员变量是由其他成员的计算结果或构造函数参数决定的，可以在构造函数体内进行更复杂的逻辑处理。
总结：
- 初始化列表 是初始化成员变量的推荐方式，尤其对于常量、引用类型或需要动态分配内存的成员。它通常更高效，并且在某些场景下是必须的。
- 构造函数体内赋值 可以用于不需要立即初始化的成员变量，尽管效率较低，但对某些场景是可接受的。
建议尽量使用 初始化列表，特别是当成员变量是常量、引用或需要动态分配内存时。
析构函数
第一次尝试：
#include<iostream>using namespace std;class Dequeue
{
private:int head = 0, tail = 0, size,input = 0;int* arr;public:Dequeue(int n) : arr(new int[n]) { size = n; }~Dequeue() { delete[] arr; }void front_push(int x){if (input > size){cout << "the dequeue is full !" << endl;return;}if (head == 0){arr[size - 1] = x;head = size - 1;}else{arr[--head] = x;}input++;}void back_push(int x){if (input > size){cout << "the dequeue is full !" << endl;return;}if (tail == size - 1){tail = 0;arr[tail] = x;}else{arr[++tail] = x;}input++;}int front_pop(){if (input == 0){cout << "the dequeue is empty !" << endl;return -1;}return arr[head++];input--;}int back_pop(){if (input == 0){cout << "the dequeue is empty !" << endl;return -1;}return arr[tail--];input--;}bool empty(){if (input == 0) return true;else false;}//we dont want to code the top function
};int main()
{Dequeue dequeue(5);cout << dequeue.back_pop() << endl;for (int i = 0; i < 6; i++){dequeue.back_push(i);}dequeue.front_push(7);return 0;
}改进：
主要改进点：
-
边界检查的简化：
input > size应该改为input == size，因为当input等于size时表示队列已满。empty()函数中的else不需要写，可以简化成return input == 0;。- 检查
input来判断是否为空或者已满的地方，可以提取成一个单独的辅助函数，避免代码重复。
-
front_pop和back_pop中的input--顺序问题：- 在
return arr[head++]这样的代码中，您先返回了head的值，然后才做了input--，会导致先处理返回值再减小input，应该在返回之前先减小input。
- 在
-
尾部操作时循环移动：
back_push和front_push使用循环时，应该更加明确地更新tail和head，避免使用复杂的条件分支。
// 辅助函数: 检查是否满bool is_full() const {return input == size;}// 辅助函数: 检查是否空bool is_empty() const {return input == 0;}void front_push(int x){if (is_full()){cout << "The dequeue is full!" << endl;return;}head = (head - 1 + size) % size; // 环形队列arr[head] = x;input++;}void back_push(int x){if (is_full()){cout << "The dequeue is full!" << endl;return;}arr[tail] = x;tail = (tail + 1) % size; // 环形队列input++;}4，与数学里面遇到重复复杂结构使用换元，编程里面遇到重复使用结构，我们也试着去构造函数来简化代码。例如上图的辅助函数。
5，对于边界的更新，特别是head和tail，使用模运算实现周期变换，因为mod n，那结果是0到n-1范围内。特别是head逆时针（向左移动循环）。
如果只是有if和else也可以使用三目运算来简化代码。
head = (head == 0) ? size - 1 : head - 1;
错误：
a，在return代码后面还进行操作，这种低级错误。