efficient idiomatic queue?

[David Eppstein]

What is the idiomatic way in Python of implementing the following 
operations on a list of elements:
 - return the element at the front of the list, without changing the list
 - remove the element from the front of the list
 - add a new element to the rear of the list

My first choice would be L[0], del L[0], and L.append(), however it 
seems from some brief experiments that the del operation takes time linear 
in the length of the list, so this would be very inefficient for long 
lists. I also tried replacing the del with L=L[1:] but that wasn't any 
better.  A third possibility would be to have to variables L and i, and 
implement the three operations with L[i], i=i+1, and L.append(), which is 
fast but not good in space usage when the total number of operations is 
much larger than the length of the list.

Is there a simple Pythonic way of implementing these three operations in 
constant (amortized) time per operation and space linear in the length of 
the list?

The application this came up for me is a merge sort example for an 
algorithms class.  So, I don't want to confuse the students with additional 
code that has nothing to do with the actual algorithm, otherwise it would 
be easy to do linked lists, or to do the third possibility above plus 
slicing L down to size when i grows too large, or something like that.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/