1670、设计前中后队列
题目：
请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。
请你完成 FrontMiddleBack 类：
- FrontMiddleBack() 初始化队列。
- void pushFront(int val) 将 val 添加到队列的 最前面 。
- void pushMiddle(int val) 将 val 添加到队列的 正中间 。
- void pushBack(int val) 将 val 添加到队里的 最后面 。
- int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
- int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
- int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：
将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。
思路：
由于可以从前中后读取插入数据，这个时候可以用数组来实现
解法1：
class FrontMiddleBackQueue:
def __init__(self):
self.queue = []
def pushFront(self, val: int) -> None:
self.queue.insert(0, val)
def pushMiddle(self, val: int) -> None:
n = len(self.queue)
self.queue.insert(n // 2, val)
def pushBack(self, val: int) -> None:
self.queue.append(val)
def popFront(self) -> int:
if len(self.queue) == 0:return -1
return self.queue.pop(0)
def popMiddle(self) -> int:
n = len(self.queue)
if not n: return -1
return self.queue.pop((n-1) // 2)
def popBack(self) -> int:
if len(self.queue) == 0:return -1
return self.queue.pop()
解法2：
尝试挑战一下，用双端队列实现
class DoubleLinkedNode:
def __init__(self, val=0, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
def __str__(self):
arr, cur = [], self
while cur:
arr.append(cur.val)
cur = cur.next
return arr.__str__()
# 双端队列主要需要考虑链表中间的位置
class FrontMiddleBackQueue:
def __init__(self):
self.head = DoubleLinkedNode()
self.tail = DoubleLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.count = 0
self.middle = None
def pushFront(self, val: int) -> None:
newNode = DoubleLinkedNode(val, next=self.head.next, prev=self.head)
self.head.next.prev = newNode
self.head.next = newNode
self.count += 1
# 如果当前队列只有一个元素，那么中间位置就是这个元素，
# 如果是偶数，那么原来的链表是奇数的，而插入的元素是在左侧这个时候中间位置左移一位即可
# 如果是奇数，中间位置没有发生变化
if self.count == 1:
self.middle = newNode
elif self.count % 2 == 0:
self.middle = self.middle.prev
def pushMiddle(self, val: int) -> None:
if self.count == 0: return self.pushFront(val)
newNode = DoubleLinkedNode(val)
# 这里需要考虑当前链表是奇数还是偶数，奇数的话，需要在中间结点左侧插入，偶数在中间节点右侧插入
# 最后中间节点要变更为插入结点的位置
if self.count % 2 == 0:
newNode.next = self.middle.next
newNode.prev = self.middle
self.middle.next.prev = newNode
self.middle.next = newNode
self.middle = newNode
else:
newNode.next = self.middle
newNode.prev = self.middle.prev
self.middle.prev.next = newNode
self.middle.prev = newNode
self.middle = newNode
self.count += 1
def pushBack(self, val: int) -> None:
newNode = DoubleLinkedNode(val, next=self.tail, prev=self.tail.prev)
self.tail.prev.next = newNode
self.tail.prev = newNode
self.count += 1
# 如果当前只有一个元素，那么中间元素就是这个元素
# 如果是奇数的话，那么未插入之前是偶数，由于插入的元素是在后方，所以中间结点向后移动一位
# 如果是偶数，不需要移动
if self.count == 1:
self.middle = newNode
elif self.count % 2:
self.middle = self.middle.next
def popFront(self) -> int:
if self.count == 0: return -1
head = self.head.next
head.next.prev = self.head
self.head.next = head.next
self.count -= 1
# 如果pop出去后变为奇数，由于从队首pop的，所以此时中间节点需要后移
if self.count % 2:
self.middle = self.middle.next
return head.val
def popMiddle(self) -> int:
if self.count == 0: return -1
prev = self.middle.prev
next = self.middle.next
prev.next = next
next.prev = prev
self.count -= 1
val = self.middle.val
# 从中间pop元素，这个时候如果元素由偶数变为奇数，那么需要设置为中间结点的下个结点
# 否则设置为前置结点
if self.count % 2:
self.middle = next
else:
self.middle = prev
return val
def popBack(self) -> int:
if self.count == 0: return -1
tail = self.tail.prev
tail.prev.next = self.tail
self.tail.prev = tail.prev
self.count -= 1
# 如果为偶数，就说明是从奇数变更为偶数，此时中间节点需要像前移动一位
if self.count % 2 == 0:
self.middle = self.middle.prev
return tail.val
网友评论