双端队列(Deque)原理及实现

简介: 双端队列支持在队头和队尾高效地插入、删除元素,时间复杂度均为O(1)。相比标准队列的“先进先出”,它更灵活,类似两端可进出的过街天桥。可用链表或环形数组实现,常用于算法题中模拟栈或队列。

基本原理
如果你理解了前面讲解的内容,这个双端队列其实没啥可讲的了。所谓双端队列,主要是对比标准队列(FIFO 先进先出队列)多了一些操作罢了:
class MyDeque {
// 从队头插入元素,时间复杂度 O(1)
void addFirst(E e);

// 从队尾插入元素,时间复杂度 O(1)
void addLast(E e);

// 从队头删除元素,时间复杂度 O(1)
E removeFirst();

// 从队尾删除元素,时间复杂度 O(1)
E removeLast();

// 查看队头元素,时间复杂度 O(1)
E peekFirst();

// 查看队尾元素,时间复杂度 O(1)
E peekLast();

}
标准队列 只能在队尾插入元素,队头删除元素,而双端队列的队头和队尾都可以插入或删除元素。
普通队列就好比排队买票,先来的先买,后来的后买;而双端队列就好比一个过街天桥,两端都可以随意进出。当然,双端队列的元素就不再满足「先进先出」了,因为它比较灵活嘛。
在做算法题的场景中,双端队列用的不算很多。感觉只有 Python 用到的多一些,因为 Python 标准库没有提供内置的栈和队列,一般会用双端队列来模拟标准队列。
用链表实现双端队列
很简单吧,直接复用 我们之前实现的MyLinkedList 或者标准库提供的 LinkedList 就行了。因为双链表本就支持 O(1) 时间复杂度在链表的头尾增删元素:
import java.util.LinkedList;

public class MyListDeque {
private LinkedList list = new LinkedList<>();

// 从队头插入元素,时间复杂度 O(1)
void addFirst(E e) {
    list.addFirst(e);
}

// 从队尾插入元素,时间复杂度 O(1)
void addLast(E e) {
    list.addLast(e);
}

// 从队头删除元素,时间复杂度 O(1)
E removeFirst() {
    return list.removeFirst();
}

// 从队尾删除元素,时间复杂度 O(1)
E removeLast() {
    return list.removeLast();
}

// 查看队头元素,时间复杂度 O(1)
E peekFirst() {
    return list.getFirst();
}

// 查看队尾元素,时间复杂度 O(1)
E peekLast() {
    return list.getLast();
}

public static void main(String[] args) {
    MyListDeque<Integer> deque = new MyListDeque<>();
    deque.addFirst(1);
    deque.addFirst(2);
    deque.addLast(3);
    deque.addLast(4);

    System.out.println(deque.removeFirst()); // 2
    System.out.println(deque.removeLast()); // 4
    System.out.println(deque.peekFirst()); // 1
    System.out.println(deque.peekLast()); // 3
}

}
用数组实现双端队列
也很简单吧,直接复用我们在 环形数组技巧 中实现的 CycleArray 提供的方法就行了。环形数组头尾增删元素的复杂度都是 O(1):
class MyArrayDeque {
private CycleArray arr = new CycleArray<>();

// 从队头插入元素,时间复杂度 O(1)
void addFirst(E e) {
    arr.addFirst(e);
}

// 从队尾插入元素,时间复杂度 O(1)
void addLast(E e) {
    arr.addLast(e);
}

// 从队头删除元素,时间复杂度 O(1)
E removeFirst() {
    return arr.removeFirst();
}

// 从队尾删除元素,时间复杂度 O(1)
E removeLast() {
    return arr.removeLast();
}

// 查看队头元素,时间复杂度 O(1)
E peekFirst() {
    return arr.getFirst();
}

// 查看队尾元素,时间复杂度 O(1)
E peekLast() {
    return arr.getLast();
}

}

相关文章
|
存储 Linux 虚拟化
开源虚拟化平台oVirt4.3简单搭建实践(下)
开源虚拟化平台oVirt4.3简单搭建实践(下)
2153 0
开源虚拟化平台oVirt4.3简单搭建实践(下)
|
11月前
|
存储 缓存 算法
学习数据结构和算法的框架思维
本文系统梳理数据结构与算法核心思想:所有数据结构本质为数组或链表的变形,基本操作均为遍历与访问;算法本质是穷举,关键在于“无遗漏”和“无冗余”。掌握框架思维,方能以不变应万变,高效刷题。
学习数据结构和算法的框架思维
|
11月前
|
人工智能 测试技术 API
Minion框架早已实现PTC:超越传统Tool Calling的Agent架构
Minion框架早于Anthropic的PTC特性,率先采用“LLM规划+代码执行”架构,通过Python编排工具调用,显著降低Token消耗、提升性能与可靠性。支持完整生态、状态管理与多模型协作,已在生产环境验证大规模数据处理、多源整合等复杂任务,推动AI Agent迈向高效、可扩展的下一代架构。
|
11月前
|
存储 算法 API
时间空间复杂度入门
初学者只需掌握:用Big O表示时空复杂度,保留最高次项;时间复杂度看循环嵌套层数,空间复杂度看额外内存占用;通常分析最坏情况,越小越好。n指输入规模,如数组长度。
|
存储 缓存 编解码
阿里云服务器实例规格怎么选?经济型、通用算力型、计算型、通用型、内存型场景化选购指南
阿里云服务器的实例规格有经济型、通用型、计算型、内存型、通用算力型、大数据型、本地SSD型、高主频型、突发型、共享型等不同种类的实例规格,以满足不同用户和业务场景的需求。对于初次接触阿里云服务器的用户来说,如何选择合适的实例规格成为了一个重要的问题。本文将为大家解析阿里云的经济型、通用算力型、计算型、通用型和内存型实例规格的主要性能和适用场景情况,帮助用户根据实际需求选择合适的云服务器实例。
1256 10
|
7月前
|
编译器 Linux C语言
【2026最新】VS Code编写C语言程序图解教程(超级详细)
本文详解在Windows平台配置VS Code运行C语言程序的完整流程:先安装MinGW(GCC编译器),再依次安装C/C++和Code Runner两大扩展插件,并推荐中文化设置。操作直观、跨平台一致,零基础也可快速上手编译与运行C代码。
|
11月前
|
算法 数据可视化
二叉树的递归/层序遍历 递归遍历(DFS)
本文详解二叉树的遍历框架,涵盖递归遍历的固定访问顺序及前、中、后序的本质区别——即代码在递归函数中的位置不同所致。同时深入讲解层序遍历(BFS)的三种实现方式,适用于不同场景,尤其适合求最短路径问题;而DFS则因结构天然适合搜索所有路径。通过实例对比,阐明BFS与DFS的应用偏好及原理依据。
二叉树的递归/层序遍历 递归遍历(DFS)
|
11月前
|
人工智能 自然语言处理 Cloud Native
AI时代代码开发
AI时代重塑软件开发,本课程聚焦DeepSeek+Cursor+Devbox+Sealos工具链,打造零基础全栈开发新范式。无需编程经验,3小时掌握从需求分析、数据库设计到云部署的AI全流程开发,助力开发者高效构建并上线项目,抢占智能化转型先机。(238字)
|
缓存 算法 调度
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
1085 5
|
机器学习/深度学习 API
机器学习入门(七):线性回归原理,损失函数和正规方程
机器学习入门(七):线性回归原理,损失函数和正规方程
2417 1