cleanup: use the deque type where appropriate
There have been quite a few places where we pop elements off the
front of a list. This can turn O(n) algorithms into something more
like O(n**2). Python has provided a deque type that can do this
efficiently since at least 2.4.
As an example of the difference a deque can make, it improves
perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
http://mercurial.selenic.com/bts/issue1089
$ hg init
$ mkdir a
$ echo a > a/b
$ hg ci -Am m
adding a/b
$ hg rm a
removing a/b (glob)
$ hg ci -m m a
$ mkdir a b
$ echo a > a/b
$ hg ci -Am m
adding a/b
$ hg rm a
removing a/b (glob)
$ cd b
Relative delete:
$ hg ci -m m ../a