使用模板类和循环数组实现动态双端队列

双端队列（Deque），也称为双向队列，是一种队列类型，可以在前端和后端进行插入和删除操作。双端队列是一种数据结构，它将栈和队列的功能结合到单一数据结构中。

在本教程中，我们将使用模板类和循环数组来创建一个动态双端队列。

使用模板类和循环数组，创建一个具有以下功能的动态双端队列

• front() 返回双端队列的第一个元素。
• size() 返回双端队列的元素数量。
• back() 返回双端队列的最后一个元素。
• capacity() 返回双端队列当前的最大元素数量。
• push back(X): 使用 push back 在双端队列的末尾插入 X。
• empty(): 检查双端队列是否为空。
• push front(X): 使用 push front 在双端队列的开头插入 X。
• pop front(): 从双端队列的开头移除一个元素。
• Pop back(): 从双端队列的末尾移除一个元素。

下面是分步说明

• 双端队列最初是空的。
• 将 1 添加到双端队列的末尾
• 将元素 2 和 3 添加到双端队列的末尾。
• 将 4 添加到双端队列的开头。
• 将 5 添加到双端队列的末尾。
• 从双端队列的开头选择两个元素，从末尾选择两个元素。

方法： 当数组容量达到上限时，其思路是将其大小加倍并将先前数组的元素复制到新数组中。按照以下步骤解决问题

• 要使用双端队列，请设置四个变量：frontIndex、backIndex、sizeVar 和 capacityVar，以及一个数组 arr[]。
• 编写一个名为 capacity() 的函数，它返回 capacityVar 变量的值并确定当前正在使用的数组的大小。
• 编写一个 size() 函数，它计算双端队列中的元素并返回 sizeVar 变量的值。
• 创建一个名为 full() 的函数，它检查双端队列是否已满，如果 sizeVar 等于 capacityVar，则返回 true。否则，返回 false。
• 编写一个 empty() 函数，它检查双端队列是否为空，如果 frontIndex 和 backIndex 都为 -1，则返回 true。否则，返回 false。
• 创建一个名为 Front() 的函数，它打印双端队列的第一个元素。如果双端队列不为空，则打印 arr[frontIndex] 处的元素。
• 创建一个 Back() 函数来打印双端队列的最后一个元素。如果双端队列不为空，则打印 arr[BackIndex] 处的元素。
• 创建一个 push back(X) 函数以在双端队列的末尾插入一个元素
  1. 如果双端队列已满，则将当前数组的大小加倍并将先前数组的元素复制到新数组中。
  2. 如果双端队列为空，将 frontIndex 和 backIndex 设置为 0，然后将 X 设置为 arr[frontIndex] 和 arr[backIndex]，并将 sizeVar 递增 1。
  3. 如果不是，则将 backIndex 设置为 (backIndex+1)%capacityVar，将 X 分配给 arr[backIndex]，并将 sizeVar 递增 1。
• 编写一个名为 push front(X) 的函数，它在双端队列的开头插入一个元素
  1. 如果双端队列已满，则将当前数组的大小加倍并将先前数组的元素复制到新数组中。
  2. 如果双端队列为空，将 frontIndex 和 backIndex 设置为 0，然后将 X 设置为 arr[frontIndex] 和 arr[backIndex]，并将 sizeVar 递增 1。
  3. 如果不是，则将 frontIndex 更改为 (frontIndex-1 + capacityVar)%capacityVar，将 X 分配给 arr[frontIndex]，并将 sizeVar 递增 1。
• 编写一个名为 pop front() 的函数，以从双端队列的开头删除一个元素
  1. 如果双端队列为空，则打印“下溢”。
  2. 如果 sizeVar 大于 1，则将 frontIndex 和 backIndex 都设置为 -1，并将 sizeVar 递减 1。
  3. 否则，应将 FrontIndex 更新为 frontIndex = (frontIndex+1)%capacityVar，并将 sizeVar 递减 1。
• 创建一个名为 pop back() 的函数，以从双端队列的开头删除一个元素
  1. 如果双端队列为空，则打印“下溢”。
  2. 否则，如果 sizeVar 等于 1，则将 frontIndex 和 backIndex 都设置为 -1，并将 sizeVar 递减 1。
  3. 否则，将 sizeVar 递减 1，并将 backIndex 更新为 backIndex = (backndex-1 + capacityVar)%capacityVar。

上述方法实现如下

C++ 程序

输出

Current capacity 16
Current size 9
Front element 9
Rear element 8

Pop an element from front
Pop an element from back

Current capacity 16
Current size 7
Front element 7
Rear element 6

时间复杂度 将为 O(N)。

辅助空间 将为 O(N)。