从栈中搜索

我正在实现一个堆栈，虽然实现基本操作push和pop是一件容易的事，但我不知道如何实现有效的搜索。底层结构是一个链表从栈中搜索

2010-02-13 Masse

+11

堆栈不支持搜索 - 如果您需要搜索，堆栈是使用错误的数据结构。 – 2010-02-13 14:47:20

@Neil：但是，如果OP *需要堆栈，即LIFO语义怎么办？我不认为他在问STL堆栈，Boost堆栈或其他任何类型的“标准”堆栈实现。他说他正在“实施”这个堆栈。显然，可以实现实现同时有效地搜索*和* LIFO语义。它只需要一个额外的数据结构（红黑树或散列表）分层堆栈结构的顶部。 – 2010-02-13 16:33:02

好搜索并不是恰当的词，而是我需要知道一个项目是否在堆栈 – Masse 2010-02-13 17:06:52

在其基本形式中，堆栈只允许缓慢的线性搜索。也就是说，如果堆栈有n个元素，则需要搜索所有n（平均1/2 n）来查找匹配项。如果你的堆栈比较小，那么这个线性（逐个）搜索可能并不重要。但是，如果您有更大的集合，则可以将两个数据结构组合在一起以提高搜索效率：例如，除了之外，您还可以使用散列表：每次推入堆栈中的某些东西，也可以将它添加到散列表中。相反，当你将它从堆栈中移出时，可以将它从桌面上移除。哈希表允许相对快速的查找，即使是非常大的数据集也是如此 - 因此，您的搜索可能会非常快。

我提出的解决方案的一个问题是如何正确处理重复的项目：堆栈可以容纳dups，但散列表通常不会。因此，您可能需要在哈希表中实现一些简单的引用计数：每次弹出时，减少哈希表中的计数 - 当计数降至零时，可以将其从哈希中删除。

另一个类似的可能性是使用“多图” - 这与散列表类似，但可以更容易地处理重复项。

来源

2010-02-13 14:53:52

谢谢，我认为这正是我正在寻找的，因为我只需要知道某些数据是否在堆栈中。 – Masse 2010-02-13 17:08:23

当我重新思考我的算法时，我意识到，我甚至不需要这些信息，所以整个问题都是无关紧要的。但是，谢谢你的答案;更多的是实现某种形式的hashmap的原因。（我对C没有经验，但一直在练习，我喜欢这些练习:)） – Masse 2010-02-13 17:16:03

，如果你实现了一个持久的堆栈（push和pop返回新栈，而参数堆栈继续存在）或可变的堆栈（堆栈传递到push和pop就地进行修改）你没有提到。

在任何情况下，最深的值是那些变化最小的值，所以加速搜索的策略是将缓存先前搜索的结果缓存到最深的2,4,8 ...元素你处理的堆栈。如果您实现了可变堆栈，请将缓存视为合适的无效（当堆栈深度低于2^n时，将前2^n个元素的缓存条目无效）。

来源

2010-02-13 14:54:14

堆栈的设计不是“可搜索的”。当然，您可以轻松地在底层链表上实现搜索并将其展示给用户 - 但它不再是堆栈了。

链表

线性时间搜索看起来是这样的：

listentry* first; 

for(first = head; (first=first->next);) { 
    if (first->val == value_to_search) { 
    // have a match 
    return 1; 
    } 
} 
return 0;

的“合法”的方式来搜索一个堆栈是“流行（），直到您要搜索的价值是在顶部堆栈'。如果您之后需要堆叠，请不要这样做。

来源

2010-02-13 14:55:58

如果您需要检查堆栈中除顶部项目以外的任何项目，则可能不应使用堆栈来包含项目。重新考虑你的数据结构的选择。

来源

2010-02-13 15:24:06 sizzzzlerz

回答

相关问题