数据结构-队列

leetcode 622. 设计循环队列

解题重点：
1.指针下标超界问题，用if或者%将其避开

class MyCircularQueue:
	def __init__(self, k: int): 
		self.queue = [-1 for i in range(k)] 
		self.front = 0 
		self.rear = 0 
		self.length = 0 
		self.k = k
	def enQueue(self, value: int) -> bool: 
		if self.isFull():return False 
		self.queue[self.rear] = value 
		self.rear = self.rear + 1 if self.rear + 1 < self.k else 0 # (self.rear + 1 
		self.length += 1 
		return True
	
	def deQueue(self) -> bool: 
		if self.isEmpty():return False 
		self.queue[self.front] = -1 
		self.front = self.front + 1 if self.front + 1 < self.k else 0
		self.length -= 1 
		return True
	
	def Front(self) -> int: 
		return self.queue[self.front]
	
	def Rear(self) -> int: 
		return self.queue[self.rear - 1 if self.rear - 1 >= 0 else self.k - 1]
	
	def isEmpty(self) -> bool: 
		return self.length == 0
	
	def isFull(self) -> bool: 
		return self.length == self.k

leetcode 641. 设计循环双端队列

解题重点：
1.注意front和rear在删除和增加的时候下标的移动方向
2.注意初始值的设定

class MyCircularDeque:
	def __init__(self, k: int): 
		""" Initialize your data structure here. Set the size of the deque to be k. """ 
		self.arr = [-1 for _ in range(k)] 
		self.k = k 
		self.length = 0 
		self.head = 0 
		self.tail = 1
	
	def insertFront(self, value: int) -> bool: 
		""" Adds an item at the front of Deque. Return true if the operation is successful """ 
		if self.isFull():return False 
		#print(self.length) 
		self.arr[self.head] = value 
		self.head = self.head - 1 if self.head - 1 >= 0 else self.k - 1
		self.length += 1 
		return True
	
	def insertLast(self, value: int) -> bool: 
		""" Adds an item at the rear of Deque. Return true if the operation is successful. """ 
		if self.isFull(): 
			return False 
		self.arr[self.tail] = value 
		self.tail = (self.tail + 1) % self.k 
		self.length += 1 
		return True
	
	def deleteFront(self) -> bool: 
		""" Deletes an item from the front of Deque. Return true if the operation is succe """ 
		if self.isEmpty():return False 
		self.head = (self.head + 1) % self.k 
		self.arr[self.head] = -1 
		self.length -= 1 
		return True
	
	def deleteLast(self) -> bool: 
		""" Deletes an item from the rear of Deque. Return true if the operation is succes """ 
		if self.isEmpty():return 
		self.tail = self.tail - 1 if self.tail - 1 >= 0 else self.k - 1
		self.arr[self.tail] = -1 
		self.length -= 1 
		return True
	
	def getFront(self) -> int: 
		""" Get the front item from the deque."""
		# print(self.arr) 
		# print(self.head) 
		# print(self.tail) 
		return self.arr[(self.head + 1) % self.k]
	
	def getRear(self) -> int: 
		""" Get the last item from the deque. """ 
		return self.arr[self.tail - 1 if self.tail - 1 >= 0 else self.k - 1]
	def isEmpty(self) -> bool: 
		""" Checks whether the circular deque is empty or not. """ 
		return self.length == 0
	
	def isFull(self) -> bool: 
	""" Checks whether the circular deque is full or not. """ 
		return 	self.length == self.k

leetcode 1670. 设计前中后队列

解题重点：
1.前中后队列，使用双向链表加3指针方便操作，注意判断只要1、2元素队列的情况
2.如果用列表则简单至极

class Node:
	def __init__(self, val): 
		self.val = val 
		self.next = self.prev = None
	
class FrontMiddleBackQueue: 
	def __init__(self): 
		self.head = self.tail = self.mid = None 
		self.sign = False #作为链表当前奇偶判断，True为奇数，False为偶数
	
	def pushFront(self, val: int) -> None: 
		if not self.head:#判断队列为空的情况 
			self.head = self.tail = self.mid = Node(val) 
			self.sign = True 
			return
	
		self.head.prev = Node(val) 
		self.head.prev.next = self.head 
		self.head = self.head.prev #将头节点链接新节点，并将head指针移到前面 
		if self.sign: 
			self.mid = self.mid.prev 
			self.sign = False 
		else:
			self.sign = True
	
	def pushMiddle(self, val: int) -> None: 
		if not self.head:#判断队列为空的情况 
			self.head = self.tail = self.mid = Node(val) 
			self.sign = True 
			return
		node = Node(val)
	
	   if self.sign:#判断当前队列奇偶 
	   	self.sign = False#为奇数则添加元素后变为偶数 
	   	if self.mid.prev:#判断是否是单个元素的队列 
	   		self.mid.prev.next = node 
	   		node.prev = self.mid.prev 
	   		self.mid.prev = node 
	   		node.next = self.mid 
	   		self.mid = node 
	   	else:#如果是单个元素，将头和mid放最前面 
	   		self.mid.prev = node 
	   		node.next = self.mid 
	   		self.head = self.mid = node 
	   else:#偶数的情况要么0个，要么2个以上 
	   		node.next = self.mid.next 
	   		self.mid.next = node.next.prev = node 
	   		node.prev = self.mid self.mid = node 
	   		self.sign = True
	
	def pushBack(self, val: int) -> None: 
		if not self.head:#判断队列为空的情况 
			self.head = self.tail = self.mid = Node(val) 
			self.sign = True 
			return 
		self.tail.next = Node(val) 
		self.tail.next.prev = self.tail 
		self.tail = self.tail.next 
		if self.sign: 
			self.sign = False 
		else:
			self.mid = self.mid.next 
			self.sign = True
	
	def popFront(self) -> int: 
		if not self.head:#判断队列为空的情况 
			return -1 
		res = self.head.val 
		self.head = self.head.next 
		if not self.head: 
			self.mid = self.tail = None 
			self.sign = False 
			return res 
		
		self.head.prev = None 
		if self.sign: 
			self.sign = False 
		else:
			self.mid = self.mid.next 
			self.sign = True 
		return res
	
	def popMiddle(self) -> int: 
		if not self.head:#判断队列为空的情况 
			return -1
		res = self.mid.val
		if not self.head.next:#表示只有一个元素的队列情况 
			self.head = self.mid = self.tail = None 
			self.sign = False 
			return res
		
		if not self.mid.prev:#表示只有两个元素的情况下 
			self.head = self.mid = self.tail = self.mid.next
			self.head.prev = None 
			self.sign = True 
			return res
		
		self.mid.prev.next = self.mid.next 
		self.mid.next.prev = self.mid.prev
		if self.sign: 
			self.mid = self.mid.prev 
			self.sign = False 
		else:
			self.mid = self.mid.next 
			self.sign = True 
		return res
	
	def popBack(self) -> int: 
		if not self.head:#判断队列为空的情况 
			return -1 
		res = self.tail.val 
		self.tail = self.tail.prev 
		if not self.tail:#表示删除前只有一个元素的情况下 
			self.mid = self.head = None 
			self.sign = False 
			return res 
		
		self.tail.next = None 
		if self.sign: 
			self.mid = self.mid.prev 
			self.sign = False 
		else:
			self.sign = True 
		return res