队列优化：双端队列与优先队列在LeetCode中的应用
在数据结构与算法的学习过程中，队列是一种非常基础且常用的数据结构。它遵循“先进先出”（FIFO）的原则，即最先进入队列的元素最先被取出。在某些特定的场景下，标准的队列可能无法满足我们的需求。为了应对这些挑战，我们可以使用双端队列和优先队列这两种优化后的队列结构。本文将围绕这两种队列在LeetCode平台上的应用进行探讨。
双端队列
定义
双端队列（Deque，Double-ended queue）是一种支持在两端进行插入和删除操作的数据结构。它既可以像队列一样从一端插入元素，从另一端删除元素，也可以像栈一样从两端进行操作。
实现方式
在Python中，可以使用列表来实现双端队列。以下是使用列表实现双端队列的基本操作：
python
class Deque:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if not self.is_empty():
return self.items.pop(0)
return None
def remove_rear(self):
if not self.is_empty():
return self.items.pop()
return None
def size(self):
return len(self.items)
LeetCode应用
在LeetCode中，双端队列常用于解决一些需要从两端进行操作的问题。以下是一些使用双端队列解决LeetCode问题的例子：
1. 题目：232. 用栈实现队列（Implement Queue using Stacks）
- 题目描述：使用两个栈实现一个队列，支持队列的基本操作（入队、出队、队首元素）。
- 解题思路：使用一个栈来存储入队元素，另一个栈来存储出队元素。当出队栈为空时，将入队栈的所有元素逆序转移到出队栈中。
- 代码实现：
python
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int) -> None:
self.in_stack.append(x)
def pop(self) -> int:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack.pop()
def peek(self) -> int:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stack
2. 题目：641. 设计循环双端队列（Design Circular Deque）
- 题目描述：设计一个循环双端队列，支持在队列的两端进行插入和删除操作。
- 解题思路：使用一个固定大小的数组来实现循环双端队列，通过维护两个指针来表示队列的头部和尾部。
- 代码实现：
python
class MyCircularDeque:
def __init__(self, k: int):
self.capacity = k
self.queue = [0] k
self.head = 0
self.tail = 0
self.size = 0
def insertFront(self, value: int) -> bool:
if self.size == self.capacity:
return False
self.head = (self.head - 1 + self.capacity) % self.capacity
self.queue[self.head] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
if self.size == self.capacity:
return False
self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1
return True
def deleteFront(self) -> bool:
if self.size == 0:
return False
self.head = (self.head + 1) % self.capacity
self.size -= 1
return True
def deleteLast(self) -> bool:
if self.size == 0:
return False
self.tail = (self.tail - 1 + self.capacity) % self.capacity
self.size -= 1
return True
def getFront(self) -> int:
if self.size == 0:
return -1
return self.queue[self.head]
def getRear(self) -> int:
if self.size == 0:
return -1
return self.queue[(self.tail - 1 + self.capacity) % self.capacity]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
优先队列
定义
优先队列（Priority Queue）是一种特殊的队列，它根据元素的优先级对元素进行排序。在优先队列中，具有最高优先级的元素最先被取出。
实现方式
在Python中，可以使用内置的`heapq`模块来实现优先队列。`heapq`模块提供了一个最小堆的实现，可以通过调整元素顺序来实现优先队列的功能。
以下是使用`heapq`模块实现优先队列的基本操作：
python
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def is_empty(self):
return len(self.heap) == 0
def push(self, item, priority):
heapq.heappush(self.heap, (-priority, item))
def pop(self):
if not self.is_empty():
return heapq.heappop(self.heap)[1]
return None
def size(self):
return len(self.heap)
LeetCode应用
在LeetCode中，优先队列常用于解决需要根据元素优先级进行操作的问题。以下是一些使用优先队列解决LeetCode问题的例子：
1. 题目：347. 前 K 个高频元素（Top K Frequent Elements）
- 题目描述：给定一个非空整数数组，返回其中出现频率最高的k个元素。
- 解题思路：使用哈希表统计每个元素的频率，然后使用优先队列存储频率最高的k个元素。
- 代码实现：
python
import collections
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counter = collections.Counter(nums)
heap = []
for num, freq in counter.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for _, num in sorted(heap, reverse=True)]
2. 题目：23. 合并K个排序链表（Merge k Sorted Lists）
- 题目描述：合并k个已排序的链表。
- 解题思路：使用优先队列存储每个链表的头部元素，并按照元素值进行排序。每次从优先队列中取出最小元素，将其添加到结果链表中，并更新优先队列。
- 代码实现：
python
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
dummy = ListNode()
current = dummy
heap = []
for node in lists:
if node:
heapq.heappush(heap, (node.val, node))
while heap:
_, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, node.next))
return dummy.next
总结
本文介绍了双端队列和优先队列这两种优化后的队列结构，并探讨了它们在LeetCode平台上的应用。通过学习这些数据结构，我们可以更好地解决一些具有挑战性的问题。在实际应用中，选择合适的数据结构对于提高算法效率至关重要。希望本文能对您有所帮助。
Comments NOTHING