树可以用来创建堆栈吗？

Question

我知道链接列表、集合和数组可以用来自己创建堆栈。背后的理论是

linked-list：在某些语言中，链接列表是数组的替代品.堆栈是先入先出的操作。

array：push和pop方法调用类似堆栈的行为。

set：集合与数组完全相同，只是它不具有重复元素的特性。

我很难找到一种可以用树来创建堆栈的方法

Answer 1

微不足道的。

您的堆栈对象只是维护一个ints树。推送操作与插入键大于当前最大键的树中的项相同。这应该是根注释中的键，新节点将成为新根。

Pop操作是删除具有最大键(根)的节点。

这种方法仍然适用于自平衡树，尽管对于那些树来说，它会慢一些(因为最大键不再在根目录上，所以访问它需要O(ln，N)而不是O(1))。

堆栈位置的内容只是树节点中的附加内容。

Answer 2

已经给出了一个很好的答案，但是您也可以实现一个max堆，然后插入一个优先级等于堆中当前元素数量的元素。