Data Structure and Algorithms in python

Q1 - Suppose an initially empty queue Q has executed a total of 32 enqueue operations, 10 first operations, and 15 dequeue operations, 5 of which raised Empty errors that were caught and ignored. What is the current size of Q?

I think the answer of this question is 22 ; but i need help in this question ...

Q2 - Had the queue of the previous problem been an instance of ArrayQueue that used an initial array of capacity 30, and had its size never been greater than 30, what would be the final value of the front instance variable?

It would help to start by defining the operations on queues strictly:

• void Enqueue(Item) - insert Item to the end of the queue.
• Item Dequeue - remove and return the Item at the front of the queue. Throw an Empty Error if the queue is empty when the operation is invoked.
• Item First - return the Item at the front of the queue, do not remove it.

This means that Enqueues add one to the queue's size, Dequeues remove one from the queue's size, if the size is greater than 0, and Firsts don't impact the queue's size.

So we have 32 increments, 10 no-ops and 15 potential decrements. Five of those potential decrements did not impact the queue size, so only ten remain.

32 * 1 + 10 * 0 + 5 * 0 + 10 * -1 = 22

This is only valid if the operations are defined as they are above. For example, if we change the definition of Enqueue and Dequeue to be like this:

• void Enqueue(List of Items) - insert each Item in the List to the end of the queue.
• List of Items Dequeue(Count) - remove and return Count Items from the front of the queue. Returns max(Count, queue's size) Items.

Now, we don't have enough information to answer the question. This is why it's important to be precise about the operations you're considering.

As for the second question, assuming an ArrayQueue is implemented as a circular array buffer of size 30 (30-element array with a pointer to the "front" and "back" elements), and assuming that Enqueues happen on the "back" and Dequeues happen on the "front", then all we need to do is count the number of Dequeues, as this is the only operation that affects the front pointer.

15 total possible operations can change where front points. 5 of them wouldn't have changed the position of front, so front would have moved a total of 10 times. Assuming the array is zero-indexed, front will be pointing at array index 10 (the 11th item, ready for the next Dequeue or First operation).

A different implementation of ArrayQueue would have a different answer. Again, it helps to be specific about the implementation of structures when trying to reason about their inner workings.