Hello all,

Please help me if you can:

my question is

what is the efficiency of the queue's insertion and deletion operations when the ADT list's implemetnation is

a. Array-based

b. Pointer-based


Give me a hint if you can. I am new to the C++ world so please forgive me about my questions.

Thanks in advance

Talk yourself through what steps you have to go through to work the queue (enqueuing and dequeuing). Think about the elements of the array. What steps have to happen after you remove the first element if the queue is built on an array model?

Reread your text's section on big O notation to get the right terminology.

Talk yourself through what steps you have to go through to work the queue (enqueuing and dequeuing). Think about the elements of the array. What steps have to happen after you remove the first element if the queue is built on an array model?

Reread your text's section on big O notation to get the right terminology.

Can you clarify more? If you the answer please say it if you don't mind.

I'm not going to give you the answer, I want you to figure it out on your own. Is there a section on big-O notation in your text? In other words, is the efficiency of your algorithm in either of those cases dependent on the number of items in the queue?

Draw a diagram with your model queue on top and the array (or list) representing it underneath, what has to happen after you remove the first item?

I'm not going to give you the answer, I want you to figure it out on your own. Is there a section on big-O notation in your text? In other words, is the efficiency of your algorithm in either of those cases dependent on the number of items in the queue?

Draw a diagram with your model queue on top and the array (or list) representing it underneath, what has to happen after you remove the first item?

Yes they are dependent on the number of items in the queue. After I remove the first item from the array, everything will be affected and the program wont execute. Is this correct?

What about the pointer-based implementaion. Give me a hint if you can?

I don't have a section about the big-O notation or maybe we didn't reach it yet.

help me more if you can!

See if http://www.cs.bu.edu/teaching/c/queue/ helps you (it's not a link to a page, but it's a link to a directory tree that has 4 webpages of information in it). It's about C not C++ but the concepts are the most important thing. You should verify with your instructor the details of your array-based implementation.

>>After I remove the first item from the array, everything will be affected and the program wont execute. Is this correct?

The program should always execute. If it doesn't, there's a bug

Arrays are always consecutive. No holes are allowed, so things need to be adjusted. Adjusting involves moving memory and takes time.

>> What about the pointer-based implementaion. Give me a hint if you can?

Pointers (possibly) won't rely on consecutive memory and thus will (possibly) take less memory moving and less time.

Comments
Good hints
This article has been dead for over six months. Start a new discussion instead.