周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
使用2个堆栈实现的队列非常节省空间（与使用至少有1个额外指针/引用开销的链接列表不同）。
如何使用两个堆栈实现队列？
当排队人数很大时，这对我来说效果很好。如果我在一个指针上节省了8个字节，这意味着拥有百万条目的队列节省了大约8MB的RAM。
其他回答
PATRICIA-检索字母数字编码信息的实用算法，D.R.Morrison（1968）。
PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一个子集时，Trie中的许多（大多数）内部节点只有一个后代，这是非常常见的情况。这导致Trie具有较高的空间复杂性。
http://www.csse.monash.edu.au/~合金/瓷砖AlgdS/树/PATRICIA/
正确的字符串数据结构。几乎每个程序员都满足于一种语言对结构的任何原生支持，而这种支持通常是低效的（尤其是对于构建字符串，你需要一个单独的类或其他东西）。
最糟糕的是将字符串作为C中的字符数组，并依赖NULL字节来确保安全。
Splay Trees很酷。它们以将最常查询的元素移到更靠近根的方式重新排序。
计数的未排序平衡树。
非常适合文本编辑器缓冲区。
http://www.chiark.greenend.org.uk/~sgtatham/算法/cbtree.html
看看唐纳德·克努思（Donald Knuth）展示的侧面堆。
http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx
