Categories : Java

 

A FIFO is a data structure in which things come out in the same order in which they are put inn; First In First Out. This data structure is commonly reffered to as a queue, which is why the concept is no stranger to you if you have a printer. Print jobs are printed in the same order in which they a are reqwuested. Much like the Stack, a queue is a fairly secure and stable way of storing your data.

Why a Queue?

The security of using a queue is complimented by its efficiency. Most of the time we want thiings to be retrieved in the order that they are stored, and this is what a queue does. A queue has two “holes,” one for putting data into the queue (an enqueue operation), and one for retriving data from the queue (a dequeue operation), so you do have to manage more than on access point, but the advantage is that each access point does only one thing.

How a Queue Works

I’m willing to bet that at some point in your life you’ve had to stand in line. In a fair world, there would be no cutting, no exchanging or saving places, and no VIP treatment that could bring you or anyone else directly to the front of the line. The first person in line would be the first person to get food, toickets, etc. In a fair world, standing in line would be an excellent example of a queue; The first piece of data to arrive is the first piece to be removed. So anyway, now that you’ve got those basics down, lets take a look at what the code for a basic FIFO looks like.

class FIFO
{
 private int[] a;
 private int oldest, newest, size;

 FIFO(int capacity)
 {
  a = new int[capacity];
  size = capacity;
 }

 public void enqueue(int data)
 {
   a[newest++] = data;
 }

 public int dequeue()
 {
  return a[oldest++];
 }

 public boolean isempty()
 {
  return oldest == newest;
 }
}
This is yet another nice and simple piece of code. Of course it is expandable so that you can include something along the line of a ring buffer. Let’s take a walk through one piece at a time.

class FIFO
Remember, everything in Java is a class, so we have to start out with this declaeration. However, this example should help convey why this is a strength, and not an annoyance, of the language

private int[] a;
The first thing we want to do is set aside some space for the array. Note that we’ve made it private so that it is only directly accessable in this class.

private int oldest, newest;
Here we’ve declared two ints to keep track of where data is in the buffer. Since there are two access points, there are two numbers. Again, they’re private so only the methods in this class can access them directly. You may cringe at the sight of the numbers not being given a value, but remember that they do receive the default value zero.

The third int of this bunch, size, serves a completely different purpose, so I’m mentioning it seperately. We’ll use this number to store the size of the buffer. For this example, it’s not really necessary to keep track of the size, but if you want to extend the example, you’re going to have to. I’ll discuss this in the next section.

FIFO (int capacity)
Okay, I’ll admit it, I lied. This FIFO actually has a little bit of sophistication built into it. We can specify the size of the FIFO when we make a new instance of the class, and this line is a big part of making that possible. This is really the constructor method for the class. Every class has one, but up until now we’ve been using the default no arg constructor. Now we’re actually taking this a step further by providing an argument to the instance of the class, which gives us a little more customizeability over it. FIFO is the name of the constructor because that is the name of the class. There’s no way around this. Other than that, it takes a single argument, an integer. So when you make a new instance of the class, you need to give that instance an argument, as in FIFO queue = new FIFO(5);

a = new int[capacity];
Now we’re going to use that variable that we fed into the class. capacity is the size to which integer array a is intialized.

size = capacity;
We won’t actually use the size variable in this program, but if we want to directly access the size of the array (capacity), than we need to pass its value to a globally accessable variable. This allows us to keep track of end of the array in case we need to know that information.

public void enqueue(int data)
Thus begins our definition of the enqueue() method, which we will use for getting information into the array.

a[newest++] = data;
Yep, a one liner. Give the value of data to a at the value of newest, and then incriment newest.

public in dequeue()
Yep, another function definition. dequeue() is the method that we use to get information out of the array.

return a[oldest++];
In plain english, return the value of a at oldest and then incriment oldest. It is an incriment because newest and oldest both start out at the same place. Presuming we’ve enqeued something, and thus incrimented newest, oldest will let us remember that the first thing in the buffer is still at cell 0. After its incriment, oldest will let us remember that the new oldest thing in the buffer is at cell 1, and so on.

public boolean isempty()
Another method definition begins. We need some way of telling whether or not the buffer is empty.

return oldest == newest;
If oldest and newest are the same, than we have dequeued as much as we have enqueued, and so the buffer is empty.

So that’s a wrap. We now have a queue. I caution you that it is a very rudimentary queue, and so if you actually want to go out and use it, than I highly recommend that you at least add a ring buffer to it, or something to that effect. Good luck!

 Posted on : August 22, 2014
Tags:

You might also likeclose