有一些数据结构对于大多数程序员来说很有用，但是却不为人所知。它们都是哪些呢？
每个人都知道链表、二叉树和哈希表，但是例如跳表和布隆过滤器呢？我想了解更多不太常见但值得知道的数据结构，因为它们依赖于巨大的思想，并且丰富了程序员的工具箱。
PS：我还对像舞蹈链这样聪明地利用常见数据结构属性的技术感兴趣。
编辑: 请尝试在描述数据结构的页面中包含链接。此外，请尽量添加一些关于为什么某个数据结构很酷的词语（正如Jonas Kölker 已经指出的）。此外，请每次只提供一个数据结构的答案。这将使更好的数据结构根据它们的投票结果浮现在最上面。
使用两个栈实现队列非常节省空间（与使用至少一个额外指针/引用开销的链表相比）。
当队列很大时，这对我非常有效。如果我能在指针上节省8字节，那么有一百万条记录的队列就可以节省约8MB的RAM。
一个合适的字符串数据结构。几乎每个程序员都会使用语言本身对该结构的支持，但通常这种方式效率低下（特别是对于构建字符串而言，你需要一个单独的类或其他东西）。
最糟糕的是在C中将字符串视为字符数组，并依赖NULL字节来确保安全性。
我个人认为稀疏矩阵数据结构非常有趣。 http://www.netlib.org/linalg/html_templates/node90.html
著名的BLAS库使用这些。当您处理包含数十万行和列的线性系统时，使用它们变得至关重要。其中一些也类似于紧凑网格（基本上像桶排序的网格），这在计算机图形中很常见。 http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf
就计算机图形而言，MAC网格有点有趣，但只是因为它们很聪明。 http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf
Delta列表/ Delta队列被用于类似cron或事件模拟器的程序中，以确定下一个事件应该何时触发。 http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf
一个角缝合数据结构。从摘要中可以看出：
角缝合是一种表示矩形二维对象的技术。它似乎特别适用于VLSI布局交互式编辑系统。该数据结构具有两个重要特点：首先，明确地表示了空白区域；其次，矩形区域在其角落处被缝合在一起，就像拼布一样。这种组织形式导致快速算法（线性时间或更好）用于搜索、创建、删除、拉伸和压缩。该算法是在简化的VLSI电路模型下提出的，并讨论了该结构的存储要求。测量表明，角缝合需要大约三倍于最简单表示的内存空间。
Burrows–Wheeler转换（块排序压缩）
它是压缩的基本算法。假设您想要压缩文本文件中的行。您可能会说，如果对这些行进行排序，就会丢失信息。但是BWT的工作方式是通过对输入进行排序来大大降低熵，并保留整数索引以恢复原始顺序。
