Python 3.x

There is a lot to this question:

Starter Code:

import TStack as Stack def create(): """  Purpose  creates an empty queue  Return  an empty queue  """  q2 = {} q2['e-stack'] = Stack.create() q2['d-stack'] = Stack.create() return q2 def is_empty(queue): """  Purpose  checks if the given queue has no data in it  Pre-conditions:  queue is a queue created by create()  Return:  True if the queue has no data, or false otherwise  """  return True def size(queue): """  Purpose  returns the number of data values in the given queue  Pre-conditions:  queue: a queue created by create()  Return:  The number of data values in the queue  """  return 0 def enqueue(queue, value): """  Purpose  adds the given data value to the given queue  Pre-conditions:  queue: a queue created by create()  value: data to be added  Post-condition:  the value is added to the queue  Return:  (none)  """  return def dequeue(queue): """  Purpose  removes and returns a data value from the given queue  Pre-conditions:  queue: a queue created by create()  Post-condition:  the first value is removed from the queue  Return:  the first value in the queue  """  return None def peek(queue): """  Purpose  returns the value from the front of given queue without removing it  Pre-conditions:  queue: a queue created by create()  Post-condition:  None  Return:  the value at the front of the queue  """  return None

Tstack.py:

def create(): """  Purpose  creates an empty stack  Return  an empty stack  """  return '__Stack__',list() def is_empty(stack): """  Purpose  checks if the given stack has no data in it  Pre-conditions:  stack is a stack created by create()  Return:  True if the stack has no data, or false otherwise  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error : Expected __Stack__ but received '+t return len(s) == 0 else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def size(stack): """  Purpose  returns the number of data values in the given stack  Pre-conditions:  stack: a stack created by create()  Return:  The number of data values in the queue  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return len(s) else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def push(stack, value): """  Purpose  adds the given data value to the given stack  Pre-conditions:  queue: a stack created by create()  value: data to be added  Post-condition:  the value is added to the stack  Return:  (none)  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t s.append(value) else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def pop(stack): """  Purpose  removes and returns a data value from the given stack  Pre-conditions:  stack: a stack created by create()  Post-condition:  the top value is removed from the stack  Return:  returns the value at the top of the stack  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return s.pop() else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def peek(stack): """  Purpose  returns the value from the front of given stack without removing it  Pre-conditions:  stack: a stack created by create()  Post-condition:  None  Return:  the value at the front of the stack  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return s[-1] else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) 

TQueue.py:

def create(): """  Purpose  creates an empty queue  Return  an empty queue  """  return '__Queue__',list() def is_empty(queue): """  Purpose  checks if the given queue has no data in it  Pre-conditions:  queue is a queue created by create()  Return:  True if the queue has no data, or false otherwise  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return len(q) == 0 else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def size(queue): """  Purpose  returns the number of data values in the given queue  Pre-conditions:  queue: a queue created by create()  Return:  The number of data values in the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return len(q) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def enqueue(queue, value): """  Purpose  adds the given data value to the given queue  Pre-conditions:  queue: a queue created by create()  value: data to be added  Post-condition:  the value is added to the queue  Return:  (none)  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t q.append(value) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def dequeue(queue): """  Purpose  removes and returns a data value from the given queue  Pre-conditions:  queue: a queue created by create()  Post-condition:  the first value is removed from the queue  Return:  the first value in the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return q.pop(0) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def peek(queue): """  Purpose  returns the value from the front of given queue without removing it  Pre-conditions:  queue: a queue created by create()  Post-condition:  None  Return:  the value at the front of the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return q[0] else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue))

Question 4 (16 points) Purpose: To work with ADTs on the ADT programming side. To learn that multiple implementations can have an identical interface Degree of Difficulty: Moderate to Tricky.A substantial number of marks can be obtained in this question without solving it completely. The implementation of QueueTwo might be a little confusing, but it is not actually difficult. In class we saw ADTs for Stacks and Queues implemented as Python lists. The code for these is available on Moodle (but not on the A4 page). The Queue implementation used Python list methods to reaize the behaviour of the Queue we used append() ?nside the enqueue ( ) operation, and pop (0) ?nside the dequeue() operation. The ADT interface hides the details of the implementation. In this question, you'll be building an alternate implementation of the Queue ADT, called QueueTwo. The ADT interface for QueueTwo is exactly the same as Queue, but the implementations behind the interface are quite different. The lesson to learn here, among other things, is that there may be several ways to implement an ADT's operations. From the outside, a QueueTwo looks exactly like a Queue. But on the inside, the data structure for the QueueTwo implementation will be a dictionary containing twoStacks. Let's call them E-stack and D-stack. The create operation is as follows: def create(): Purpose creates an empty queue Return mpty queue q2 D 'e- stack'] Stack.create () q2[ 'd- stack'] Stack.create () return q2 The two stacks will be hidden behind the ADT interface, and the QueueTwo operations will use these two stacks in a clever way, so that, to an applications programmer, the queue behaviour is still FIFO. The ADT programmer, however, will see that the two LIFO stacks, working together.get the FIFO job done But how? That's the big question. In general, an enqueue operation will place the new value on the top of the E-stack (the E comes from enqueue). The dequeue operation will remove the value from the top of the D-stack (the D comes from dequeue). But we have to do this carefully, as follows. The create operation above starts with two empty stacks. New data enqueued should be pushed on the E-stack. The enqueued data will pile up on the E-stack as longas there havebeen no dequeue operations. However, when there is a first dequeuerequest, the valueto be dequeued has to be the first item enqueued (FIFO, remember), and in this situation, it will be at the bottom of the E-stack! Therefore, before you can dequeue it, you have to pop all elements from the E-stack and push them on to the D-stack. Now the value to be dequeued is at the top of the D-stack, and can be popped! In general, youmay see enqueue and dequeue requests in any order. The following rules indicate what to do: . If there is an dequeue operation when the E-stack is not empty. we popevery element off the E-stack and push it on to the D-stack first, then pop the top element of the D-stack. .If there is an enqueue operation when the D-stack is not empty.we pop every element off the D-stack and push it on to the E stack first, then push the new element on top of the E-stack