周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
优先级取消队列比维护两个不同排序的独立优先级队列更便宜。http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.htmlhttp://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf
其他回答
向左倾斜的红黑树。罗伯特·塞奇威克（Robert Sedgewick）于2008年发表的红黑树的一个显著简化的实现（大约是要实现的代码行的一半）。如果您在红黑树的实现方面遇到过困难，请阅读此变体。
与安德森树非常相似（如果不是完全相同）。
铲斗大队
它们在Apache中被广泛使用。基本上，它们是一个在环中围绕自身循环的链接列表。我不确定它们是否在Apache和Apache模块之外使用，但它们适合作为一种很酷但鲜为人知的数据结构。桶是一些任意数据的容器，桶大队是桶的集合。其思想是，您希望能够在结构中的任何点修改和插入数据。
假设您有一个bucket旅，其中包含一个html文档，每个bucket包含一个字符。您希望将所有<和>符号转换为<；并且>；实体。当您遇到<或>符号时，bucket旅允许您在旅中插入一些额外的bucket，以适应实体所需的额外字符。因为铲斗大队在一个环中，您可以向后或向前插入。这比使用简单的缓冲区要容易得多（在C语言中）。
关于铲斗大队的一些参考信息如下：
Apache Bucket旅参考
Buckets和Brigades简介
使用2个堆栈实现的队列非常节省空间（与使用至少有1个额外指针/引用开销的链接列表不同）。
如何使用两个堆栈实现队列？
当排队人数很大时，这对我来说效果很好。如果我在一个指针上节省了8个字节，这意味着拥有百万条目的队列节省了大约8MB的RAM。
区域四叉树
（引自维基百科）
区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的分区，每个叶节点包含对应于特定子区域的数据。树中的每个节点要么正好有四个子节点，要么没有子节点（叶节点）。
像这样的四叉树很适合存储空间数据，例如纬度和经度或其他类型的坐标。
这是我在大学里最喜欢的数据结构。对这家伙进行编码并看到它的工作非常酷。如果你正在寻找一个需要思考并且有点偏离常规的项目，我强烈建议你这样做。无论如何，它比通常在数据结构类中分配的标准BST派生工具有趣得多！
事实上，作为奖励，我在这里找到了（弗吉尼亚理工大学的）课堂项目前的演讲笔记（pdf警告）。
Burrows–Wheeler变换（块排序压缩）
它是压缩的基本算法。假设您想压缩文本文件中的行。你会说，如果你对行进行排序，你就失去了信息。但BWT是这样工作的——它通过对输入进行排序，保持整数索引以恢复原始顺序，从而大大降低了熵。
