代码之家 › 专栏 › 技术社区 › Rehno Lindeque

树状队列

queue data-structures language-agnostic c++

3

Rehno Lindeque · 技术社区 · 16 年前

            x -> y -> z
a -> b -> { g -> h -> i -> j }
            f -> b

有什么想法吗?使用队列池实现自己似乎是一个相对简单的结构,但我遵循的是“先思考,后编写代码”的策略:)

谢谢

编辑:

a -> b

是按顺序执行的,也是以提交结束的分支。例如。

x -> y -> z -> COMMIT

但是,a->当至少有一个分支被提交时,b将只执行一次。如果所有三个分支都以ROLLBACK结束,则丢弃整个树,包括初始事件a->B

谢谢你的回答!我一回到家就会详细复习。

5 回复 | 直到 16 年前

1

2

Quicksilver 16 年前

Boost Graph Library 包含一个称为不相交集的数据结构,该数据结构对此处所需的结构(一组相互关联的集)进行建模。

将此数据结构视为林的另一种方式。森林是树木不相交的结合体。

2

0

kiwicptn 16 年前

在我看来,它就像是 Tree ,但不是平衡的或二进制的。如果您想完全控制如何添加新节点,那么必须指定如何添加新节点。 a.addSibling(b)

因为这是为了安排时间,我猜兄弟姐妹应该大致同时去探望。你的访客,而不是回溯,将不得不为你有分支的地方产生其他访客。所以第三个元素是x,g F

也许能帮你看看 JGraphT .

3

0

Arun 16 年前

对我来说,它看起来更像一棵树(一般的树,而不是二进制的),而不是一个队列。但是,删除节点的语义需要有很好的定义。

顺便说一句,一提到“排班队列”就给我们敲响了警钟 Priority Queue 也

4

0

Rehno Lindeque 16 年前

http://en.wikipedia.org/wiki/Disjoint-set_data_structure 在这里: http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html ).

所以现在我倾向于一个简单的想法,一个队列池。一旦需要一个新队列,请从池中选择它,如果没有可用的队列,则创建一个新队列,然后将其添加到树中。如果队列为空,则将其返回到池并删除树节点。池本身将是一个优先级队列,前面分配的缓冲区最大,后面分配的缓冲区最小。一段时间后,将分配很少或没有新内存(假设发生的“弹出”量与“推”量大致相同)

5

0

Community Mohan Dere 9 年前

你说,

它也可以指树状队列,它包括多个N个y,一组状态/数据检查,从顶部(z)执行,但从底部(x)接收状态变化。

x[N]("data check") -> x[N-1]("data check") -> x[N-2]("data
勾选“->检查->y->检查-> y->状态->z->检查->z->状态->z->犯罪

对我来说(我的)是类似的问题 What are patterns/types of task queues? Can the multi-level task queue exist in form of a N-tree? )似乎是一个N级结构,它遍历子节点,每个级别有三种状态机可用:,$me->tryCommit(下面是tryadvancechilds(tryAdvanceToNextSiblingStep(getNextSibling()))和要重写的混乱实现。