In this task, you will compare the runtimes of the dequeue$()$ methods in the Bounded Queue and the Circular Queue.

In the Bounded Queue, the dequeue method removes the item at the front of the queue, and then shifts the remaining items in the list to the left $($i$.$e$.$ to fill in the hole created by removing that first item$).$ For a Bounded Queue containing $n$ items, what is the big$-$O time efficiency of the dequeue?

In the Circular Queue, you just shift the head index when you dequeue an item $-$ no shifting of the actual data elements is required. For a Circular Queue containing $n$ items, what is the big$-$O time efficiency

of the dequeue?

Considering your answers to the above two questions, which queue's dequeue do you predict will run faster?

Download and save lab$6\_$efficiency.py and terminalplot.py$.($Save in the same folder as your queue.py from Exercise $1.)$ In this file, both our Bounded and Circular Queues have been imported from queues.py$.$ This file also contains $4$ function definitions: $3$ have already been completed for you $($enqueue$\_$experiment, average$\_$dequeue$\_$experiment, and main$).$ Read through

the comments of those $3$ functions to understand what they are doing.

Complete the function dequeue$\_$experiment$($queue$)$ so that it removes the first item in the

queue, and continues to do so until that queue is empty. Note that the queue is passed in as an

input to the function $-$ so you do NOT have to create it or fill it with data in this function. Use a

function from either the time or timeit modules to measure how long it takes to dequeue all of the

items in the queue, and return that time measurement.

Hint: there is an example of how to use time.time$()$ at the bottom of

lab$6\_$efficiency.py$.$ The time module returns times in seconds.

import time

start $=$ time.time $()$

# The statement$($s$)$ that you want to test

end $=$ time.time$()$

time$\_$interval $=$ end $-$ start

Run lab$6\_$efficiency. $($This may take some time to run.$)$ This will run a number of experiments,

measuring the time it takes to dequeue all items from Bounded and Circular Queues of increasing

capacities. These times will be printed in a table for you to view. The data should also be plotted

for you, with time on the $y-$axis, and $n$ on the $x-$axis $($where $n$ is the number of dequeues made$).$ If

a plot is not displayed $($i$.$e$.$ if you see a message that says "Not able to print graph.

Continuing..."$),$ plot the data from the table using a spreadsheet program. You can run more

experiments with larger queue capacities to get more values for your graph, but keep in mind that

doing so will increase the runtime of the overall program. Which has a more efficient dequeue

method: the Bounded Queue, or the Circular Queue?

terminalplot.py