1. Recall that Advising has begun. Freshmen and Sophomores must sign up at http://www.cis.usouthal.edu/advising. Juniors, Seniors, and Graduate Students must sign up on the board in FCW 20. Time is running short. Advising for Juniors, Seniors, and Graduate students will only last for two weeks. After that time, even if you meet with an advisor, there will still be a block placed on your registration. So make sure you sign up soon. Advising for Freshmen and Sophomores will last for three weeks. Each Freshmen and Sophomore is assigned a particular week to be advised. You will be told what week you have been assigned when you sign up.
2. There are three scholarships and one fellowship available to deserving students. You can find applications in the main School of CIS office, FCW 20, or you can apply online at http://www.cis.usouthal.edu/scholarships/2000ScholarshipFellowship.html. The deadline has been extended until next Monday, April 10, 2000.
3. The Annual ACM Banquet will be held this year on the Battleship Alabama on April 22. The winners of the scholarships and fellowships will be announced at the banquet. The cost of the banquet until today is $22.50. After today the cost will be $25. The banquet will consist of a nice dinner and dancing after dinner on the Battleship. All students are encouraged to attend. If you need more information, you may contact the ACM Faculty sponsor, Dr. David Langan.

public class Stack {
   final int maxSize = 100;
   Object[] myStack = new Object[maxSize];
   Object delimiter = new String(";");
   int positionOfDelimiter;

   public Stack() {
      myStack[0] = delimiter;
      positionOfDelimiter = 0;
   }

   public Object peek() {
      return(myStack[0]);
   }

   public boolean empty() {
      return(myStack[0] == delimiter);
   }

   public int search(Object o) {
      int i = 0;

      while ((myStack[i] != o) && (i<=maxSize))
         i++;

      return(i-1);
   }

   public Object pop() {
      Object topOfStack = myStack[0];

      for (int i=0;i < positionOfDelimiter;i++)
         myStack[i] = myStack[i+1];

      positionOfDelimiter--;

      return(topOfStack);
   }

   public Object push(Object item) {
      for (int i=positionOfDelimiter+1;i>0;i--)
         myStack[i] = myStack[i-1];

      myStack[0] = item;

      positionOfDelimiter++;

      return(item);
   }         
}

Stack.java

This exercise was to let you examine how the Stack methods work and to reinforce the idea of abstraction. Notice that when you place this file in the same directory as ReversePolishNotation.java and recompile it it should work the same way. This is because the implementation of the methods is irrelevant to their use.

When you work with Stacks in your assignment you should use the predefined class.

Recall that Stacks are an example of a LIFO data structure since the last element in the Stack is the first element out of the stack. A Stack is important in programming for many reasons. It is not simply an intellectual exercise. One example is the Stack used by the interpreter when running a program. Recall that in the Throwable class we can print out a stack trace. This is because the interpreter uses a Stack to keep track of which line of code is has executed. We will see another example of the use of Stack when we look at recursion.

In many instances a Stack is not appropriate. For instance, consider lining up at a movie theather to buy tickets. It would not be appropriate for the last person to arrive to be the first one to buy a ticket. We need a data structure in which the first element added is the first element removed. This is called a Queue. It is named after the British way of describing a line. In Great Britain when people line up it is referred to as queueing up. A Queue is referred to as a FIFO data structure.

Unlike the Stack class, the Queue is not implemented for you. Therefore you must define and implement your own Queue class. Note the important methods that are natural to a queue.

Adding a new element to the queue is called enqueing.

Taking an element out of the queue is called dequeing.

We may also implement an empty method.

When implementing a Queue we may use either Vectors or Arrays. Recall that the drawback to using Arrays is that you must specify how large the Array is.

There is another concept that can be used to implement Queues. But for your assignment you must use either Vectors or Arrays.

Linked Lists

There is another very useful data structure called a Linked List. A linked list is a list of nodes each of which contains a reference or pointer to the next node in the list. The list will have a head which points at the first node in the list. The end of the list will be identified by a node which has a null reference. To accomplish a Linked List consider the following Class definition as found on page 507 of your text.

class Node {
   private Object datum;
   private Node link;

   public Node(Object item,Node pointer) {
      datum = item;
      link = pointer;
   }
}

Notice that is this definition we include a variable whose type is the class we're defining! For this reason this class is known as a self-referential structure.

We can use a self-referential structure to build a linked list.

Consider the following example.

Node head = null;

head = new Node("Fred",head);
head = new Node("Esther",head);
head = new Node("Lamont",head);

The following illustrates what is happening with each of these statements.

Node head = null;



head = new Node("Fred",head);



head = new Node("Esther",head);



head = new Node("Lamont",head);

---

Assignment 4

---