DEV Community
·
641. 设计循环双端队列
💡
原文英文，约1100词，阅读约需4分钟。
📝
内容提要
设计一个循环双端队列类 `MyCircularDeque`，支持初始化大小为 `k`，在队列前后插入或删除元素，获取前后元素，检查队列是否为空或已满。使用数组实现，头尾指针实现循环，操作时间复杂度为 O(1)，空间复杂度为 O(k)。
🎯
关键要点
- 设计一个循环双端队列类 MyCircularDeque，支持初始化大小为 k。
- 支持在队列前后插入或删除元素，获取前后元素。
- 检查队列是否为空或已满。
- 使用数组实现，头尾指针实现循环。
- 所有操作的时间复杂度为 O(1)，空间复杂度为 O(k)。
- 初始化时，使用大小为 k 的数组，所有值初始为 -1。
- 前后指针初始化为 0，size 用于跟踪当前元素数量。
- insertFront 方法检查队列是否已满，若未满则在前面插入元素。
- insertLast 方法检查队列是否已满，若未满则在后面插入元素。
- deleteFront 方法检查队列是否为空，若不为空则从前面删除元素。
- deleteLast 方法检查队列是否为空，若不为空则从后面删除元素。
- getFront 方法返回前指针指向的元素，若队列为空则返回 -1。
- getRear 方法返回后指针前的元素，若队列为空则返回 -1。
- isEmpty 方法返回队列是否为空。
- isFull 方法返回队列是否已满。
❓
延伸问答
如何初始化一个循环双端队列？
使用 MyCircularDeque(int k) 构造函数初始化，设置最大大小为 k。
循环双端队列的插入和删除操作的时间复杂度是多少？
所有操作的时间复杂度为 O(1)。
如何检查循环双端队列是否为空？
使用 isEmpty() 方法，如果队列为空返回 true，否则返回 false。
如何从循环双端队列的前面插入元素？
使用 insertFront(value) 方法，检查队列是否已满，若未满则在前面插入元素。
循环双端队列的空间复杂度是多少？
空间复杂度为 O(k)，其中 k 是队列的大小。
如何获取循环双端队列的最后一个元素？
使用 getRear() 方法，若队列为空则返回 -1，否则返回最后一个元素。
➡️
