CIS 121 March 29, 2000
Recall that our exam is tomorrow. You are guaranteed to have at least one
programming problem on each of the following topics:
- Detecting and acting on button clicks
- Detecting and acting on a checkbox event
- Drawing graphics
Make sure you review these.
Next week Advising will begin. Freshmen and Sophomores must sign up for an
appointment at http://www.cis.usouthal.edu/advising.
Juniors, Seniors, and
Graduate Students must sign up for an appointment in FCW 20. Advising is
mandatory for all students, and any student which is not advised during
this period will be blocked from Phase I Registration. They will not be
able to register until their block is cleared, and by that time most of
the courses you may want or need may be full. So make sure that you get
advised.
Data Structures
Today we will begin talking about Data Structures.
A data structure is a collection of data consisting of primitive data
items, such as int and float, and other data structures. We associate this
collection with operations that are performed on this collection. So the
concept of a Java class is well-suited for data structures.
We have already seen an example of a data structure when we looked at
arrays. Arrays are a collection of data items, each of the same type. The
programmer implements the operations of add and delete.
We will first examine two other common data structures, Stacks and Queues.
Stacks
To visualize the concept of a stack, considered plates in a restaurant.
When a plate is cleaned it is placed on top of a collection of other
plates. When a customer needs a plate, they will take the one off the top
unless there are no plates left. The customer can also look at the plate
without taking it. The customer can also search through the plates until
they find the one that they want and note its position.
Note the operations that have been performed on this collection of plates.
When the staff places a clean plate on the stack, this is called a
push operation.
When the customer takes a plate off the top of the stack, this is called a
pop operation.
When the customer examines the stack to see if there are any plates, he
is using a boolean operation, empty.
When the customer looks at the plate on the top of the stack but doesn't
take it, this is called a peek operation.
When the customer searches through the stack to find the position of a
plate, this is called a pop operation.
There is a predefined class in the java.util package that implements these
methods. The interface of this class is
public class Stack extends Vector {
public Stack();
public boolean empty();
public Object peek();
public Object pop();
public Object push(Object item);
public int search(Object o);
}
Notice that the last object pushed onto the stack will be the first one
popped off. Because of this stacks are known as LIFO data
structures, Last In First Out.
As an important and useful example of using stacks, consider the problem
of Reverse Polish Notation.
Normally when we write arithmetic expressions, we write them in a form
similar to a+b. This is called infix notation since the operator is
between the operands. Another way of writing this arithmetic expression is
postfix or Reverse Polish Notation, named after the nationality of Jan
Lukasiewicz who developed the notation. In Reverse Polish Notation, the
operator is written after the operands. So the above example in
Reverse Polish Notation would be ab+. If you have an HP calculator
you will be familiar with Reverse Polish Notation.
In order to convert infix notation to Reverse Polish Notation it is
helpful to use a stack. In order to accomplish this, let us first make
some elementary rules.
We surround our expression with [ and ], and establish the following
priority system of operations.
| Operator |
Priority |
| [ |
0 |
| { |
1 |
| - |
2 |
| + |
2 |
| / |
3 |
| * |
3 |
| ^ |
4 |
To convert infix notation to Reverse Polish Notation we use the following
algorithm found on page 529 of your book.
for every character in the infix expression
if next character is closing parenthesis ')'
pop operator from stack
while operator not opening parenthesis '('
store operator in string buffer
pop operator from stack
else if next character is closing bracket ']'
pop operator from stack
while operator not opening bracket '['
store operator in string buffer
pop operator from stack
else if next character is opening parenthesis '(' or opening bracket '['
push next character on to stack
else if next character is arithmetic operator
while priority of next character is <= priority of stack top operator
pop operator from stack
store operator in string buffer
push next character on to stack
else
store next character in string buffer
Let's look at some examples of how this algorithm works and on Friday we
will look at the code to accomplish it.