Introduction to Programming in Python, Aug-Dec 2014
                          Assignment 7
                  Due Saturday, 15 November, 2014

----------------------------------------------------------------------
NOTE: The usual rules apply about file names for submitting your
      assignment.
----------------------------------------------------------------------

Filename: deque.py

Deques and doubly linked lists
------------------------------

Write a Python class Deque that implements a double ended queue
supporting the following operations:

   insert_front(x)   # Inserts x at front of queue
   delete_front()    # Deletes and returns element at front of queue
   insert_rear(x)    # Inserts x at rear of queue
   delete_rear()     # Deletes and returns element at rear of queue

All four operations should take constant time, independent of the
size of the deque.  The two delete functions should generate an
IndexError exception with a suitable message if the deque is empty.

To build the deque, write another Python class Doublenode that
defines nodes with three internal variables: one to store a value
and two to point to the next and previous node in the list.
(This is called a "doubly-linked list".)  Don't cheat and use
Python's built in list type to store the data in the deque!

The Deque class should define a header node that is not part of
the deque itself, with pointers to the first and last Doublenode
nodes in the deque.  (See the supplementary material after
Lecture 22 on how to implement normal lists with a header node
and internal nodes.)

The __init__ function for Deque should allow the creation of a
deque with an initial list of values.  The default is to create
an empty deque.  The optional argument to __init__ should be a
normal Python list, whose values are then inserted into the deque
so that the order is preserved.

You should also define an appopriate __str__ function for Deque
to display the contents of a deque in sequence, from front to
rear.  

Deque and Doublenode should be separate classes (i.e., do not
nest Doublenode inside Deque), both defined in "deque.py".

======================================================================