Python deque vs list: why list.pop(0) gets slow (5 tested examples)

If you only ever call list.pop(0), your program works fine until the queue gets big. Then it slows...