[DATA STRUCTURE & Other Objects Using JAVA] Chapter 7 Queue

stack vs. queue

7.1 Introduction to Queues

  • A queue is a data structure of ordered items such that items can be inserted only at one end (called the rear) and removed at the other end (called the front). The item at the from end of the queue is called the first item.
  • Because items must be removed in exactly the same order as they were added to the queue, a queue is call a first in/first out data structure (FIFO).
  • The only difference between stack and queue is the rule that determines which item is removed first.

7.1.1 The Queue Class

  • The method for adding an item to the queue is often called an insert or enqueue operation.
  • The method for removing an item from the queue is often called a getFront of dequeue operation.
  • If a program attempts to remove an item from an empty queue, that is a kind of error called queue underflow.
  • Java’s queue also provides two alternative methods, offer() and poll(), that a queue can use instead of add and remove.

7.1.2 Uses for Queues

  • Because queues occur in real-life situations, they are frequently used in simulation programs.
  • Queues also appear in computer system software, such as the operating system that runs on Pc.
  • Buffering data in a queue is often used when one computer component is receiving data from another faster computer component.

7.2 Queue Applications

7.2.1 Java Queues

  • Java does not actually have a separate Queue class.
  • Java has a Queu interface.
  • But there are several other Java classes that implement the Queue interface.
  • If you want a simple Java queue, consider using the Queue interface and the LinkedList class.

7.2.2 Palindromes

  • A palindrome is a string that reads the same forward and backward.
  • We treat both the uppercase and lowercase versions of a letter as being the same character.
  • The program only accepts alphabetic letters.

7.2.3 Car Wash Simulation (Skipped)

7.3 Implementations of the Queue Class

7.3.1 Array Implementation of a Queue

  • When a class requires some small computation that is likely to be used several times, consider implementing the computation with a helper method (that is, a private method).

Invariant of the ArrayQueue Class

  1. The number of items in the queue is stored in the instance variable manyItems.
  2. For a non-empty queue, the items are stored in a circular array beginning at data[front] and continuing through data[rear].
  3. For an empty queue, manyItems is zero and data is a reference to an array, but we are not using any of the array, and we don’t care about front and rear.

Specification

Implementation

7.3.2 Linked List Implementation of a Queue

Invariant of the LinkedQueue Class

  1. The number of items in the queue is stored in the instance variable manyNodes.
  2. The items in the queue are stored in a linked list, with the front of the queue stored at the head node and the rear of the queue stored at the final node.
  3. For a non-empty queue, the instance variable front is the head reference of the linked list of items, and the instance variable rear is the tail reference of the linked list.

Implementation

7.4 Deques and Priority Queues

7.4.1 Double-Ended Queues

  • Entries can be quickly inserted and removed at both ends.
  • The ends of the deque are called front and back, but these designations are arbitrary since the same operations can occur at both ends.
  • In Java, deques are an interface, java.util.Deque, that includes all of the queue interface plus additional methods such as addFirst and removeLast.

7.4.2 Priority Queues

  1. A priority queue is a data structure that stores items along with a priority for each item.
  2. Items are removed in order of priority.
  3. The highest-priority item is removed first.
  4. If several items have equally high priorities, then the one that was placed in the priority queue first is the one removed first.

7.4.3 Priority Queue ADT — Specification

7.4.4 Priority Queue Class — An Implementation That Uses an Ordinary Queue

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 6 Stacks

6.1 Introduction to Stacks

  • Stack is sometimes called a push down store.
  • A stack is a data structure of ordered items such that items can be inserted and removed only at one end.
  • Stack items must be removed in the reverse order of that in which they are placed on the stack.
  • LIFO: Last-in/first-out
  • Only the top item is accessible.
  • Adding an item to a stack is called a push operation and removing an item form a stack is called a pop operation.

6.1.1 The Stack Class — Specification

  • Ge the top item of this stack without removing the item.

  • Stack underflow: If a program attempts to pop an item off an empty stack, it is asking for the impossible; this error is called stack underflow, which will throw an EmptyStackException.

6.1.2 Programming Example: Reversing a Word

  • Stack is surprisingly useful:

    • Most compilers use stacks to analyze the syntax of a program.
    • Stacks are used to keep track of local variables when a program is run.
    • Stacks can be used to search a maze or a family tree or other types of breaching structures.

6.2 Stack Application

6.2.1 Programming Example: Balanced Parenthesis

  • Every time a left parenthesis occurs, it is pushed onto the stack.
  • Every time a right parenthesis occurs, a matching left parenthesis is popped off the stack.
  • If all goes smoothly and the stack is empty at the end of the expression, then the parenthesis match.

6.2.2 Evaluation Arithmetic Expression

Evaluation Arithmetic Expression — Design

(((6 + 9) / 3) * (6 – 4))

  • Evaluate the leftmost of the innermost expression repeatedly
  • The end of the expression to be evaluated is always a right parenthesis ‘)’, and moreover it is always the first right parenthesis.
  • The next right parenthesis will indicate the end of the next expression to be evaluated.
  • Whenever we reach a right parenthesis, we combine the top two numbers (on the number stack) using the topmost operation (on the character stack).

Something About Java Scanner

  • The expression input.hasNext(UNSIGNED_DOUBLE) is true if the next part of the input expresso is a double number.
  • The expression next = input.findInLine(UNSIGNED_DOUBLE) sets the stringnext equal to the next part of the input expression, which must a double number.
  • The expression next = input.findInLine(CHARACTER) sets next equal to the next single character (skipping spaces) in the input expression.

Evaluation Arithmetic Expression — Implementation

Evaluation Arithmetic Expression — Testing and Analysis

The algorithm for the program is O(n).

Evaluation Arithmetic Expression — Enhancements

  • Permit expression that are not fully parenthesized
  • Use the Java precedence rules to decide the order of operations when parentheses are missing

6.3 Implementations of the Stack ADT

6.3.1 Array Implementation of a Stack

Invariant of the ArrayStack Class

  1. The number of items in the stack is stored in the instance variable manyItems.
  2. The items in the stack are stored in a partially filled array called data, with the bottom of the stack at data[0], the next item at data[1], and so on, to the top of the stack at data[manyItems-1].

Specification

6.3.2 Linked List Implementation of a Stack

Invariant

  1. The items in the stack are stored in a linked list, who the top of the stack stored at the head node, down to the bottom of the stack at the final node.
  2. The instance variable top is the head reference of the linked list of items.
  3. Because we are using a linked list, there are no capacity worries.

Specification

Since we are using linked list here, we do not need method to maintain correct size.

6.4 More Complex Stack Applications

6.4.1 Evaluating Postfix Expressions

  • Infix Notation: 2 + 3
  • Prefix Notation (Polish Prefix Notation): * + 2 3 7 = (2 + 3) * 7
  • Postfix Notation (Polish Postfix Notation) (Reverse Polish Notation): Write the operations after the two numbers being combines. 2 3 + 7 *
  • In Reverse Polish Notation, an operation is applied to the two numbers that are immediately before it. 7 3 5 * + 4 = 7 + (3 * 5)
  • Do not intermix prefix and postfix notation.
  • Postfix notation is handy because it does not require parentheses and because it is particularly easy to evaluate.
  • Each operation is used as soon as it is read.
  • Each time an operation appears in the input, the operands for the operation are the two most recently seen numbers.
  • Sometimes the “most recently seen number” is not actually an input number; instead, it is a number that we computed and pushed back onto the stack.
  • When the input is exhausted, the number remaining in the stack is the value of the entire expression.

6.4.2 Translating Infix to Postfix Notation

  • One strategy for evaluating an ordinary infix expression is to first convert it to postfix notation and then evaluate the postfix expression.
  • If the infix expression is fully parenthesized, all that’s needed to convert from infix to postfix is to move each operation symbol to the location of the right parenthesis corresponding to that operation and then remove all parenthesis.
  • The operands in the equivalent postfix expression are in the same order as the operands in the corresponding infix expression we start out with.

6.4.3 Using Precedence Rules in the Infix Expression

  • In practice, infix expressions are usually not fully parenthesized, and the computer must rely on precedence rules to determine the order of operations for the missing parentheses.
  • Operations of equal precedence are performed in left-to-right order.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 9 Trees

9.0 Introduction

  • Tree is a nonlinear structure.
  • The nonlinear structure often allows dramatically improved efficiency for collection classes.

9.1 Introduction to Trees

9.1.1 Binary Trees

A binary tree is a finite set of nodes. The set might be empty (no nodes, which is called the empty tree). But if the set is not empty, it follows these rules:

  1. There is one special node, called the root
  2. Each node can be associated with up to two other different nodes, called its left child and its right child. If a node c is the child of another node p, then we say that “p is c’s parent“.
  3. Each node, except the root, has exactly one parent; the root has no parent.
  4. If you start at a node and move to the node’s parent (provided there is one), and then move again to that node’s parent, and keep moving upward to each node’s parent, you will eventually reach the node.

Terminologies

  • Sibling: Two nodes are siblings if they have the same parent.
  • Ancestor: A node’s parent is its first ancestor. The parent of the parent is the next ancestor and so on.
  • Descendant: A node’s children are its first descendants. The children’s children are its next descendants and so on.
  • Subtree: View a node as root. Subtree includes this node and nodes below.
  • Left and Right Subtrees of a Node: The nodes beginning with its left child and below are its left subtree. The nodes beginning with its right child and below are its __right subtree.
  • Depth of a Node: The number of steps for a node to move upward to reach the root.
  • Depth of a Tree: The depth of a tree is the maximum depth of any of its leaves. If a tree has only one node, the root, then its depth is zero. The empty tree doesn’t have any leaves, so we use -1 for its depth. height = depth.
  • Full Binary Trees: In a full binary tree, every leaf has the same depth, and every non-leaf has two children.
  • Complete Binary Trees: To be a complete tree, every level except the deepest must contain as many as nodes as possible; and at the deepest level, all the nodes are as far left as possible.

9.1.2 Binary Taxonomy Trees

  • Binary taxonomy trees can be used to store certain kinds of knowledge.
  • Computer scientists use the term decision tree for this kind of tree with yes/no question at each non-leaf node.

9.1.3 More Than Two Children

  • In general, a node in a tree can have any number of children.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 5 Generic Programming

5.1 Java’s Object Type and Wrapper Classes

  • Java has an important built-in data type called Object. AnObject variable is capable of holding a reference to any kind of object.

5.1.1 Widening conversion

Suppose x and y are reference variables. An assignment x = y is a widening conversion if the data type of x is capable of referring to a wider variety of things than the type of y.

5.1.2 Narrowing conversion

Suppose x and y are reference variables, and x has a smaller ability to refer to things than y. A narrowing conversion using a typecast can be made to assign x from y.

Narrowing conversions also occur when a method returns anObject and the program assigns that Object to a variable of a particular type.

5.1.3 Wrapper Classes

  • Wrapper class: A wrapper class is a class in which each object holds a primitive value.
  • Boxing conversion: placing an integer into an Integer object.
  • Unboxing conversion: taking back out an integer form an Integer object.

5.2 Object Methods and Generic Methods

Object Methods

There are some potential type errors that can’t be caught until the program is running.

Generic Methods

A generic method is a method that is written the types of the parameters not fully specified.

  • T is called the generic type parameter.
  • Single capital letters such as T for “type”, and E for “element”.
  • The generic type parameter always appears in angle brackets right before the return type of the method.
  • When a generic method is activated, the compiler infers the correct class for the generic type parameter.
  • A generic method allows any class for the argument, and the compiler can detect certain type errors.
  • The generic type parameter is similar to id in Objective-C.
  • Generic methods with more than one generic type parameter.

  • The data type inferred by the compiler for the generic type must always be a class type.

  • You may not call a constructor for the generic type, nor may you create a new array of elements of that type.

5.3 Generic Classes

5.3.1 Writing a Generic Class

When an entire class depends on an underlying data type, the class can be implemented as a generic class, resulting in the same typechecking advantages that you have seen for generic methods.

  • The single capital letter ‘E’ indicates that it is the unknown class of an “element” in the bag.
  • Programs cannot creates arrays where the components are the generic type parameter.

5.3.2 Using a Generic Class

  • A program that wants to use a generic class must explicitly specify what class will be used for the generic type parameter. This process is called instantiating the generic type parameter.

  • You cannot add a String object to a bag of Integer objects.

5.3.3 Creating an Array to Hold Elements of the Unknown Type

  • Within the generic class implementation, we are not allowed to create a new array of objects of the unknown type E.
  • The solution is to declare data as an array of Java Objects.

5.3.4 Retrieving E Objects from the Array

Whenever we retrieve a component of the array, we must apply a typecast to the type E.

This typecast (E) is one of several places where Java compilers issue warnings about possible errors that can occur at run time.

5.3.5 Warning in Generic Code

Typecasts

During the runtime, the information about the actual data type of a generic object is always unavailable. Therefore there is no way for the program to check whether the typecast is correct. The warning that Java produces in this situation is an “unchecked cast” warning. This means that if the typecast is illegal at run time, then the error will not be caught as it usually is.

Variable Arity Methods

Variable arity methods will cause the compiler to create an array of generic object, which usually is forbidden because it can result in unchecked typecast errors.

Suppressing Unchecked Warnings

There is no semicolon after this annotation, and the line can be placed by itself just prior to any method declaration.

  • Available since Java 1.7
  • It can suppresses both warning at the declaration of the variable arity method and the warning that sometimes occur when the variable arity method is activated.
  • Only available to static or final methods.

5.3.6 Using ArrayBag as the Type of a Parameter or Return Value

All the uses of the ArrayBag data type within its own implementation will be written as ArrayBag<E>.

5.3.7 Generic Collections Should Use the equals Method

When a generic collection tests for the presence of a non-null elements, it should generally use the equals method rather than the == operator.

5.3.8 Set Unused Reference to null

When a collection class is converted to a generic collection class, make sure any unused reference variables are set to null. This usually occurs in methods that remove elements from the collection. Setting these variables to null will allow Java to collect any unused memory.

5.3.9 Steps for Converting a Collection Class to a Generic Class

1. The Name of the Class

  • Convert all IntArrayBag to ArrayBag<E>.
  • The name of the constructor is just ArrayBag.

2. The Type of the Data Array

3. The Type of the Underlying Element

Find all the remaining spots where the old classes used int to refer to an element in the bag, and change them to the generic type parameter.

4. Change Static Methods to Generic Static Methods

Any static method that depends on the generic type E must be changed to a generic method, which means that <E> appears just before the return type in the method’s heading.

5. Use Typecasts When an Element Is Retrieved from the Array

return (E)data[i];

6. Suppress Warning

Some code in generic collection classes generates “unchecked” warnings. Examine each of these spots and suppress the warning.

7. Updated Equality Tests

Use the method equals() instead of ==.

8. Decide How to Treat the null Reference

  • Allow the null reference to be placed in the bag, and indicate this in the documentation.
  • Some of the bag’s methods will need special cases to deal with null references.
  • Such as the countOccurrences() will search for a null target using “==”, but non-null target is counted by using its equals method.

9. Set Unused Reference Variable

10. Update All Documentation

5.4 Generic Nodes

  • In general, the equals method may be used only when you know that the target is non-null.
  • When the purpose of a boolean expression is to test whether two references refer to the exact same object, then use the “==” or “!=” operator.

5.5 Interfaces and Iterators

  • A Java interface is primarily a list of method that a programmer may want to implement in a single class.
  • A class that has implemented the methods of a interface is said to implement the interface.

5.5.1 How to Write a Class That Implements an Interface

1. Read the documentation that is provided for the interface.

2. Tell the compiler that you are implementing an interface.

  • The keyword implements informs the compiler that you are implementing the interface.
  • If a class implements several difference interfaces, then the names of the interface appear one after another, separated by comma.

3. Implement the class in the usual way.

Make sure that each of the specified methods is implemented.

5.5.2 Generic Interfaces and the Iterable Interface

  • A generic interface specifies a list of methods that depend on one or more unspecified classes.
  • Interface Iterator<E>

  • remove() removes the element that was given by the most recent call to next().

  • Sometimes an iterator does not allow elements to be removed. In this case, activating the remove() method results in an UnsupportedOperationException.

5.5.3 The Comparable Generic Interface

  • Java has a generic interface called Comparable<T> that requires just one method:

  • x.compareTo(y): The method returns an integer that is negative (if x is less y), zero (if x and y are equal), or positive (if x is greater than y).

5.5.4 Parameters That Use Interfaces

When an interface name is used as the type of a method’s parameter, the actual argument must be a data type that implements the interface.

5.5.5 Using instanceof to Test Whether a Class Implements an Interface

variable instanceof interface-or-class-name

5.5.6 The Cloneable Interface

  • There are no methods specified in the Cloneable interface. (What the fuck?!)
  • object.clone()

    1. Check to see whether the class has implemented the Cloneable interface. If not, a CloneNotSupportedException is thrown.
    2. Otherwise, the clone is make by copying each of the instance variable of the original.

5.7 The Java Collection Interface and Map Interface

Map: A map is a collection class in which key/value pairs may be added. A pair can be retrieved or removed by specifying just its key. This is similar to NSDictionary in Objective-C.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 2 Java Classes and Information Hiding

2.0 Introduction

  • Object-oriented programming is an approach to programming in which data occurs in tidy packages called objects.
  • The separation of specification from implementation is an example of information hiding.
  • ADT (abstract data type): In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. (from wikipedia)

2.1 Classes and Their Members

  • Member: Taken together, the data (instance variables), constructors, and methods of a class are called the class members.
  • class head: consists of the Java key word public class followed by the name of the new class.

  • Always use a capital letter for the first character of names of new classes.

  • public & private

2.1.1 Constructors

  • Before any constructor begins its work, all instance variable are assigned Java “default values” which is zero.
  • The name of a con structure must be the same as the name of the class.
  • A constructor is not really a method, and therefore it does not have any return value.
  • Some classes may have more than one constructor, and those constructors are distinguished by distinct sequence of parameters.

2.1.2 No-Arguments Constructors

  • no-argument constructor: a constructor with no argument
  • If you write a class with no constructs at all, then Java automatically provides a non-arguments construct that initializes each instance variable to its initialization value or its default value.

2.1.3 Methods

  • Accessor method: It gives information about an object without altering the object.
  • Modification method: It can change the status of an object.
  • Accessor method often have no parameters, no precondition, and only a simple return condition in the specification.

Why private and accessor method?

  1. Don’t need to know how the class is implemented (don’t need to know what instance variable the class has, only need to know public functions)
  2. Programs use the class will still work when the implementation of class is changed, because the accessor methods are not changed.
  3. It is easy to test the accessor method, which makes the class more reliable.
  4. The pattern of “private data, public method” is able to forbid other programmers from using instance variables in unintended ways (such as setting numberOfPeople to negative).
  • Modification methods are usually void, meaning there is no return value. Most modification methods have parameters.
  • Arithmetic overflow: trying to compute or store a number that is beyond the legal range of the data type.
  • The name of the Java file must match the name of the class.

2.2 Using Class

2.2.1 Creating and Using Objects

  • Call a method = activate a method
  • When a program has several objects of the same class, each object has its own copies of the class’s instance variable.
  • Reference variable: used to refer to objects

2.2.2 Null Reference

  • Null reference: Sometimes a reference variable does not refer to anything. This is a null reference, and the value of the variable is called null.

NULLPOINTEREXCEPTION

If a variable is null, then it is a error to activate a method of it. However, it is fine to send message to NULL in Objective-C, which does nothing.

2.2.3 Assignment Statements with Reference Variables

  • If t1 and t2 are reference variables, then the assignment t2 = t1 is allowed.
  • If t1 is null, then the assignment makes t2 null also.
  • It t1 is not null, then the assignment changes t2 so that it refers to the same object that t1 already refers to. At this point, changes can be made to that one object through either t1 or t2.

2.2.4 Clone

  • Clone: A separate copy is a copy of the original object which should not alter the original, nor should subsequent changes to the original alter the copy. (Deep copy)

2.2.5 Test for Equality with Reference Variables

For reference variable t1 and t2, the test (t1 == t2) is true if both references are null or if t1 and t2 refer to the exact same object.

2.3 Packages

2.3.1 Declaring a Package

  • Using the Internet domain name in reserve as a prefix to name package

  • Package declaration

  • Place the package at the right place

    1. Suppose the pwd is a folder called classes.
    2. Underneath the classes directory, crate a subdirectory called com.
    3. Underneath comm, create a subdirectory called brucedsu.
    4. Underneath bruecedsu, create a subdirectory called PACKAGE_NAME
    5. All the .java and .class files for the package mush be placed in the PACKAGE_NAME subdirectory.

2.3.2 The Import Statement to Use a Package

‘*’ means import all classes.

Only import the class called ‘CLASS_NAME’.

2.3.3 The JCL Packages

  • JCL: Java Class Libraries
  • Package java.lang is so useful that is automatically imported into every Java program.

2.3.4 More about Public, Private, and Package Access

  • Access modifiers: The keywords public and private are called the access modifiers because they control access to the class members.

2.4 Parameters, Equals Method, and Clones

2.4.1 Static Method

  • The static keyword means that the method is not activated by any one object.

2.4.2 Parameters That Are Objects

  • When a parameter is an object, then the parameter is initialized so that it refers to the same object that the actual argument refers to.
  • Double.Nan: a constant that a program uses to indicate that a double value is “not a number”.
  • Double.POSITIVE_INFINITY
  • Double.NEGATIVE_INFINITY

2.4.3 Methods May Access Private Instance Variables of Objects in Their Own Class

A method may access private instance variables of an object as long as the method is declared as part of the same class as the object.

2.4.4 How to Choose the Name of Method?

Accessor Methods

  • The name of a boolean accessor method will usually begin with “is” followed by an adjective, such as isOn().
  • Methods that convert to another kind of data start with “to”, such as toString().
  • Other accessor method start with ‘get’ or some other verb followed by a noun that describes the return value, such as getFLow().

Modification Methods

A modification method can be named by a descriptive verb, such as shift(), or a short verb phrase, such as shutOff().

Static Methods that Returns a Value

Try to use a noun that describes the return object, such as distance() or midpoint().

2.4.5 Java’s Object Type

In Java, Object is a kind of “super data type” that encompasses all data except the eight primitive types (byte, short, int, long, float, double, boolean, char). In Objective-C, NSObject is the “super data type”.

2.4.6 Using and Implementing an equals() Method

  • When p itself is null, it is a programming error to activate any method of p. Trying to activate any method when p is null results in a NullPointerException.
  • instanceof: is an boolean operator. On the right of the operator is a class name, such as Location. The test returns true if it is valid to convert the object to the given data type.
  • To avid ClassCastException use instanceof first. In Objective-C, use isKindOfClass(__unsafe_unretained Class).

2.4.7 Implementing a clone() Method

1. Modify the Class Head

Add the words “implements Cloneable” in the class head. Just like conforms to protocol in Objective-C.

2. Use super.clone() to Make a Copy

super.clone() is actually clone() method from Java’s Object type.

This exception is thrown by the clone() method from Java’s Objet type when a programmer tries to call super.clone() without including the implements Cloneable clause as part of the class definition.

3. Make Necessary Modification and Return

2.4.8 Java Parameters

  • The eight primitive types: The parameters is initialized with the value of the argument. Subsequent changes to the parameter do not effect the argument.
  • Reference variables: When a parameter is a reference variable, the parameter is initialized so that it refers to the same object as the actual argument. Subsequent changes to this object do affect the actual argument’s object.