C++——双端队列(deque)
·
1. 双端队列(deque)
双端队列(deque)是队列的一种变形,一般队列只能在队尾添加元素(push),在队首删除元素(pop),双端队列则同时在队首或者队尾执行添加和删除工作。C++中,使用双端队列需要包含头文件<deque>。C++中队列的基本操作如下:
- push_back():在队列尾部添加元素,无返回值。这个操作跟普通队列(queue)的push()方法类似,在队列的尾部添加一个元素;
- push_front():在队列头部添加元素,无返回值;
- pop_back():删除队列尾部的元素,无返回值;
- pop_front():删除队列头部的元素,无返回值;
- front() :获得队列头部元素。此函数返回值为队列的头部元素,常与pop_front()函数一起,先通过front()获得队列头部元素,然后用pop_front()将其从队列中删除;
- back(): 获得队列尾部元素。此函数返回值为队列的尾部元素,常与pop_back()函数一起,先通过back()获得队列头部元素,然后用pop_back()将其从队列中删除;
- size():获得队列大小。此函数返回队列的大小,返回值是“size_t”类型的数据,“size_t”是“unsigned int”的别名;
- empty() :判断队列是否为空。此函数返回队列是否为空,返回值是bool类型。队列空:返回true;不空:返回false。
更多介绍,可以参考:[C++ STL] deque使用详解。
下面是一个实例:
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main(void) {
deque<string> q;
q.push_back("world"); //将"world"入队尾
cout << "将'world'入队尾后q.back(): " << q.back() << endl; //输出队列尾部元素,就是"world"(此时队列中只有一个元素,队列头=队列尾)
q.push_front("Hello "); //将"Hello "入队首
cout << "将'Hello '入队首后q.front(): " << q.front() << endl; //输出队列头部元素,就是"Hello "
cout << "此时队列的尾部元素: " << q.back() << endl; //输出队列中尾部元素,就是"world"
q.push_back("!"); //将"!"入队尾
q.pop_front(); //将队列头部的元素删除(删除"Hello "),无返回值
cout << "删除队列头部元素后,新队列的头部元素: " << q.front() << endl; //此时队列头部元素为"world"
cout << "队列是否为空(0:非空;1:空): " << q.empty() << endl; //empty()返回bool值,表示队列是否为空,此时不为空,返回0
q.pop_back(); //将队列尾部的元素删除(删除"!",此时队列中只有一个"world"),无返回值
cout << "又删除了队尾元素‘!',现在队列是否为空(0:非空;1:空): " << q.empty() << endl; //empty()返回bool值,表示队列是否为空,此时队列不为空,返回0
cout << "此时队列的大小: " << q.size() << endl; //返回队列的大小,此时队列大小为1,输出1
return 0;
}
上面代码的输出如下:
使用双端队列可以构造单调队列,解决一些算法问题。比如LeetCode中滑动窗口的问题。
更多推荐
已为社区贡献6条内容
所有评论(0)