There are numerous application for either of these data structures. For example, you issue a print command on a multi-user system, is it not possible for other people to also issue the same command? A queue allows us to process these print requests in order. An example of where a stack is useful is in implementation of a preemption mechanism for resources. Lets consider a single cpu system with multiple processes competing for access to cpu. Often we assign priority to these requests. Suppose we have 4 priority levels, 1 through 4. Now, assume a process with the lowest priority (1) takes over the cpu and is processed for a while. Suppose that a new process comes along with priority 2, it preempts the first process by taking it over the cpu, but the system can't throw away the first process, so it is put on a stack. Consider a process with priority 3 coming along and preempting the process with priority 2, guess what happens to the preempted process? Yes, it gets put on the stack, but because of the behavior of the stack, when the priority 3 process is done, it is a "no brainer" as to who should be picked from the ones preempted. The one with the highest priority will be at the top and it is the one we take off since the data structure is a stack.
There are variety of implementations for stacks and queues. For a queue,
we can define an array and put each element that comes in in the next
available spot. When it is time to take an element off, we take the element
in cell zero and move the rest back.
We can implement a circular queue where we keep two
indexes one to the front of the queue and one to the back. In such a
implementation, we don't move everything back when an element is taken off--we
just move our index over to the next cell. But, its more complicated, as the
name indicates when we get to the last spot in the array we circle back to
the beginning. This makes adding and removing a little more complex, but
the advantage is in that you don't have to move everything back, each time
that you remove an element. The last implementation is a linked list. If
we don't know how much room we need to put aside for our queue, we
implement it with a linked list that can grow indefinitely!
Here is a simple stack class for integers and a simple queue of strings.
Note that neither is designed to handle exception cases, such as, attempting
to dequeue when there is nothing in the queue, or push something
onto the stack when it is full. The application just blows up in those cases.
public class Stack {
private int size;
private int top=-1;
private int l[];
public Stack (int init_size) {
size = init_size;
l=new int[size];
}
public boolean empty() {
return top == -1;
}
public boolean full() {
return top == size-1;
}
public int pop() {
top--;
return l[top+1];
}
public void push(int val) {
l[++top]=val;
}
}
public class Queue {
private int size;
private int last=-1;
private String q[];
public Queue (int init_size) {
size = init_size;
q=new String[size];
}
public boolean empty() {
return last == -1;
}
public boolean full() {
return last == size-1;
}
public void enqueue(String x) {
q[++last]=x;
}
}
public String dequeue() {
String temp = q[0];
for (int i=0;i<last;i++) q[i]=q[i+1];
}
}
The major advantages to Object Orientation are encapsulation and inheritance.
We have already discussed encapsulation when we discussed the class Tank. An object or an instance of class tank not only has the content of a tank held inside it, it has the methods that operate on or query the content inside it also. This way, no matter where in the application that uses tanks trys to add or remove liquid, we can be sure content is never left in an abnormal state. Remember that we throw exceptions if the application attempts to over fill the tank or take too much out of the tank. This simple solution saves a great deal of our debugging time, as we would not have designed tank this way if we were programming imperatively with side-effects. We would have probably had a content variable for each tank maintained and would have increased or decreased its content with assignment statements right in the application. So, say the content has become negative due to a bad operation, most often, we wouldn't figure that out until much later. These bugs used to be difficult to find and very time consuming. The way that tank is designed here enables us to detect the error where it happens. I want to make it clear that this doesn't mean we were stupid before and with object orientation we have become smart. It simply means that we avoid the whole issue of forgetting to check for content having become instable, the object itself won't let you forget by throwing an exception.
So, it is very useful for tank objects to protect their content. We have achieved that by encapsulating data and methods, including exception handling mechanism that we created for tank in each instance/variable/object (any of those names are ok here) of class Tank.
We first talked about Inheritance when we discussed the exception handling features of Java. Recall that in Java we create exception classes such as TankOverFlowException that are subclasses of a super class called Exception. It is not hard to think of why super classes such as Exception are useful. For one thing, it provides uniformity to the way we handle abnormal cases. Any of our methods that throw an exception force the application that invokes them to catch that exception. This is something that if the application programmer forgets to deal with, he or she will be reminded with a compilation error. Since all exceptions are designed in similar fashion, we have a sense of familiarity when we look at new classes that throw them. That feeling of familiarity is part of the draw for object orientation, it prevails all over the place.
I like to introduce inheritance in a more significant way by introducing you to the concept of abstract vs. concrete classes. We will design a class hierarchy for queues that hold string objects. We will also have our first look at linked lists.
First off, regardless of how a queue is implemented, we are interested
in its FIFO behavior. Here we would like to be able to provide applications
the flexibility of choosing implementation at run time. To achieve this, we
will first design a class stringQueue.
public abstract class stringQueue {
public abstract boolean empty();
public abstract boolean full();
public abstract void enqueue(String x);
public abstract String dequeue();
}
A couple of things to note here:
Suppose we declare an object of stringQueue with a statement
such as, stringQueue q;. Understand the difference between
declaring and constructing. When we declare q, we simply say
that it will be a stringQueue. You can see that there is no constructor in
stringQueue, so, you can't say something like
stringQueue q = new stringQueue(...);. If
you think about it, it all makes sense--if you don't have any variables
in this class then what could you construct, what could you set?
Obviously, we need code in order for our q variable
to actually behave like a queue. We also need it to have some way of
storing the strings that we queue into it. This happens in concrete
classes that inherit stringQueue. Concrete refers to classes that have
code along with structures and variables that hold data.
fixedStringQueue class
fixedStringQueue class provides us with one implementation for stringQueue. This class will hold the strings in an array which is of a fixed length determined when a queue is constructed. There are plenty of applications where with reasonable certainty we can choose a fixed size for our queue. For example, in an operating system where we allow for time sharing, but have a limit on how many processes can actually run at the same time. It makes sense to have a fixed length queue for processes that are waiting to run. As processes come in, they go into the queue, when it is their turn, they get taken off the queue and get processed. If a process needs more time than the system is willing to give, they get processed for the duration that they can get, and go back to the queue and wait to be processed again. A queue implemented with an array works great in this case since we have a max limit on how many processes are allowed in the system at the same time, so you never have to worry about going beyond the fixed size.
There are several variations to array implementation of a queue. The easiest is to maintain a last index that holds the position of the last element. Each time enqueue is invoked, we increment last and place the new element there. When dequeue is invoked, we remove what is in the zero cell and move all elements back by one cell. However, we won't employ this method. We are going use a circular queue. In the previous method, note that the front of the queue is stationary, always in position zero. In a circular queue, we use a last and a first index. Each time enqueue is invoked, we change last to point to the next available space and place the new element there. Note that I said point to the next available space. When dequeue is invoked, we remove the element in front and move first to next occupied cell. The advantage in using the circular queue in place of the simple version discussed earlier should be obvious: in the simple version, every time you dequeue an element, the rest have to move back, no such movement is needed with a circular queue.
Moving to the next cell, in either enqueue or dequeue
may require to circle around to the beginning. Let me demonstrate with an
example. Assume This array of elements represents our queue with existing
content and values for the first and last indexes.
first=0 last=3
--------------------------------------------
| jones | morris | vax | fays | |
--------------------------------------------
0 1 2 3 4
Lets enqueue "new" into this queue.
first=0 last=4
--------------------------------------------
| jones | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
Lets dequeue one element from this queue. Note that you don't have
to physically remove "jones" from the array. You can assume that
"jones" is the string that we return from dequeue.
first=1 last=4
--------------------------------------------
| jones | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
Lets enqueue "circle" into this queue. Notice that we rap around
since we have no more cells on the right, but there is available space at
the beginning. It is strange to see last be behind first, but that is how
circular queues work.
last=0 first=1
--------------------------------------------
| circle | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
It is simple to implement, The private method next is written
to accomplish changing the two indexes in enqueue or dequeue.
private int next (int pos) {
if (pos == size-1)
return 0; // allow rap-around
else
return pos+1;
}
How is full determined? next(last) == first simply says that if last is moved to the next cell, it will run into the first.
There are a couple of other things for you to note. first and
last are set to -1 when queue is empty. The constructor
for the fixedStringQueue is parameterized to let the application set the
size that it wants. The statement q=new String[size];
creates the array q at run time using the size provided by the
application. Of course, this size is fixed for the life of the object
created.