21xrx.com
2025-03-30 17:30:46 Sunday
文章检索 我的文章 写文章
C++中的双端队列deque的使用
2023-07-13 18:13:12 深夜i     13     0
C++ 双端队列 deque 数据结构 STL

C++中的双端队列deque是一种支持在队头和队尾进行插入和删除操作的容器。deque是“double-ended queue”的缩写，也被称为双端队列。deque底层实现为一个动态数组，具有随机访问的能力，因此在访问元素时效率很高。

deque的定义方式如下：

std::deque<T> deque_name;

其中T为deque中存储元素的类型，deque_name为deque的变量名。deque的定义可以设置初始元素个数和初始元素值，例如：

std::deque<int> mydeque(5, 100); // 包含5个整数，每个值都是100

deque支持的成员函数和操作有很多，以下是其中常用的一些：

1. push_front()： 在队头插入元素

2. push_back()：在队尾插入元素

3. pop_front()：删除队头元素

4. pop_back()：删除队尾元素

5. front()：返回队头元素

6. back()：返回队尾元素

7. size()：返回deque中元素的个数

8. empty()：判断deque是否为空

9. clear()：清空deque中的所有元素

下面是一个使用deque的例子，演示了如何使用双端队列添加、删除、访问元素等基本操作：

#include<deque>
#include<iostream>
int main()
{
  std::deque<int> mydeque; //定义一个空的双端队列
  //在队尾插入三个元素
  mydeque.push_back(1);
  mydeque.push_back(2);
  mydeque.push_back(3);
  //在队头插入两个元素
  mydeque.push_front(4);
  mydeque.push_front(5);
  //打印队列大小和元素值
  std::cout << "deque size: " << mydeque.size() << std::endl;
  for (auto it = mydeque.begin(); it != mydeque.end(); ++it)
  {
    std::cout << *it << " ";
  }
  std::cout << std::endl;
  //删除队头和队尾元素
  mydeque.pop_front();
  mydeque.pop_back();
  //打印队列大小和元素值
  std::cout << "deque size: " << mydeque.size() << std::endl;
  for (auto it = mydeque.begin(); it != mydeque.end(); ++it)
  {
    std::cout << *it << " ";
  }
  std::cout << std::endl;
  //访问队头和队尾元素
  std::cout << "deque front: " << mydeque.front() << std::endl;
  std::cout << "deque back: " << mydeque.back() << std::endl;
  //清空队列
  mydeque.clear();
  return 0;
}

输出结果为：

deque size: 5
5 4 1 2 3
deque size: 3
1 2 3
deque front: 1
deque back: 3

在实际开发中，deque常用于需要在队头和队尾频繁插入和删除元素的场景，如最近最少使用算法(LRU)中维护未使用过的元素集合。deque的应用场景比vector更广泛，是C++中一个非常实用的容器。

  
  

评论区

请求出错了