DEV Community
·
641. 设计循环双端队列
内容提要
设计一个循环双端队列类 `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，否则返回最后一个元素。
