What are the lesser known but useful data structures? (stackoverflow.com)

It really annoys me that questions like this aren't welcome on Stack Overflow anymore. This is a great example of a question which doesn't have "one right answer" but is still constructive and relevant.