目录Python全系列 教程
3567个小节阅读：5931.2k
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
双向队列 ，就是在队列的基础上增加一个双端操作的功能。允许在头部和尾部执行元素的添加或删除操作
| 方法名 | 描述 | 时间复杂度 |
|---|---|---|
| push_first( ) | 将元素添加至队首 | $O(1)$ |
| push_last( ) | 将元素添加至队尾 | $O(1)$ |
| pop_first( ) | 删除队首元素 | $O(1)$ |
| pop_last( ) | 删除队尾元素 | $O(1)$ |
| peek_first( ) | 访问队首元素 | $O(1)$ |
| peek_last( ) | 访问队尾元素 | $O(1)$ |
提示
python中有现成的队列类collections .deque，在此只是为了模拟底层实现
xxxxxxxxxxclass ArrayDeque: def __init__(self,capacity:int=8): self._data = [0] * capacity # 存储数据的数组 self._head = 0 # 队头元素的下标 self._size = 0 # 队列中元素的个数 def capacity(self): '''返回队列的容量''' return len(self._data) def is_empty(self) -> bool: '''判断队列是否为空''' return self._size == 0 def index(self,i:int) -> int: '''获取指定正确的索引''' return (i+self.capacity())%self.capacity() def peek_first(self) -> int: '''查看队头元素''' if self.is_empty(): raise Exception("Deque is empty") return self._data[self._head] def peek_last(self) -> int: '''查看队尾元素''' if self.is_empty(): raise Exception("Deque is empty") # 获取队尾元素的下标 i = self.index(self._head + self._size - 1) return self._data[i] def push_last(self,val:int): '''增加队尾元素''' # 判断队列是否已满 if self._size == self.capacity(): raise Exception("Deque is full") # 获取队尾元素的下标 i = self.index(self._head + self._size) # 将元素添加到队尾 self._data[i] = val # 队列中元素的个数加1 self._size += 1 def push_first(self,val:int): '''增加队头元素''' # 判断队列是否已满 if self._size == self.capacity(): raise Exception("Deque is full") # 获取队头元素的下标 i = self.index(self._head - 1) # 将元素添加到队头 self._data[i] = val # 队列中元素的个数加1 self._size += 1 # 修改队头元素的下标 self._head = i def pop_first(self) -> int: '''删除队头元素''' if self.is_empty(): raise Exception("Deque is empty") # 获取队头元素的值 val = self.peek_first() # 修改队头元素的下标 self._head = self.index(self._head + 1) # 队列中元素的个数减1 self._size -= 1 return val def pop_last(self) -> int: '''删除队尾元素''' if self.is_empty(): raise Exception("Deque is empty") # 获取队尾元素的值 val = self.peek_last() # 队列中元素的个数减1 self._size -= 1 return val
def to_list(self): '''转换为列表''' res = [] for i in range(self._size): tmp_index = self.index(self._head + i) res.append(self._data[tmp_index]) return res
if __name__ == "__main__": deque = ArrayDeque(5) deque.push_last(1) deque.push_last(2) deque.push_last(3) deque.push_last(4) deque.push_last(5) print(deque.to_list()) # [1,2,3,4,5] deque.pop_first() # 1 deque.push_last(6) # [2,3,4,5,6] print(deque.to_list()) # [2,3,4,5,6] print(f'队尾拿到数据:{deque.pop_last()}') # 6 deque.push_first(7) # [7,2,3,4,5] print(deque.to_list()) # [7,2,3,4,5]xxxxxxxxxxclass ListNode: def __init__(self, x): self.val = x # 节点值 self.next = None # 后继节点 self.prev = None # 前驱节点
class LinkedDeque: def __init__(self): self.head = None # 头指针 self.tail = None # 尾指针 self.size = 0 # 队列长度 def is_empty(self) -> bool: '''判断队列是否为空''' return self.size == 0 def peek_first(self) -> int: '''查看队首元素''' if self.is_empty(): raise Exception('Deque is empty') return self.head.val def peek_last(self) -> int: '''查看队尾元素''' if self.is_empty(): raise Exception('Deque is empty') return self.tail.val
def push(self,val:int,flag:bool): # 创建新节点 node = ListNode(val) # 判断当前队列是否为空 if self.is_empty(): self.head = node self.tail = node elif flag == True: '''队首增加元素''' # 原队首节点的前驱节点指向新节点 self.head.prev = node # 新节点的后继节点指向原队首节点 node.next = self.head # 新节点成为新的队首节点 self.head = node else: '''队尾增加元素''' # 原队尾节点的后继节点指向新节点 self.tail.next = node # 新节点的前驱节点指向原队尾节点 node.prev = self.tail # 新节点成为新的队尾节点 self.tail = node # 队列长度加1 self.size += 1 def push_first(self,val:int): '''队首增加元素''' self.push(val,True) def push_last(self,val:int): '''队尾增加元素''' self.push(val,False)
def pop(self,flag:bool) -> int: if self.is_empty(): raise Exception('Deque is empty') if flag == True: '''队首删除元素''' # 获取队首节点的值 val = self.peek_first() # 获取队首节点的后继节点 next_node = self.head.next # 判断队首节点的后继节点是否为空 if next_node: # 队首节点的后继节点的前驱节点指向空 next_node.prev = None # 原队首节点的后继节点指向空 self.head.next = None # 队首节点的后继节点成为新的队首节点 self.head = next_node else: '''队尾删除元素''' # 获取队尾节点的值 val = self.peek_last() # 获取队尾节点的前驱节点 prev_node = self.tail.prev # 判断队尾节点的前驱节点是否为空 if prev_node: # 队尾节点的前驱节点的后继节点指向空 prev_node.next = None # 原队尾节点的前驱节点指向空 self.tail.prev = None # 队尾节点的前驱节点成为新的队尾节点 self.tail = prev_node # 队列长度减1 self.size -= 1 return val def pop_first(self) -> int: '''队首删除元素''' return self.pop(True) def pop_last(self) -> int: '''队尾删除元素''' return self.pop(False) def to_list(self): '''将队列转换为列表''' # 创建列表 res = [] # 获取队首节点 cur = self.head # 遍历队列 while cur: # 将节点值添加到列表中 res.append(cur.val) # 获取当前节点的后继节点 cur = cur.next return res
if __name__ =='__main__': deque = LinkedDeque() deque.push_last(1) deque.push_last(2) deque.push_last(3) deque.push_last(4) deque.push_last(5) print(deque.to_list()) print(f'获取队首元素:{deque.pop_first()}') print(f'获取队尾元素:{deque.pop_last()}') print(deque.to_list()) deque.push_first(6) deque.push_last(7) print(deque.to_list())