algorithm - 使用高效的 `has` 操作实现堆栈
问题描述
我需要一个具有 3 个操作的数据结构:1. push
, 2. pop
3. has
. 它就像一个具有类似集合元素查找的堆栈。如果堆栈包含参数,则该has
操作应返回 true。我需要has
快速操作,如何实现?
例子:
- 推(1),推(2),推(1),弹出()。// 期望 has(1) 为真。
解决方案
好吧,你可以提出一个论点,如果你需要一个has/contains
方法,它可能不应该是一个堆栈。但是,如果我需要这样的功能(并且它是一种面向对象的语言),我将简单地从实际堆栈继承,然后拦截push
andpop
调用以维护另一个备用集合(例如,排序的可调整大小的向量或排序的列表,或计数集,其他合适的)。
每次推送某些内容时,我也会将其添加到备用集合中。弹出后,它也会从备用集合中删除。
然后你的push
andpop
操作变得(希望只是)稍微慢一点,并且你的has
方法使用备用集合,这可能比基本堆栈快很多(使用检查堆栈中每个元素的方法来查看项目是否在那里) )。
是的,您可能有重复的数据,但优化通常是空间/时间的权衡。在任何情况下,您都可以通过在备用集合中使用(引用)堆栈项中的指针来避免任何实际影响。
由于您没有指定一种语言,而且 Python 是最终的伪代码 :-),这就是我将如何使用该语言来处理它。首先是一个基本的堆栈类,除了push/pop
:
class Stack:
def __init__(self):
self.stack = [] # Empty list to start.
def push(self, item):
self.stack.append(item) # Add to list end.
def pop(self):
item = self.stack[-1] # Get list end,
self.stack = self.stack[:-1] # shorten list by one,
return item # and return it.
继承自它的类调用每个项目的基类,但还维护一个字典(关联数组),它将项目映射到一个计数(实际上是一个计数集)。
class AltStack(Stack):
def __init__(self):
super().__init__() # Defer to base but
self.alternate = {} # also create alternate.
def push(self, item):
super().push(item) # Defer to base but
try: # also increment in
self.alternate[item] += 1 # alternate, creating if
except KeyError: # not yet set.
self.alternate[item] = 1
def pop(self):
item = super().pop() # Defer to base. Then
if self.alternate[item] == 1: # decrement in alternate,
del self.alternate[item] # deleting item from
else: # alternate when count
self.alternate[item] -= 1 # reaches zero.
return item
def has(self, item):
return item in self.alternate # Use alternate for "has".
那么您所需要的只是最简单的测试工具:
my_stack = AltStack()
# Push 0, two each of 1-6, and 7.
for i in range(7):
my_stack.push(i)
my_stack.push(i+1)
# Pop each, displaying both it and whether stack has specific item.
for i in range(14):
print("Popping", my_stack.pop(), "has(4)? =", my_stack.has(4))
从(带注释的)输出中可以看出,这可以按预期工作:
Popping 7 has(4)? = True <-- 4 was pushed twice, has(4) true.
Popping 6 has(4)? = True
Popping 6 has(4)? = True
Popping 5 has(4)? = True
Popping 5 has(4)? = True
Popping 4 has(4)? = True <-- first 4 popped, has(4) still true.
Popping 4 has(4)? = False <-- final 4 popped, has(4) now false.
Popping 3 has(4)? = False
Popping 3 has(4)? = False
Popping 2 has(4)? = False
Popping 2 has(4)? = False
Popping 1 has(4)? = False
Popping 1 has(4)? = False
Popping 0 has(4)? = False <-- and stay false forever.
请记住,这是一个示例,展示了如何将其作为一个概念来完成。我不判断字典是否比列表更有效,尽管我怀疑它们适用于中型到大型结构。所以在你开始对我做事的方式提出问题之前,试着记住这个概念的本质。
推荐阅读
- xcode - 文档中的 AppCode 链接导航到代码库中的另一个类型/成员
- discord - 如何正确上传过长的消息作为文件?
- python - pandas - 按列分组并获取另一个带空值的字符串列的最大长度
- xunit - xunit忽略测试但可以强制运行
- javascript - D3js,动态改变X轴的域
- javascript - 使用 https.get 获取 URL 响应代码并将其存储在变量中
- tailwind-css - 在像素顺风中设置最小高度
- python - Pandas - 删除重复的列名,但将其唯一的行值附加到现有列
- javascript - 引导模式加载具有特定元素的远程内容
- spring-boot - Spring Boot 导出 Excel XSSFSheet 添加标题不起作用