设计循环双端队列

难度: Medium

设计实现双端队列。

实现 MyCircularDeque 类:

MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4

提示：

1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

Submission

运行时间: 47 ms

内存: 17.2 MB

############################################################
# Write code in file solution.py (Folder: HW 4)
# Post� solution.py in Canvas along with 4 screen shots that shows Leetcode has passed. We will not use screen shot to give 100
# Cut and paste the whole solution.py file in Leetcode and run. All tests must pass
# Note that you should do 4 times in 225, 235,622 and 641
# TA will run solution.py file 4 times in 225, 235,622 and 641
# All tests must pass for 100
########################################################### 

class ListNode:
    #NOTHING CAN BE CHANGED HERE
    def __init__(self, val = 0, next= None):
        self.val = val
        self.next = next
         
            
############################################################
#  class  Slist
###########################################################   
class Slist():
    def __init__(self):
        #NOTHING CAN BE CHANGED HERE
        self._first = None
        self._last = None
        self._len = 0 
        
    #############################
    # WRITE All public functions BELOW
    # YOU CAN HAVE ANY NUMBER OF PRIVATE FUNCTIONS YOU WANT
    #############################
    def __len__(self) -> int:
        return self._len

    def append(self, x: int) -> None:
        self._len = self._len + 1
        self._build_a_node(x,True)
    
    def prepnd(self, x: int) -> None:
        self._len = self._len + 1
        self._build_a_node(x,False)

    def delete_front(self) -> None:
        nodes = [self._first, None]
        if self._unhook(nodes):
            return True
        else:
            return False

    def delete_last(self) -> None:
        nodes = [self._last, None]
        if self._unhook(nodes):
            return True
        else:
            return False

    def _build_a_node(self, i: 'int', append:'bool' = True) -> None:
        n = ListNode(i)
        if self._first == None and self._last == None:
            self._first = n
            self._last = n
        else:
            if append:
                self._last.next = n
                self._last = n
            else:
                n.next = self._first
                self._first = n
    
    def get_front(self) -> int:
        if self._first :
            return self._first.val
        else:
            return -1
        
    def get_last(self) -> int:
        if self._first :
            assert self._last
            return self._last.val
        else:
            return -1
    
    def _unhook(self, nodes: 'List') -> bool:
        if (nodes[0]):
            currentnode = nodes[0]
            previousnode = nodes[1]
            if ((currentnode == self._first) and (currentnode == self._last) and (previousnode == None)):
                assert(self._first == self._last)
                self._first = None
                self._last = None
            elif (currentnode == self._first):
                assert(self._first.next != None)
                self._first = currentnode.next
            elif (currentnode == self._last):
                assert(self._first)
                previousnode.next = None
                self._last = previousnode
            else:
                assert(self._first)
                assert(self._last)
                previousnode.next = currentnode.next
            self._len = self._len - 1
            return True
        else:
            return False
                
    
    def delete(self, i: int) -> bool:
        nodes = self._find(i)
        a = self._unhook(nodes)
        return a
    
    def _find(self, i: int) -> 'List':
        nodes =  [self._first, None]
        while (nodes[0]!= None):
            if nodes[0].val == i:
                return nodes
            nodes[1] = nodes[0]
            nodes[0] = nodes[0].next
        return nodes
  
  
############################################################
#  class  MyStack
#225. Implement Stack using Queues

#https://leetcode.com/problems/implement-stack-using-queues
########################################################### 
# class MyStack:
#     def __init__(self):
#         #NOTHING CAN BE CHANGED HERE
#         self._s = Slist()
    
#     def push(self, x: int) -> None:
#         self._s.prepnd(x)
    
#     def pop(self) -> int:
#         x = self._s.get_front()
#         self._s.delete_front()
#         return x
    
#     def top(self) -> int:
#         return self._s.get_front()
    
#     def empty(self) -> bool:
#         l = len(self._s)
#         if l == 0:
#             return True
#         else:
#             return False

# ############################################################
# #  class  MyQueue
# #232. Implement Queue using Stacks

# # https://leetcode.com/problems/implement-queue-using-stacks/
# ########################################################### 
# class MyQueue:
#     def __init__(self):
#         #NOTHING CAN BE CHANGED HERE
#         self._s = Slist()
    
#     def push(self, x: int) -> None:
#         self._s.append(x)
    
#     def pop(self) -> int:
#         x = self._s.get_front()
#         self._s.delete_front()
#         return x
    
#     def peek(self) -> int:
#         return self._s.get_front()
    
#     def empty(self) -> bool:
#         l = len(self._s)
#         if l == 0:
#             return True
#         else:
#             return False

# ############################################################
# #  MyCircularQueue
# # 622. Design Circular Queue
# # https://leetcode.com/problems/design-circular-queue/
# ########################################################### 

# class MyCircularQueue:
#     def __init__(self, k: int):
#         #NOTHING CAN BE CHANGED HERE
#         self._K = k 
#         self._s = Slist()

#     def enQueue(self, value: int) -> bool:
#         if (self.isFull()):
#             return False
#         self._s.append(value)
#         return True
    
#     def deQueue(self) -> bool:
#         if (self.isEmpty()):
#             return False
#         self._s.delete_front()
#         return True
    
#     def Front(self) -> int:
#         return self._s.get_front()
    
#     def Rear(self) -> int:
#         return self._s.get_last()
    
#     def isEmpty(self) -> bool:
#         l = len(self._s)
#         if l == 0:
#             return True
#         else:
#             return False
    
#     def isFull(self) -> bool:
#         l = len(self._s)
#         if l == self._K:
#             return True
#         else:
#             return False

# ############################################################
# #  MyCircularDeque
# #641. Design Circular Deque
# #https://leetcode.com/problems/design-circular-deque

# ###########################################################  
class MyCircularDeque:
    def __init__(self, k: int):
        #NOTHING CAN BE CHANGED HERE
        self._K = k 
        self._s = Slist()

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        new_node = ListNode(value)
        if self.isEmpty():
            self._s._first = new_node
            self._s._last = new_node
        else:
            new_node.next = self._s._first
            self._s._first.prev = new_node
            self._s._first = new_node
        self._s._len += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        new_node = ListNode(value)
        if self.isEmpty():
            self._s._first = new_node
            self._s._last = new_node
        else:
            new_node.prev = self._s._last
            self._s._last.next = new_node
            self._s._last = new_node
        self._s._len += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        if self._s._len  == 1:
            self._s._first = None
            self._s._last = None
        else:
            self._s._first = self._s._first.next
            self._s._first.prev = None
        self._s._len -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        if self._s._len == 1:
            self._s._first = None
            self._s._last = None
        else:
            self._s._last = self._s._last.prev
            self._s._last.next = None
        self._s._len -= 1
        return True

    def getFront(self) -> int:
        return -1 if self.isEmpty() else self._s._first.val

    def getRear(self) -> int:
        return -1 if self.isEmpty() else self._s._last.val

    def isEmpty(self) -> bool:
        return self._s._len == 0

    def isFull(self) -> bool:
        return self._s._len == self._K

Explain

该题解使用双向链表来实现循环双端队列。通过维护队列的头节点 _first 和尾节点 _last，可以在 O(1) 的时间复杂度内完成插入、删除、获取头尾元素等操作。同时使用 _len 变量记录队列的当前长度，方便判断队列是否为空或已满。

时间复杂度: O(1)

空间复杂度: O(k)

class MyCircularDeque:
    def __init__(self, k: int):
        #初始化循环双端队列，最大容量为 k
        self._K = k 
        self._s = Slist()

    def insertFront(self, value: int) -> bool:
        #在队列头部插入元素 value
        if self.isFull():
            return False
        new_node = ListNode(value)
        if self.isEmpty():
            self._s._first = new_node
            self._s._last = new_node
        else:
            new_node.next = self._s._first
            self._s._first.prev = new_node
            self._s._first = new_node
        self._s._len += 1
        return True

    def insertLast(self, value: int) -> bool:
        #在队列尾部插入元素 value
        if self.isFull():
            return False
        new_node = ListNode(value)
        if self.isEmpty():
            self._s._first = new_node
            self._s._last = new_node
        else:
            new_node.prev = self._s._last
            self._s._last.next = new_node
            self._s._last = new_node
        self._s._len += 1
        return True

    def deleteFront(self) -> bool:
        #删除队列头部的元素
        if self.isEmpty():
            return False
        if self._s._len  == 1:
            self._s._first = None
            self._s._last = None
        else:
            self._s._first = self._s._first.next
            self._s._first.prev = None
        self._s._len -= 1
        return True

    def deleteLast(self) -> bool:
        #删除队列尾部的元素
        if self.isEmpty():
            return False
        if self._s._len == 1:
            self._s._first = None
            self._s._last = None
        else:
            self._s._last = self._s._last.prev
            self._s._last.next = None
        self._s._len -= 1
        return True

    def getFront(self) -> int:
        #获取队列头部的元素，如果队列为空则返回 -1
        return -1 if self.isEmpty() else self._s._first.val

    def getRear(self) -> int:
        #获取队列尾部的元素，如果队列为空则返回 -1
        return -1 if self.isEmpty() else self._s._last.val

    def isEmpty(self) -> bool:
        #判断队列是否为空
        return self._s._len == 0

    def isFull(self) -> bool:
        #判断队列是否已满
        return self._s._len == self._K

Explore

在题解中提供的代码里，初始化一个循环双端队列并没有显式地设置节点的前驱和后继关系来维护循环性质，因为每当新节点被加入时，它的前驱和后继指针是根据队列的当前状态动态更新的。特别是当队列为空时，新插入的第一个节点的前驱和后继都指向自身，这在代码中没有直接体现，而是通过在队列为空时将_first和_last都指向新节点来隐式实现。

在题解中，当队列长度从1变为0时，代码确实将_first和_last指针都设置为None，从而使队列为空状态。但是，没有显式地清除被删除节点的前驱和后继指针。在大多数情况下，这不会造成问题，因为Python的垃圾回收机制会处理这些孤立的节点。然而，在某些环境或长时间运行的系统中，如果这些节点的引用未被清除，可能会导致内存泄漏。

在向队列头部插入元素时，新节点的next指针指向原来的_first节点，然后更新原_first节点的prev指针指向新节点，并将_first更新为新节点。在向队列尾部插入时，新节点的prev指针指向原来的_last节点，然后更新原_last节点的next指向新节点，并将_last更新为新节点。这种方式确保了每次插入操作都正确维护了双向链表的结构，使得每个节点都正确地连接到其前驱和后继节点。

这不是一个遗漏，而是一个设计选择。在题解中使用的是非循环的双向链表。这种选择简化了实现，特别是在处理队列头部和尾部的插入和删除操作时，不需要考虑复杂的循环条件（如头尾相连）。此外，非循环链表在逻辑上更直观，易于理解和维护。使用非循环链表的主要考虑是避免循环引用带来的复杂性，尤其是在自动内存管理的语言环境下，循环引用可能需要额外的垃圾回收处理。