Python中是否存在支持O(1)复杂度的任意位置弹出、队首弹出及队尾压入的数据结构？

Python标准库中没有直接提供同时支持以下O(1)操作的现成数据结构，但可以通过**双向链表+哈希表（字典）**的组合手动实现，完全符合你的需求：

• 队尾压入（push_back）
• 队首移除（pop_front）
• 按对象任意位置弹出（pop(item)）

实现原理 #

这个结构的核心逻辑和你提到的C语言双向链表+哈希表方案一致：

• 双向链表：维护元素的顺序，支持O(1)时间的队首移除、队尾添加，以及已知节点时的任意位置移除。
• 哈希表（Python dict）：存储元素到对应链表节点的映射，支持平均O(1)时间的元素查找，为任意位置弹出提供快速定位能力。

具体操作逻辑 #

• push_back(item)：创建新链表节点并添加到链表尾部，同时在字典中记录元素与节点的映射，两步均为O(1)。
• pop_front()：取出链表头节点的元素，移除头节点并删除字典中对应映射，全部操作O(1)。
• pop(item)：通过字典快速找到元素对应的链表节点，从链表中移除该节点并删除字典映射，平均时间复杂度O(1)。

Python实现示例 #

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class OrderedHashSet:
    def __init__(self):
        self.head = None
        self.tail = None
        self.node_map = {}
    
    def push_back(self, item):
        # 若元素已存在，先移除再移到尾部（可选逻辑，按需调整）
        if item in self.node_map:
            self.pop(item)
        new_node = Node(item)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.node_map[item] = new_node
    
    def pop_front(self):
        if not self.head:
            raise IndexError("无法从空结构中执行pop_front操作")
        node = self.head
        # 处理只剩一个节点的情况
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        del self.node_map[node.value]
        return node.value
    
    def pop(self, item):
        if item not in self.node_map:
            raise KeyError(f"元素 {item} 不存在")
        node = self.node_map[item]
        # 调整前驱节点的指针
        if node.prev:
            node.prev.next = node.next
        else:
            # 当前节点是头节点
            self.head = node.next
        # 调整后继节点的指针
        if node.next:
            node.next.prev = node.prev
        else:
            # 当前节点是尾节点
            self.tail = node.prev
        del self.node_map[item]
        return item

复杂度验证 #

• push_back：链表操作O(1)，字典插入平均O(1)
• pop_front：链表操作O(1)，字典删除平均O(1)
• pop(item)：字典查找平均O(1)，链表移除O(1)，字典删除平均O(1)

内容的提问来源于stack exchange，提问作者yellowcard123