python学习笔记(15)算法(8)双向队列

embedded/2024/11/29 9:48:42/

在队列中,我们仅能删除头部元素或在尾部添加元素。双向队列(double‑ended queue)提供了更高的灵活性,允许在头部和尾部执行元素的添加或删除操作。

一、双向队列常用操作

  1. 队首入队(push_front):在双向队列的头部添加一个元素。
  2. 队首出队(pop_front):删除双向队列头部的元素。
  3. 队尾入队(push_back):在双向队列的尾部添加一个元素。
  4. 队尾出队(pop_back):删除双向队列尾部的元素。
  5. 访问队首元素(peek_front):获取双向队列头部的元素,但不删除它。
  6. 访问队尾元素(peek_back):获取双向队列尾部的元素,但不删除它。
  7. 获取队列长度(size):返回双向队列中元素的个数。
  8. 判断队列是否为空(isEmpty):如果双向队列为空,则返回true,否则返回false。
from collections import deque
# 初始化双向队列
deque: deque[int] = deque()# 元素入队
deque.append(2)
# 添加至队尾
deque.append(5)
deque.append(4)
deque.appendleft(3)
# 添加至队首
deque.appendleft(1)
# 访问元素
front: int = deque[0]
# 队首元素
rear: int = deque[-1]
# 队尾元素
# 元素出队
pop_front: int = deque.popleft()
# 队首元素出队
pop_rear: int = deque.pop()
# 队尾元素出队
# 获取双向队列的长度
size: int = len(deque)
# 判断双向队列是否为空
is_empty: bool = len(deque) == 0

二、双向队列实现 *

1.基于双向链表的实现

回顾上一节内容,我们使用普通单向链表来实现队列,因为它可以方便地删除头节点(对应出队操作)和在尾节点后添加新节点(对应入队操作)。
对于双向队列而言,头部和尾部都可以执行入队和出队操作。换句话说,双向队列需要实现另一个对称方向的操作。为此,我们采用“双向链表”作为双向队列的底层数据结构。

将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除节点的功能。

# 双向链表节点定义
class DListNode:def __init__(self, val=0, prev=None, next=None):self.val = valself.prev = prevself.next = next# 双向队列类定义
class LinkedListDeque:def __init__(self):self.front = Noneself.rear = Noneself.size = 0def push(self, val, is_front=True):new_node = DListNode(val)if self.size == 0:self.front = self.rear = new_nodeelif is_front:new_node.next = self.frontself.front.prev = new_nodeself.front = new_nodeelse:new_node.prev = self.rearself.rear.next = new_nodeself.rear = new_nodeself.size += 1def pop(self, is_front=True):if self.size == 0:raise IndexError("双向队列为空")if self.size == 1:val = self.front.valself.front = self.rear = Noneelif is_front:val = self.front.valself.front = self.front.nextself.front.prev = Noneelse:val = self.rear.valself.rear = self.rear.prevself.rear.next = Noneself.size -= 1return valdef peek_front(self):if self.size == 0:raise IndexError("双向队列为空")return self.front.valdef peek_back(self):if self.size == 0:raise IndexError("双向队列为空")return self.rear.valdef size(self):return self.sizedef is_empty(self):return self.size == 0# 示例代码
if __name__ == "__main__":deque = LinkedListDeque()deque.push(1)deque.push(2, is_front=False)print(deque.peek_front())print(deque.peek_back())print(deque.pop())print(deque.pop(is_front=False))

2.基于数组的实现

class ArrayDeque:def __init__(self, capacity):self.capacity = capacityself.array = [None] * capacityself.front = 0self.rear = 0self.size = 0def is_full(self):return self.size == self.capacitydef is_empty(self):return self.size == 0def push_front(self, item):if self.is_full():raise IndexError("队列已满")self.front = (self.front - 1 + self.capacity) % self.capacityself.array[self.front] = itemself.size += 1def push_back(self, item):if self.is_full():raise IndexError("队列已满")self.array[self.rear] = itemself.rear = (self.rear + 1) % self.capacityself.size += 1def pop_front(self):if self.is_empty():raise IndexError("队列已空")item = self.array[self.front]self.front = (self.front + 1) % self.capacityself.size -= 1return itemdef pop_back(self):if self.is_empty():raise IndexError("队列已空")self.rear = (self.rear - 1 + self.capacity) % self.capacityitem = self.array[self.rear]self.size -= 1return itemdef peek_front(self):if self.is_empty():raise IndexError("队列已空")return self.array[self.front]def peek_back(self):if self.is_empty():raise IndexError("队列已空")return self.array[self.rear - 1 + self.capacity] % self.capacitydef get_size(self):return self.size


http://www.ppmy.cn/embedded/141431.html

相关文章

flink学习(6)——自定义source和kafka

概述 SourceFunction:非并行数据源(并行度只能1) --接口 RichSourceFunction:多功能非并行数据源(并行度只能1) --类 ParallelSourceFunction:并行数据源(并行度能够>1) --接口 RichParallelSourceFunction:多功能并行数据源(并行度能够>1) --类 【建议使用的】 ——…

数据结构 ——— 快速排序算法的实现(挖坑法版本)

目录 前言 快速排序算法(挖坑版本)的思想 单躺排序逻辑的实现 快速排序算法的实现(挖坑法) 前言 在上一章学习了 hoaer 版本的快速排序算法的实现数据结构 ——— 快速排序算法的实现(hoare版本)-CSDN…

SQL面试题——in和not in 不支持怎么办

in和not in 不支持怎么办 这是来自读者群的一位同学的问题,说是别人问他in和not in 不支持怎么办,现在我们来看一下这个问题 in 不支持 其实很多朋友都能写出这样的SQL,其实这个SQL 在没有底层优化的时候还是很可怕的 SELECT a.key, a.value FROM a WHERE a.key in (SEL…

LeetCode题练习与总结:替换后的最长重复字符--424

一、题目描述 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回 包含相同字母的最长子字符串的长度。 示例 1: 输入:s &quo…

什么是 Token 和 MD5 ?

目录 一:Token和MD5分别是什么 1:Token 2:MD5 二:简易Token的实现 1:Base64。 2:验证Token 三:MD5的使用 一:Token和MD5分别是什么 1:Token Token 的中文有人翻译成…

nvm 常用命令

nvm 常用命令 参考1 参考2 nvm list available 查看nodejs有哪些版本 npm install 10.13.0 下载10.13.0版本 nvm use 10.13.0 切换到10.13.0版本 nvu list 查看已安装版本

迁移学习和无监督学习是什么

迁移学习和无监督学习都是机器学习中的重要方法,它们在湍流速度场超分辨率重建任务中有着独特的作用。让我们通过简单的语言和例子来解释它们如何帮助解决这个问题。 1. 迁移学习: 迁移学习是一种方法,它利用一个领域(例如某种类…

R语言处理JSON文件

R语言处理JSON文件 引言 JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。它基于JavaScript编程语言的一个子集,但JSON是独立于语言的文本格式&#xff0c…