cs230 Lecture Notes
Week 7, Thursday

Homework 5 is due Today.

Quiz today that is (as promised) retrospective.

Homework 6 out today.  Due Thursday after break.

If you haven't finished Chapter 16, you should.


Quiz 6 Solutions
----------------





















Postfix
-------

Section 15.9

What is the value of the postfix expression 1 2 + 3 *




One of the nice things about postfix is that the order of
operations is completely specified, so there is no need
for parentheses.

1 2 + 3 *      is equivalent to (1 + 2) * 3


What is the postfix equivalent of the infix expression 1 + 2 * 3




There is a natural way to evaluate postfix expressions using
a stack.

1) Get the next term

   a) if it's an operand, push it
   b) if it's an operator, pop two operands, perform the
      operation, and push the result

2) At the end of the expression, there should be exactly
   one operand on the stack.  It's the result.


The Queue ADT
-------------

What are the operations that define the Queue ADT?

Syntax:

    public Queue () {
    public boolean empty () {
    public void insert (Object obj) {
    public Object remove () {

Semantics:

    the constructor makes an empty queue
    insert adds new elements to the queue
    remove removes and returns the element in the queue
       that was inserted first.

What is a queue good for?

1) keeping track of a list of tasks a program has to perform

   Example: event queues




Queue Implementation
--------------------

public class Queue {
    public LinkedList list;

    public Queue () {
        list = new List ();
    }

    public boolean empty () {
        return list.empty ();
    }

    public void insert (Object obj) {
        list.addLast (obj);
    }

    public Object remove () {
        return list.removeFirst ();
    }
}

In this case, each Queue object contains a LinkedList
object as an instance variable.

Then we can use LinkedList methods to implement Queue methods.

This is sometimes called a HAS-A relationship between classes:
the Queue class HAS-A LinkedList object.

An alternative is the IS-A relationship between classes, used
to describe inheritance.  More on this later.

This implementation could be called a veneer.

Veneers are generally a good thing, although they are
vulnerable to a PERFORMANCE HAZARD?

The problem here is that insert uses addLast, which is linear.

We should be able to do insert and remove in constant time.

The linked queue implementation solves this problem.
So does the circular buffer implementation.



Fire and brimstone
------------------

(from the syllabus)

In any class like this, it is difficult to draw a sharp line between
accceptable and unacceptable forms of collaboration.  Here are some
guidelines that might help:

1)  In general, it is acceptable to talk about programs using
natural languages, but not acceptable to use any formal language,
and especially not Java.  In other words, you should not be looking
at other people's code or showing them yours.

2) It is never acceptable to present someone else's
work as if it were your own.  Unless stated otherwise, I will assume
that all work you hand in is yours and yours alone.  If you work
with another student, you must acknowledge that student's contribution
in writing on your homework.  If you get help from me or a TA that
constitutes a significant part of the homework, you should acknowledge
that, too.  If you are not sure, err on the side of caution.

2) It is sometimes tempting to make
superficial changes to copied code to disguise it, but I should warn
you that (1) similarity between programs is often more obvious than
you think, and (2) an attempt to disguise cheating is evidence of
guilt, and is a more serious offense since it compounds plagiarism
with further deceit.

Your reputation for honesty is one of your most valuable assets.
If you lose it, you will find it very difficult to recover.
There is no grade that you will receive on any quiz, homework,
or exam, that is worth risking your reputation for honesty.