21xrx.com
2025-03-28 16:08:21 Friday
文章检索 我的文章 写文章
C++实现双端队列模板类的设计
2023-07-06 03:36:08 深夜i     17     0
C++ 双端队列 模板类 设计

双端队列是一种数据结构，它具有队列和栈的特性。在队列头尾都可以进行插入和删除操作，使得数据的处理更加方便和快速。C++语言中的模板类可以很好地实现双端队列的应用。

首先，我们需要定义一个双端队列模板类，它可以在头部和尾部插入和删除元素。以下是基本代码框架：

template <class T>
class Deque{
private:
  // 在此定义私有成员变量
public:
  Deque();
  virtual ~Deque();
  // 在此定义公有成员函数
};

在实现该模板类时，我们需要为其提供以下几种基本操作：

1.在队列头部插入元素

void push_front(T value)
  // 在队列头部插入元素代码实现

2.在队列尾部插入元素

void push_back(T value)
  // 在队列尾部插入元素代码实现

3.从队列头部删除元素

void pop_front()
  // 从队列头部删除元素代码实现

4.从队列尾部删除元素

void pop_back()
  // 从队列尾部删除元素代码实现

5.获取队头元素

T& front()
  // 获取队头元素代码实现

6.获取队尾元素

T& back()
  // 获取队尾元素代码实现

7.判断队列是否为空

bool empty()
  // 判断队列是否为空代码实现

8.获取队列大小

int size()
  // 获取队列大小代码实现

在实现双端队列时，我们可以将其定义为一个动态数组，这样可以实现在常数时间内对队头和队尾的插入和删除操作。以下是具体的代码实现：

template <class T>
class Deque{
private:
  T* data;  // 动态数组
  int capacity; // 容量
  int frontIndex; // 队头位置
  int rearIndex; // 队尾位置
  void resize(int newCapacity); // 扩容函数
public:
  Deque();
  virtual ~Deque();
  void push_front(T value);
  void push_back(T value);
  void pop_front();
  void pop_back();
  T& front();
  T& back();
  bool empty();
  int size();
};
template <class T>
Deque<T>::Deque(){
  capacity = 10;
  data = new T[capacity];
  frontIndex = rearIndex = capacity / 2;
}
template <class T>
Deque<T>::~Deque(){
  delete[] data;
}
template <class T>
void Deque<T>::push_front(T value){
  if (frontIndex == 0) {
    resize(capacity * 2); // 扩容
  }
  data[--frontIndex] = value;
}
template <class T>
void Deque<T>::push_back(T value){
  if (rearIndex == capacity - 1) {
    resize(capacity * 2); // 扩容
  }
  data[rearIndex++] = value;
}
template <class T>
void Deque<T>::pop_front(){
  if (empty()) {
    throw "队列为空，无法弹出元素";
  } else {
    frontIndex++;
  }
}
template <class T>
void Deque<T>::pop_back(){
  if (empty()) {
    throw "队列为空，无法弹出元素";
  } else {
    rearIndex--;
  }
}
template <class T>
T& Deque<T>::front(){
  if (empty()) {
    throw "队列为空，无法获取队头元素";
  } else {
    return data[frontIndex];
  }
}
template <class T>
T& Deque<T>::back(){
  if (empty()) {
    throw "队列为空，无法获取队尾元素";
  } else {
    return data[rearIndex-1];
  }
}
template <class T>
bool Deque<T>::empty(){
  return frontIndex == rearIndex;
}
template <class T>
int Deque<T>::size(){
  return rearIndex - frontIndex;
}
template <class T>
void Deque<T>::resize(int newCapacity) {
  T* newData = new T[newCapacity];
  int newSize = size();
  for (int i = frontIndex, j = 0; i < rearIndex; i++, j++) {
    newData[newCapacity/2 - newSize/2 + j] = data[i];
  }
  capacity = newCapacity;
  frontIndex = newCapacity / 2 - newSize / 2;
  rearIndex = frontIndex + newSize;
  delete[] data;
  data = newData;
}

综上所述，我们可以通过C++模板类的设计，实现一个高效的双端队列。利用动态数组的优势，在恰当的时候扩容和缩容，可大大提高队列的性能和效率，使得其更适用于各种实际应用场景。

  
  

评论区