CS241-Project 3 Queue the Stacking of the Deque Solved

Because we will use a deque as the storage medium for our queues and stacks, we will begin there. You will implement two deque classes, one using an array to store the contents and one using a linked list to store the contents. Notice that regardless of how you store the data, the six operations that define a deque must be present: two pushes, two pops, and two peeks. If something calls itself a deque, it must provide at least those six methods. The programming pattern that enforces this is called an interface or more generally an abstract base class. We provide a complete abstract base class called Deque in the file Deque.py. Notice that the file does not contain implementations; it only defines the functions that must be present. If you attempt to inherit from Deque, the child class must contain the methods listed in the abstract base class, or Python will refuse to construct the object and terminate. This is done via the special method __subclasshook__:

  def __subclasshook__(child): 

    required_methods = {'push_front', 'push_back', \                         'peek_front', 'peek_back', \                         'pop_front', 'pop_back'}     if required_methods <= child.__dict__.keys(): 

      return True     return False 

Python will call this method to see if a child class is allowed to inherit from the Deque class—that is, are the six required methods a subset of the methods in the child's namespace? (In Python a set B is a subset of set A if and only if A <= B is True.) If all six methods are there, __subclasshook__ will return True, indicating that child looks like a deque and instantiation can proceed. If any method is missing, __subclasshook__ will return False, indicating that the child does not qualify as a deque and instantiation cannot proceed. This file is complete; do not modify Deque.py.

Linked_List_Deque       and Array_Deque      should     both     inherit     from                                           Deque.

Linked_List_Deque's constructor will initialize an empty linked list for the data. Array_Deque's constructor will initialize an empty array for the data. The six required methods will have different implementations in each class because we interact with arrays and linked lists differently. Except for performance differences, the user of your deque should not be able to tell whether the implantation used a linked list or an array. Their functionality (and string representations) must be identical.

So far, we have always directly called a constructor/__init__ to build new objects. Here, we have two different classes that can create objects that do what we want. To support both of them, we introduce one more new design pattern: the factory method. The factory method is simply a function that returns various implementations of the abstract base class depending on some condition. Here, that condition is an optional parameter deque_type:

LL_DEQUE_TYPE = 0 

ARR_DEQUE_TYPE = 1 

 def get_deque(deque_type=LL_DEQUE_TYPE):   if deque_type == LL_DEQUE_TYPE:     return Linked_List_Deque()   elif deque_type == ARR_DEQUE_TYPE: 

    return Array_Deque()   raise NotImplementedError 

If the user calls this method with a parameter value of ARR_DEQUE_TYPE (or 1), she will get an array-based deque. If she specifies LL_DEQUE_TYPE (or 0) or does not provide an argument, she will get a linked list-based deque. Once the object is returned, the user does not care about the implementation details; she only cares that she has a deque. You can imagine a larger software system where this decision is made based on the contents of a configuration/preferences file or some other setting. (If you have previously programmed in a language like C++ or Java, note that although you construct a Linked_List_Deque or Array_Deque, the factory method returns an object of type Deque, meaning that only methods defined in the Deque interface can be used on the returned object.) This is the beauty of polymorphism.

One important detail about the Array_Deque is that you must not limit its capacity. Initially, the array should have a capacity of just one single cell. Whenever the user pushes an item and no cells are available, first double the capacity of the contents array and copy the contents of the old array to the new one. We have seen this requirement of array-based implementations several times in lecture; now you must implement it. After resizing the array, you should have an available cell for the item being pushed. Notice that the __grow method skeleton in Array_Deque is private; there is no reason for the user to know about this logic as long as the item ultimately lands in the right spot of the deque.

Once your deque is implemented, use it as the storage medium in your stack and queue implementations by calling get_deque in their respective constructors. Consider carefully the performance implications of your design choices. What performance results from placing the top in different locations? Choose the best one. Do the same for the front and back of your deque.  

Even though there are two deque implementations, there is only one implementation each of queue and stack. The queue and stack implementations must work correctly regardless of which deque is used to store their contents. Note that no exceptions are raised by any methods in Deque, Stack, or Queue.

Now you have stack and queue implementations that work with either array-based or linked list-based deques, solve the following two problems using your stack implementation.

The Towers of Hanoi
In the ancient game Towers of Hanoi, there are three pegs on which discs of varying size can be stacked. The rules are simple:

•        Each disc must be smaller than every disc underneath of it.

•        Only one disc may be moved at a time.

Initially, all discs are stacked on the first peg. The goal is to move all discs to the third peg without violating either of the above rules. Iterative solutions to this problem are not intuitive (though they exist). Consider the problem recursively. If the goal is to move 𝑛 discs, find a solution that involves moving 𝑛−1 discs and combining that movement somehow with the single disc left behind. Take advantage of the auxiliary peg, and consider carefully which pegs should be used as the source, auxiliary, and destinations pegs at each step. Remember that parameters are just temporary local variables that get aliased to whatever is passed in on each function call.

Once you have your Stack implemented, use it to solve the Towers of Hanoi problem, for which I have provided a skeleton file. In this implementation, discs will be represented by integers that correspond to their diameters with 0 being the smallest disc. You must solve this recursively. Fill in the #TODO section in the recursive call to implement the movement from one stack to another. My solution is six lines of code including the if and else lines (so really only four lines of actual code). I have included some print lines in the recursive function so that you can see the behavior as the algorithm progresses. Observe the timings and discuss your conclusions about this algorithm's performance in your writeup.  For 3 discs, my solution prints:

(page break to keep sample output together) 

             

PS C:\Users\Jim Deverick\Box Sync\CSCI241\2016Spring\projects\3 python .\Hanoi_sol.py 

2 [ 0, 1, 2 ] [ ] [ ] 

1 [ 0, 1, 2 ] [ ] [ ] 

0 [ 0, 1, 2 ] [ ] [ ] 

0 [ 1, 2 ] [ ] [ 0 ] 

 

0 [ 0 ] [ 2 ] [ 1 ] 

0  [ ] [ 2 ] [ 0, 1 ] 

 

1  [ 2 ] [ ] [ 0, 1 ] 

 

1 [ 0, 1 ] [ ] [ 2 ] 

0 [ 0, 1 ] [ 2 ] [ ] 

0 [ 1 ] [ 2 ] [ 0 ] 

 

0 [ 0 ] [ ] [ 1, 2 ] 

0  [ ] [ ] [ 0, 1, 2 ] 

 

1  [ ] [ ] [ 0, 1, 2 ] 

 

2  [ ] [ ] [ 0, 1, 2 ] 

 computed Hanoi(3) in 0.0004864929792431208 seconds.