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
$ cat > a <<EOF
> a
> b
> c
> EOF
$ hg ci -Am adda
adding a
$ cat > a <<EOF
> d
> e
> f
> EOF
$ hg ci -m moda
$ hg diff --reverse -r0 -r1
diff -r 2855cdcfcbb7 -r 8e1805a3cf6e a
--- a/a Thu Jan 01 00:00:00 1970 +0000
+++ b/a Thu Jan 01 00:00:00 1970 +0000
@@ -1,3 +1,3 @@
-d
-e
-f
+a
+b
+c
$ cat >> a <<EOF
> g
> h
> EOF
$ hg diff --reverse --nodates
diff -r 2855cdcfcbb7 a
--- a/a
+++ b/a
@@ -1,5 +1,3 @@
d
e
f
-g
-h