c++中如何使用数组实现双端队列_c++数组双端队列实现方法-C++-PHP中文网

c++中如何使用数组实现双端队列_c++数组双端队列实现方法

下次还敢

发布： 2025-10-07 17:45:02

原创

479人浏览过

答案：使用固定大小数组和循环索引实现双端队列，通过front和rear指针支持两端插入删除。初始化时front和rear为0，利用取模运算实现循环，避免越界并提高空间利用率。提供判空、判满、插入、删除及访问首尾元素操作，适合理解底层机制，实际应用建议用std::deque。

c++中如何使用数组实现双端队列_c++数组双端队列实现方法

在C++中，可以使用数组手动实现双端队列（deque），即允许从队列的前端和后端进行插入和删除操作。虽然标准库提供了 std::deque，但了解如何用数组实现有助于理解底层机制。

基本思路与结构设计

使用一个固定大小的数组和两个指针（或索引）front 和 rear 来标记队列的首尾位置。为了高效利用空间，可以让数组“循环”使用，即当 rear 到达数组末尾时，自动回到开头（前提是前面有空位）。

关键点：

数组大小固定，需预先定义容量。
front 指向队列第一个元素的位置。
rear 指向队列最后一个元素的下一个位置（类似左闭右开）。
通过取模运算实现循环效果。

核心操作实现

以下是主要成员函数的实现逻辑：

立即学习“C++免费学习笔记（深入）”；

const int MAX_SIZE = 100;
class ArrayDeque {
private:
   int arr[MAX_SIZE];
   int front;
   int rear;
   int capacity;
public:
   ArrayDeque() {
      capacity = MAX_SIZE;
      front = 0;
      rear = 0;
   }

判断队列是否为空或满：

   bool isEmpty() {
      return front == rear;
   }
   bool isFull() {
      return (rear + 1) % capacity == front;
   }

从队尾插入（pushBack）：

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

   void pushBack(int value) {
      if (isFull()) {
         cout << "Deque is full\n";
         return;
      }
      arr[rear] = value;
      rear = (rear + 1) % capacity;
   }

从队头插入（pushFront）：

   void pushFront(int value) {
      if (isFull()) {
         cout << "Deque is full\n";
         return;
      }
      front = (front - 1 + capacity) % capacity;
      arr[front] = value;
   }

从队头删除（popFront）：

   void popFront() {
      if (isEmpty()) {
         cout << "Deque is empty\n";
         return;
      }
      front = (front + 1) % capacity;
   }

从队尾删除（popBack）：

   void popBack() {
      if (isEmpty()) {
         cout << "Deque is empty\n";
         return;
      }
      rear = (rear - 1 + capacity) % capacity;
   }

获取队头和队尾值：

   int getFront() {
      if (isEmpty()) {
         throw runtime_error("Deque is empty");
      }
      return arr[front];
   }
   int getBack() {
      if (isEmpty()) {
         throw runtime_error("Deque is empty");
      }
      return arr[(rear - 1 + capacity) % capacity];
   }
};