如何计算特定项目从堆栈中弹出的次数？

Question

我有一堆元素，必须从中删除一个随机元素（即顶部和该特定元素之间的所有元素将被弹出并再次推送）。每次弹出一个元素时，我们都必须确定其他元素之前已弹出该元素的次数。

我已经关注这个问题很久了。 （堆栈是动态的（即不时添加和删除元素））。

Answer 1

如果我理解正确，那么您有自己的堆栈结构，并且想要计算特定元素的推送和弹出次数。如果是这种情况，您可以将数据包装在 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++;
}

Answer 2

我将堆栈存储为单链表，并在每个节点中保留一个整数来表示它被访问的次数。 IE 中，顶部有 5 个、底部有 7 个且没有进行访问的堆栈如下所示：

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

然后您可以编写自己的 pop (O(n))，它只是迭代链表，为每个节点的访问计数添加 1访问（如果你可以假设你弹出的内容总是在堆栈中，那么你只需要迭代它一次，否则你可能需要迭代两次）这样 pop(3): // Returns 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 |

Push(6):

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

pop(1): // 返回 1

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

pop(6): // 返回 1

| 5 |
| 4 |

pop(5): // 返回 4