c++ - 使用 BST 实现队列

Question

如何使用 BST 实现队列。

这是这样做的方法吗，继续在树中插入节点，同时保持与每个节点关联的计数值，但是在删除 BST 时应该像队列（FIFO）一样工作，所以开始从 BST 中删除具有最低计数的节点树中的值。

我得到了正确的问题和解决方案吗？如果没有，那么请向我解释这个问题。

score 3 · Accepted Answer

BST 实际上是一种不适合用于支持队列的数据结构。你真的应该使用链表，因为它会更快，更简单，更简单。

但是，如果您坚持使用 BST...

您可以将 BST 用作优先级队列，并定义一个包含“队列索引”的包装器类型，这是对项目进行排序的依据。但是，您必须定义比较以考虑当前队列索引，因为否则您只能添加与索引类型的最高值和最低值之间的差值一样多的项目。

score 1 · Accepted Answer

你可以有一个这样的队列：

BST // to store data
pointer to head; // Points to the head of the Queue
pointer to tail  // Points to the tail of the Queue

您还向 BST 的节点结构添加了一个指向另一个节点的指针，该节点将表示插入顺序。

struct Node{
  int x;
  //left pointer
  //right pointer
  struct Node *next_queune_element;
}

在插入过程中 当你想添加一个元素时，你首先访问指针tail指向的节点，使其指向你刚刚插入的新元素（BST节点）。然后更新尾指针以指向新元素。

删除期间删除 元素时，首先访问头指针指向的节点，将其存储next_queune_element在辅助临时变量中并删除该节点。最后，使头指针指向辅助临时变量。

score 0 · Accepted Answer

我认为二叉树将是这里所需的数据结构，而不是二叉搜索树。在进行函数式编程时，使用二叉树实现队列可能很有用。您可以使用在每次推送和弹出操作后保持高度平衡的二叉树来做到这一点，因此它们将始终为O (log n )。Push 和 pop 看起来像：

在这两种情况下，重新平衡都不会违反插入顺序。两者也很容易实现。您实际上正在使用具有更改的插入功能的 AVL 树。一个好处是元素不需要（完全）可订购。

3 回答 3