deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).

Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object "is composed of a doubly-linked list", which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.

For Python 2.7 and 3.5, the URLs of these source code files are:

1. https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c

2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

3. https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below.

import string
from collections import deque

%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 µs per loop

%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 µs per loop

%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 µs per loop

%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 µs per loop

d = deque(range(100000000))

%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop

l = range(100000000)

%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop

Yes. list.pop(0) is O(n), and deque.popleft() is O(1).

Well, first off, it's called pop for both list and deque, there is no popright method on deques.

There is usually no meaningful performance difference between the two; every once in a while, a pop on a deque will cause a block deallocation (which has fixed overhead, it just makes that particular pop a little more costly), and on a list it can cause a realloc to shrink the underlying storage (which could end up being O(n), but only a tiny fraction of pops will cause it); asymptotically they're both O(1) operations. If your list is truly huge, then shrinks a lot you might get the occasional performance hiccup when it shrinks the underlying storage, but otherwise you're highly unlikely to notice a difference.

In answer to your question, deques are ever-so-slightly more efficient for use as stacks than lists; if you're importing collections anyway, and need a stack based structure, using a deque will get you a tiny benefit (at least on CPython, can't speak to other implementation). But it's not really worth micro-optimizing here; the cost of importing collections in the first place, and the cost of whatever useful code you execute based on this stack, likely dwarfs whatever tiny difference you'll see between list and deque for pops from the right. A simple ipython3 microbenchmark:

In [24]: %%timeit from collections import deque; s = deque([0] * 10000); onethousandnones = (None,) * 1000; pop = s.pop
    ...: ; push = s.append
    ...: for _ in onethousandnones:
    ...:     pop()
    ...: for _ in onethousandnones:
    ...:     push(0)
    ...:
    ...:
104 µs ± 7.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [25]: %%timeit s = [0] * 10000; onethousandnones = (None,) * 1000; pop = s.pop; push = s.append
    ...: for _ in onethousandnones:
    ...:     pop()
    ...: for _ in onethousandnones:
    ...:     push(0)
    ...:
    ...:
131 µs ± 8.93 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

So for a 1000 pops followed by 1000 pushes onto our stack, the deque-based stack took 30 µs less (~15 ns less per operation). Now admittedly, if I remove the call parentheses to time the base overhead, the base overhead was around 50 µs, so the overhead specifically attributable to the list is a significant fraction of the "minimum cost" of the deque, but it's still pretty small in the context of a program that is presumably doing something useful, not just pushing and popping to a stack. And it's pretty stable regardless of size; for a stack that's 10x the size, the cost remains unchanged for both deque and list. If the stack was growing and shrinking so much that list's amortized growth was kicking in, it might suffer a little more from the larger reallocations, but it's not normally something to worry about.

When mydeque is empty, it resolves as False in the while loop.

while mydeque:
    value = mydeque.popleft()

This will run through all values in mydeque.