Question

Suppose we want to make a 10 item queue starting from location x4000. In class, we discussed using a HEAD and a TAIL pointer to keep track of the beginning and end of the queue. In fact, we suggested that the HEAD pointer could point to the first element that we would remove from the queue and the TAIL pointer could point the last element that we have added the queue. It turns out that our suggestion does not work.

Part a) What is wrong with our suggestion? (Hint: how do we check if the queue is full? How do we check if it is empty?)

Part b) What simple change could be made to our queue to resolve this problem?

Part c) Using your correction, write a few instructions that check if the queue is full. Use R3 for the HEAD pointer and R4 for the TAIL pointer.

Part d) Using your correction, write a few instructions that check if the queue is empty. Again, using R3 for the HEAD pointer and R4 for the TAIL pointer.

Answer 1

Part(A)

I think something wrong in you suggestion if you De-queue any element you just remove the link but the data are present in the memory .we don't have any better track which helping us for traversal and check that empty/full.

Part(B)

Before en-queue the element you need to check first the queue is not full and also before de-queue element check queue is not empty.(You may use circular Queue for better performance)

NOTE: you can interduce the element size and cap which tell us the queue is full or not

Part(C)

After the value inserted one after the other and check queue is full you can check that by match the address of your tail address with the queue array last index Address and head point to the first location of the array if they equal queue is full,

if(R3==R4&cap>=size)

return 1;

else

return 0;

Part(D)

Initially, the head and the tail pointers will be pointing to the same location, this would mean that the queue is empty.

you can check by comparing the pointing address of head and tail

if(R3==R4&cap<size)

return 1;

else

return 0;