Deque（双端队列）是一种既能从队头进队出也能从队尾进队出的数据结构。在C++中，STL提供了一个deque容器，但也可以手动实现一个deque。

实现deque需要使用循环数组，它能够快速添加或删除元素。下面是一个简单的C++代码实现deque：

#include <iostream>
using namespace std;
template <typename T>
class Deque {
private:
  T* arr;   // 存储元素的数组
  int size;  // 数组大小
  int front; // 队头
  int rear;  // 队尾
public:
  // 构造函数
  Deque() {
    size = 10;
    arr = new T[size];
    front = -1;
    rear = -1;
  }
  // 入队
  void push_front(T data) {
    if (front == 0 && rear == size - 1)
      cout << "Deque is full" << endl;
      return;
    
    // 如果queue目前为空，则在第一个位置插入数据
    if (front == -1) {
      front = rear = 0;
      arr[front] = data;
      return;
    }
    // 如果在队头有空位，则向队头加入数据
    if (front != 0) {
      front--;
      arr[front] = data;
    }
    // 如果在队尾有空位，则向队尾加入数据
    else if (front == 0 && rear != size - 1) {
      front = size - 1;
      arr[front] = data;
    }
  }
  // 出队
  void pop_front() {
    // 如果队列为空
    if (front == -1)
      cout << "Deque is empty" << endl;
      return;
    
    // 如果队列只有一个元素
    if (front == rear)
      front = rear = -1;
    
    else if (front == size - 1)
      front = 0;
    
    else {
      front++;
    }
  }
  // 入队
  void push_back(T data) {
    // 如果队列满了
    if (front == 0 && rear == size - 1)
      cout << "Deque is full" << endl;
      return;
    
    // 如果队列为空
    if (rear == -1) {
      front = rear = 0;
      arr[rear] = data;
      return;
    }
    // 如果队尾有空位
    if (rear != size - 1) {
      rear++;
      arr[rear] = data;
    }
    // 如果队头有空位
    else if (rear == size - 1 && front != 0) {
      rear = 0;
      arr[rear] = data;
    }
  }
  // 出队
  void pop_back() {
    // 如果队列为空
    if (rear == -1)
      cout << "Deque is empty" << endl;
      return;
    
    // 如果队列只有一个元素
    if (front == rear)
      front = rear = -1;
    
    else if (rear == 0)
      rear = size - 1;
    
    else
      rear--;
    
  }
  // 获取队头的元素
  T getFront() {
    if (front == -1)
      cout << "Deque is empty" << endl;
      return -1;
    
    return arr[front];
  }
  // 获取队尾的元素
  T getRear() {
    if (rear == -1)
      cout << "Deque is empty" << endl;
      return -1;
    
    return arr[rear];
  }
  // 判断队列是否为空
  bool isEmpty() {
    return (front == -1 && rear == -1);
  }
  // 判断队列是否已满
  bool isFull() {
    return (front == 0 && rear == size - 1);
  }
};
int main() {
  Deque<int> dq;
  dq.push_front(10);
  dq.push_front(20);
  dq.push_back(30);
  dq.push_back(40);
  cout << "队头元素：" << dq.getFront() << endl;
  dq.pop_front();
  cout << "队头元素：" << dq.getFront() << endl;
  cout << "队尾元素：" << dq.getRear() << endl;
  dq.pop_back();
  cout << "队尾元素：" << dq.getRear() << endl;
  return 0;
}

在这个例子中，Deque模板类是一个可以存储任意数据类型的。

这个Deque类有一个动态分配的内存用以存储存储元素的数据数组，并且也具有跟踪队列的队头和队尾的变量。 入队函数push_front和push_back，和对应的出队函数pop_front和pop_back用来在队列头部和尾部添加或删除元素。getFront和getRear用来获取队列头部和尾部的元素。

Deque的实现是个很好的例子，展示了如何使用循环数组来实现队列。使用deque能够更加方便地完成一些队列操作，例如双向遍历。

相似文章
• C++ deque的底层实现原理
  C++
  
  
• C++双端队列（deque）
  C++是一种开发高效的编程语言，被广泛应用于各种应用领域，如游戏开发、Web开发、人工智能等。在C++中，双端队列（deque）是一种常见的数据结构，也是STL（标准模板库）中的一种容器类型，可以轻松地实现许多算法和操作。
  
  
• C++序列容器介绍
  C++是一种广泛使用的编程语言，它提供了多种不同的容器类型来实现数据结构和算法。在C++中，序列容器是其中一个最基本的容器类型，它们可以存储有序的元素集合，并提供高效的元素插入、删除和访问操作。
  
  
• C++线程安全deque实现
  C++是一种广泛应用于系统编程、嵌入式编程及游戏开发领域的高级编程语言。在C++的标准库中，deque（double-ended
  
  
• C++ 容器
  C++是一种强大的编程语言，其拥有许多不同种类的容器，用于组织和管理不同类型的数据。在C++中，容器是一种通用类模板，可用于存储和管理各种类型的数据对象。
  
  
• C++ deque的遍历方法
  C++
  
  
• C++ 常用容器类名一览
  C++标准模板库（STL）提供了多个容器类，这些容器类可以方便地存储和管理数据。容器类是一种模板类，可以容纳不同类型的数据。
  
  
• C++ deque 实现入栈功能
  C++中的deque是一种双端队列（double-ended
  
  
• 《掌握Java中的deque：双端队列的使用与实现》
  《掌握Java中的deque：双端队列的使用与实现》
  
  
• Java中怎样使用LinkedList类
  Java中怎样使用LinkedList类
  
  
• TITLE: 探究JAVA中的集合类型
  TITLE: 探究JAVA中的集合类型
  
  
• 探究Java中deque的用法和特点
  探究Java中deque的用法和特点
  
  
• Java的集合框架——Collection详解
  Java的集合框架——Collection详解
  
  
• Java实现双端队列的教程
  Java实现双端队列的教程
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政