Side note: queue solution

Thought I might as well mention my solution to the queue efficiency problem. My idea was basically to not actually remove anything from the list (the implementation we’ve seen for this ADT so far). Instead, simply start a counter at 0 and make the dequeue method (a) return the item at the index of the counter, and (b) increment the counter by 1. Now none of the remaining elements need to have their indexes shifted, which is what took so awfully long in this implementation.

The issue is that your queue could get to be massive—particularly if you have hundreds of thousands of elements to enqueue and dequeue, like zingarod showed us in lecture! I just assume that in a real computing environment, you could check CPU load and quietly clear the excess items (the cache?) in the background whenever the computer has the time and processing power.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s