如何計算特定項目從堆棧中彈出的次數？

Question

我有一堆元素必須從中移除一個隨機元素（即，頂部和那個特定元素之間的所有元素將被彈出並再次被推送）。每當一個元素被彈出時，我們必須確定其它元素的彈出次數。

我很久以前就已經開始這個了。 （堆棧是動態的（即元素不時被添加和刪除））。

Answer 1

我會在堆棧存儲爲一個單鏈接列表，並在每個節點中保留一個整數以表示它被訪問的次數。即，5底部頂部，7堆棧並沒有做出看起來像訪問：

| 5 | -> | 2 | -> | 3 | -> | 1 | -> | 7 | 
| 0 | -> | 0 | -> | 0 | -> | 0 | -> | 0 | 

然後，你可以寫自己的流行音樂（O（N）），它只是通過鏈接列表中添加1迭代訪問它訪問的每個節點的計數（如果你可以假設你彈出的東西總是在堆棧中，那麼你只需要遍歷它一次，如果不是，你可能需要迭代兩次），pop（3）： //返回0

| 5 | -> | 2 | -> | 1 | -> | 7 | 
| 1 | -> | 1 | -> | 0 | -> | 0 | 

POP（7）：//返回0

| 5 | -> | 2 | -> | 1 | 
| 2 | -> | 2 | -> | 1 | 

POP（2）：//返回2

| 5 | -> | 1 | 
| 3 | -> | 1 | 

推（6）：

| 6 | -> | 5 | -> | 1 | 
| 0 | -> | 3 | -> | 1 | 

POP（1）：//返回1

| 6 | -> | 5 | 
| 1 | -> | 4 | 

彈出（6 ）：//返回1

| 5 | 
| 4 | 

流行（5）：//返回4

Answer 2

如果我正確理解你，你有自己的堆棧結構，並且你想要計算特定元素的推動和彈出。如果是這樣的話，你可以在一個struct包裝你的數據，並在堆棧商店列表（無論內部執行堆棧的是）這個struct：

struct stack_data { 
    unsigned push_count; 
    unsigned pop_count; 
    void *data; /* or whatever type the data is */ 
}; 

... 

void stack_push(/* stack argument */, struct stack_data *data) 
{ 
    ... 
    data->push_count++; 
} 

void stack_pop(/* stack argument */, struct stack_data *data) 
{ 
    ... 
    data->pop_count++; 
}