双端队列(Double-Ended Queue, 简称deque)是一种特殊的数据结构,它结合了队列(Queue)和栈(Stack)的特性,允许在两端进行插入(enqueue)和删除(dequeue)操作。双端队列可以在前端(front)进行入队(push)和出队(pop),也可以在后端(rear)进行入队和出队。这种灵活性使得双端队列在很多应用场景中非常实用,特别是在需要高效地处理双向数据流或需要快速访问两端元素的场合。
基本特征:
- 两端操作: 双端队列允许在队列的头部(front)和尾部(rear)同时进行插入和删除操作。这意味着您可以从队列的开始或结束处添加或移除元素。
- 先进先出(FIFO)与后进先出(LIFO)共存: 根据操作端的不同,双端队列可以表现出队列(FIFO)或栈(LIFO)的行为。在前端出队遵循FIFO原则(最先加入的元素最先离开),在后端出队则遵循LIFO原则(最后加入的元素最先离开)。
- 动态大小: 双端队列的大小通常不是固定的,可以根据需要动态增长或缩小。当元素被添加到队列中时,队列会自动扩容以容纳新元素;当元素被移除时,队列空间会被释放,以保持高效的空间利用率。
- 多用途: 双端队列在许多算法和应用程序中都有广泛应用,如实现回溯、滑动窗口、缓存、双向链表等。它既可用于常规的队列操作,如任务调度、消息队列等,也可用于需要栈功能的场景,如撤销/重做操作记录、深度优先搜索的回溯等。
常见操作:
- push_front: 在队列前端插入元素。
- push_rear: 在队列后端插入元素。
- pop_front: 从队列前端移除并返回元素。
- pop_rear: 从队列后端移除并返回元素。
- peek_front: 查看但不移除队列前端的元素。
- peek_rear: 查看但不移除队队后端的元素。
- is_empty: 判断双端队列是否为空。
- size: 返回双端队列中元素的数量。
实现双端队列的数据结构可以是数组、链表或更复杂的数据结构。使用数组实现时,可能需要进行动态扩容或移动元素以维持高效的插入和删除操作。链表实现则更为灵活,无需考虑连续内存空间的限制,但访问性能可能略逊于数组实现。现代编程语言中通常有内置的双端队列数据结构或第三方库提供高效实现。
总之,双端队列是一种提供两端插入和删除能力的数据结构,它结合了队列和栈的优点,适用于需要高效处理双向数据流或频繁操作两端元素的场景。
在C++中,双向队列,在头文件deque中:
我们可以使用一下它的接口:
#include <iostream>
#include<deque>
void PrintDque(const std::deque<int>& dq)
{
std::deque<int>::const_iterator it = dq.cbegin();
while( it != dq.cend())
{
std::cout << *it++ << ' ';
}
std::cout<<std::endl;
}
int main()
{
std::deque<int> dq;
dq.push_back(12);
dq.push_back(13);
dq.push_back(14);
dq.push_back(15);
PrintDque(dq);
dq.push_front(16);
dq.push_front(17);
dq.push_front(18);
dq.push_front(19);
PrintDque(dq);
dq.pop_back();
dq.pop_back();
dq.pop_back();
dq.pop_back();
PrintDque(dq);
dq.pop_front();
dq.pop_front();
dq.pop_front();
dq.pop_front();
PrintDque(dq);
if(dq.empty())
{
std::cout << "dque is empty" << std::endl;
}
return 0;
}