Conceptual Questions Suppose you are given a (strange) computer that can only perform the following instructions (in addition to if and while) . S-create_stack) create stack makes a new stack S i S.pop() removes the top item from stack s and places it in variable i . S.push(i) makes item i the top item in stack S Solve the following problems and justify your answers 1. (10 pts) Show how you can use these operations to implement a queue (operations Q -create_queue(), enqueue (i), i- dequeue)) .A picture might help to explain your answer Hint: take a look at the following image ush pop push pop F R 4 4 1 Stack 1 Stack 2 Stack 1 Stack 2 Enqueue Dequeue 2. (5 pts) What's the worst case running time of your dequeue implementation? 3. (5 pts) Over a series of n enqueues followed by n dequeues, how many pop) operations does your implementation perform? Implementation Questions Write a program that implements a queue using a standard list implementation (see M&R 312) and a queue using your solution to conceptual question #1. For the latter, you must implement a stack using a standard list implementation (see M&R 3.5) Generate a sequence of enqueue s and dequeue s to test your two queue implementations. To generate the test sequence, randomly enqueue and dequeue strings from words txt, a file containing all 118,309 valid crossword puzzle words, one on each line. Evaluate the differences between the two implementations by performing the following 1. Using timeit(), compare the running time for each queue implementation operating on your test sequence. Vary the size of your test sequence Note: Make sure you are using the same test sequence for each implementationl Also, remove all frivolous code from your implementations (e.g. print() statements), as these can affect the timingl 2. Write code to test your answer to conceptual question #2. Write up your observations 3 Write code to test your answer to conceptual question #3. Write up your observations