C++实现双端队列Deque |21xrx.com

C++实现双端队列Deque

2023-06-27 18:06:15 深夜i 31 0

C++ 双端队列 Deque 实现数据结构

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能够更加方便地完成一些队列操作，例如双向遍历。

上一篇: idea打包java可执行jar包

下一篇: C++：从键盘输入10个数，计算平均值

评论区

相似文章