Redundant binary counters were studied by Clancy and Knuth in 1977 and led to the discovery of finger search trees. These counters reappear recently in several new data structures. In particular we use them to design purely functional catenable double-ended queues that have O(1) worst-case time bound for each operation, purely functional finger search trees, and priority queues. In this talk I will describe these counters and some of the data structures in which we use them. (This is joint work with Bob Tarjan.)