In year 2264 the twenty-third starship came off the assembly lines at NASA. This starship was called the USS Enterprise. Unfortunately, the core libraries of the Enterprise were corrupted during an exploration mission. The only uncorrupted data structure left was a simple stack. A team of engineers set out to reimplement all other data structures in terms of stacks, and they started out with queues (a) (5 points) The following are parts of their original implementation of queue using two stacks (in stack and out stack). Analyze the worst-case running times of its enqueue and dequeue methods, and express them using "Big-Oh" notation 1: function ENQUEUE(o 2 instack.push(o) 3: 4: function DEQUEUE 5: while not in stack.isEmpty do 6: 7: if out stack.isEmpty then out.stack.push(in stack.pop) throw QueueEmptyException 9 return.obj outstack.pop 10 while not out stack.isEmpty do in_stack.push(out stack.pop)) 12: return return.obj b) (5 points) Later in the 23rd century, a new chief engineering officer named Montgomery Scott took over. He set out to optimize the old code. Thus a new implementation of a queue (still using two stacks) was born. What is the worst-case total running time of performing a series of 2n enqueue operations and n dequeue operations in an unspecified order? Express this using "Big-Oh" notation. Hint: Try using techniques presented in section 1.5. 1: function ENQUEUE(o 2 instack.push(o) 4: function DEQUEUE 5: if out_stack.isEmpty then 6: while not in_stack.isEmpty) do out stack.push(in stack.pop) 8: if out stack.isEmpty then throw QueueEmptyException 10: return out.stack.pop)