從棧中搜索

我正在實現一個堆棧，雖然實現基本操作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

回答

相關問題