Skip to main content

Implementing A Queue With An Array

I'm working on coding an array implementation of a queue in Java.  The implementation should have the following features:

  • The array has a head which marks the item least recently inserted.
  • The array has a tail which marks* the item most recently inserted.
  • Enqueue() adds an item to the tail of the array.
  • Dequeue() removes an item from the head of the array.
  • The array will resize() dynamically as it gets too small or too large.
  • Size() returns the size of the queue from head to tail.
  • IsEmpty() returns whether or not the queue contains anything at all.
You start out by initializing an empty array.  It looks like this:


[0] null (head / tail)

So at the beginning, the head is set to zero.  I guess the tail can also be zero.  Then you enqueue.

[0] "To" (head / tail)

So the first time you try to enqueue, the head is null.  Fill the head.  Now you want the tail to move up.  

Here's the deal with the tail (*) -- in normal cases, you want to put whatever you enqueue into the tail.  So the tail is associated with the end of the queue, as I conceive it, but actually it marks where we will insert the next item.

So the general process is this: insert at the tail, move the tail up.

What about dequeue?  Here you want to return what's at the head, empty the head, then move the head up.

But that leads to an interesting situation:

[1] "To" (Head)
[2] "Be"
[3] "Or"
[4] null (Tail)

**dequeue**

[1] null
[2] "Be" (Head)
[3] "Or"
[4] null (Tail)

So now say that I enqueue.  What happens to the tail?  Well, if I increase it, the tail will be out of bounds.  So one option would be to resize the array.  But I still have space for a new insert at the beginning of the array, where I did my last dequeue.  The trick here, I think, is to increment the tail like this:

tail = (tail + 1) % array.length

So when the tail gets past the end, you send it back to the beginning.  That leads to some complications I'm still trying to work out and will possibly discuss in my next post.

Comments

Post a Comment

Popular posts from this blog

Getting Geodata From Google's API

The apps I'm going to be analyzing are part of Dr. Charles Severance's MOOC on Python and Databases and work together according to the following structure (which applies both in this specific case and more generally to any application that creates and interprets a database using online data). The data source, in this case, is Google's Google Maps Geocoding API.  The "package" has two components: geoload.py  and geodump.py .  geoload.py  reads a list of locations from a file -- addresses for which we would like geographical information -- requests information about them from Google, and stores the information on a database ( geodata.db ).  geodump.py  reads and parses data from the database in JSON, then loads that into a javascript file.  The javascript is then used to create a web page on which the data is visualized as a series of points on the world-map.  Dr. Severance's course focuses on Python, so I'm only going to work my way through ...
Post a Comment
Read more

Shell Sort

Today I spent a little bit of time researching the "Shell" sort.  I wanted to post a few notes about the Princeton Algorithms Course's implementation to help me solidify my understanding. First, a little tidbit.  When I first heard about this algorithm, I thought it had something to do with shell games.  Turns out a man named Donald Shell discovered this method of sorting, whence the name. The Algorithms  book gives the following explanation (Sedgewick and Wayne,  Algorithms, 4th ed., p. 258): The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values o...
Post a Comment
Read more

Cash Register Algorithm

Goal: Given a price, cash tendered, and two dimensional array of change ordered by denomination (pennies, dimes, quarters, etc.), return an array of exact change. Exceptions: return "insufficient funds" if there isn't exact change; return "closed" if exact change is equivalent to the contents of the array; return a warning if the price is greater than the cash tendered. Analysis First, check the difference between the price and cash tendered. If the price is greater than cash tendered, return an error. If the price equals the cash tendered, no change is needed. From this point, we assume the price is less than the cash tendered. It helps to consider a simpler case where the cash tendered and the change on hand is all pennies and dimes.  You could proceed like this: (1) see if all of the change can be given in pennies.  If it can't (2) see if the remainder can be made up with dimes.  We could get the following cases: A. All your pennies and som...
Post a Comment
Read more