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.
$ hg init
$ echo 123 > a
$ hg add a
$ hg commit -m "first" a
$ mkdir sub
$ echo 321 > sub/b
$ hg add sub/b
$ hg commit -m "second" sub/b
$ cat sub/b
321
$ hg co 0
0 files updated, 0 files merged, 1 files removed, 0 files unresolved
$ cat sub/b 2>/dev/null || echo "sub/b not present"
sub/b not present
$ test -d sub || echo "sub not present"
sub not present