efficient idiomatic queue?

[Jason Orendorff]

> 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
> 
> [...]
> 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,
> [...]

Your analysis of the situation is correct, and there's no idiomatic
Python way around it, unfortunately.

The given operations are usually "quick enough", for small lists
(less than, say, 5000 items) since the constant coefficient is
small, compared to the ordinary semi-inefficiency of running
Python code in the first place.

For merge sort, you could probably

  L = []
  ... populate L using L.append() ...
  L.reverse()
  ... drain L using L.pop() ...

This way you're O(N) instead of O(N^2).  But it might baffle the
students.

## Jason Orendorff    http://www.jorendorff.com/