Class Notes (807,078)
Canada (492,586)
ITI1521 (1)


29 Pages
Unlock Document

University of Ottawa
Information Technology
Nathalie J.

Abstract Data Type (ADT) - STACKS A stack is a linear data structure that is always accessed from the same extremity, one element at a time, and that element is called the top of the stack. Basic operations The basic operation of a stack are: Push: add an element onto the top of the stack; Pop: remove and returns the top element; Empty: tests if the stack is empty. public interface Stack { public abstract Boolean isEmpty(); public abstract E push(E o); public abstract E pop(); //returns the object at the top of this stack without removing it public abstract E peek(); } How would you implement this interface There are two popular families of implementation techniques - Array-based; - Using linked-nodes Stack s; s= new ArrayStack(); s= new DynamicArrayStack(); s= new LinkedStack(); Implementing a Stack using an array: ArrayStack The element of this stack are stored in the low part of the array, the bottom element is always located at the position 0 (convention), an instance variable is used to indicate the position of the top element in the array. Each time an element is pushed onto the stack, the value of the index top is incremented by one, the new element is added at that position. Each time an element is removed from the stack, the reference of the top element is stored in a temporary variable, the position of the array designated by top is set to null, the index is decremented by one, the element saved is returned. This is the preferred solution. It avoids copying the elements up or down for each insertion or removal. Copying elements would become progressively more expensive as the number of elements in the stack. public Boolean isEmpty() { return top==0; } public void push (E element) { //pre-condition: the stack is not full //stores the element at position top, then increments top Elems[top++] = element; } public E peek() { //pre-conditions: ! isEmpty() Return elems[top-1]; } public E pop() { //pre-conditions: ! isEmpty() //decrements top, then access the value E saved = elem[--top]; elems[top]=null; //”scrubing” the memory! Return saved; } Implementing a Stack using an array The current implementation has a major limitation, its size is fixed. Often, the number of elements to process is not known in advance. How would you circumvent this limitation? Allocate an array that will be sufficiently large for the most applications. What are the disadvantages of this approach? Most of the time, most of the allocated memory will not be used, the capacity can be exceeded; Solution: Dynamic array Implementing a stack using an array: Dynamic array When the array is full, a new bigger array is created, the elements from the current array are moved (copied) into the new one, finally, the new array replaces the current one. There are many strategies to increase the size of the array, two of them are: Let n and n’ be the size of the current and new array respectively, n’=n+c where c=1 for instance, or, n’=cn where c=2. Abstract Data Type (ADT) – STACKS Stack-based algorithms Infix  postfix (mentally) Successively transform, one by one, all the sub-expressions following the same order of evaluation that would normally follow to evaluate an infix expression. An infix expression l°r becomes lr°, where l and r are sub-expressions and ° is an operator. 9 / ( 2 x 4 – 5 )  9 / ( 2 4 x – 5 )  9 / 2 4 x 5 -  9 2 4 x 5 - / Evaluation a postfix expression (mentally) 9 2 4 x 5 - /  9 (2 4 x) 5 - /  9 (8) 5 - /  9 (8 5 -)  9 (3) /  (3) Abstract Data Type (ADT) – STACKS using linked elements We now consider a data structure that always uses the exact amount of memory required by the application. This data structure grows one element at a time without copying any elements. We will need to create “containers” such that each “container” will hold one element. Access to the first element will be fast, but the access to the subsequent elements will necessitate “traversing” the data structure up to the element of interest. Just like arrays, each element has a single predecessor and successor (except for the first and last elements). We say that the structure is linear. Unlike the arrays, this data structure will not be implemented with contiguous memory cells. public class Elem { public Object value; public Elem next; } Linked structures allow to: - Represent linear data structures such as lists, stacks and queues; - They always use the “right” amount of memory; - All this is made possible because of this self reference; the declaration of the next type Elem within the class Elem itself. A data structure such as the one we have just described is called a linked list, to be more precise this is a singly linked list because each node has a single link (the instance variable next). Linked data structures are an alternative to arrays to store a “collection of values”. Linked structures always use the required amount of memory; because each element is stored in its own “container” which we called Elem. Each container is linked to its successor with help of reference. public class Elem { public Object value; public Elem next; public Elem(Object value, Elem next) { this.value=value;; } } p = new Elem(“A”, null); q = new Elem(“B”, null);; p = new Elem(“A”, null); q = new Elem(“B”, p); These are appropriate statements. Elem is a nested class of the class LinkedStack. Although the visibility of the class is private, and the visibility of its instance variable is private, LinkedStack has access to the instance variables of Elem, because Elem is a nested class of LinkedStack. For now, all our nested classes will be “static”. Such classes can be used as if they were top level classes except that their definition is nested and the outer implementation has access to the implementation of the nested class. public class LinkedStack implements Stack { private static class Elem { private E info; private Elem next; private Elem(E info, Elem next){;; } } private Elem top; //Instance variable public boolean isEmpty() {…} public void push(T info) {…} public T peek() {…} public T pop() {…} public String toString() { String res = “[“; If(top!=null){ Elem p=top; res = res+p.value;; while(p!=null){ res=res+”,”+p.value;;} } res=res+”]”; return res; } } /** * Stack Abstract Data Type. A Stack is a linear data structure * following last-in-first-out protocol, i.e. the last element * that has been added onto the Stack, is the first one to * be removed. * * @author Marcel Turcotte */ public interface Stack { /** * Tests if this Stack is empty. * * @return true if this Stack is empty; and false otherwise. */ public abstract boolean isEmpty(); /** * Returns a reference to the top element; does not change * the state of this Stack. * * @return The top element of this stack without removing it. */ public abstract E peek(); /** * Removes and returns the element at the top of this stack. * * @return The top element of this stack. */ public abstract E pop(); /** * Puts an element onto the top of this stack. * * @param element the element be put onto the top of this stack. */ public abstract void push( E element ); } public class ArrayStack implements Stack { // Instance variables private E[] elems; // Used to store the elements of thisArrayStack private int top; // Designates the first free cell @SuppressWarnings( "unchecked" ) // Constructor public ArrayStack( int capacity ) { elems = (E[]) new Object[ capacity ]; top = 0; } // Returns true if this ArrayStack is empty public boolean isEmpty() { // Same as: // if ( top == 0 ) { // return true; // } else { // return false; // } return ( top == 0 ); } // Returns the top element of this ArrayStack without removing it public E peek() { // pre-conditions: ! isEmpty() return elems[ top-1 ]; } // Removes and returns the top element of this stack public E pop() { // pre-conditions: ! isEmpty() // *first* decrements top, then access the value! E saved = elems[ --top ]; elems[ top ] = null; // scrub the memory! return saved; } // Puts the element onto the top of this stack. public void push( E element ) { // Pre-condition: the stack is not full // *first* stores the eleme at pos top, then increments top elems[ top++ ] = element;} } public class LinkedStack implements Stack { private static class Elem { private T info; private Elem next; private Elem( T info, Elem next) { = info; = next; } } private Elem top; public boolean isEmpty() { return top == null; } public void push( E info ) { top = new Elem( info, top ); } public E peek() { return; } public E pop() { E savedInfo =; top =; return savedInfo; } } Handling errors Error handling is a general problem and modern languages offer solutions. In Java the mechanism is called Exceptions. Exceptions are objects. Exception IOException RuntimeException ArithmeticException IllegalArgumentException NumberFormatException IllegalStateException NullPointerException IndexOutOfBoundsException An error situation is modelled using an object of the class Throwable, or one of its sub- classes. The objects encapsulates the error message. The class Throwable declares the methods String getMessage() and void printStackTrace(). Declaring a reference of type Exception (it’s simply a class), Exception e; Creating an object of the class Exception (It’s simply a class) e= new Exception (“Houston, we have a problem!”); Throw statement: Throw expression Where expression is a reference to an object of the class Throwable, or one of its subclasses. When an Exception is thrown: - The statement or expression terminates abruptly - If uncaught, the Exception will cause the whole stack of method calls to unwind, i.e. each method call on the stack will terminate abruptly. If the exception is not caught the program (thread) will terminate and print a stack trace; - None of the statement or parts of the expression that follow the point where the exception was thrown are executed; - Following an exception the next statements to be ran will be those of a catch or finally block. If an exception is thrown, the statements of the first catch block that matches the exception are executed. Match means that the exception is of the specified type or a subtype of it. No other block will be executed. If no catch matches the exception it percolates outside the try block. Statements in the finally block are always executed. Blocks finally are used to close files, for example. “Catch” expressions must be as specific as possible int DEFAULT_VALUE=1; int value; try { value = Integer.parseInt(“a”);} catch (Exception e) { value = DEFAULT_VALUE;} The block above will catch any Exception type. However, the catch statement is not designed to handle any Exception, what should it do if a ClassNotFoundException occurred? It should let it percolate so that an enclosing block can catch it. Checked and unchecker exceptions A method that throws a “checked exception” must declare or handle the exception. Checked exceptions are used to force the caller to define a strategy for handling these exceptions (declare or catch). An example of a checked exception is IOException. Often used to deal with situations caused by external events: read/write error. Used in contexts where the caller can take actions to handle the error. Unchecked exceptions include NullPointerException and IndexOutOfBoundsException. Any method that declares a reference variable can potentially throw a NullPointerException. Similarly, any method that uses an array can potentially throw a IndexOutOfBoundsException. Under normal circumstances (unless there is a bug) these methods should not be throwing exceptions. Java does not require you to declare (or catch) unchecked exceptions Hangling Exceptions Methods that could potentially throw check exceptions must declare the exceptions - Catching an exception; - Declaring an exception (throws) A method can declare checked and unchecked exceptions: the declaration of unchecked exceptions is optional. public static void main(String[] args) throws IOException, FileNotFoundException, NullPointerException {…} Here, NullPointerException, an unchecked exception is optional. Creating New Exception Types Extends Exception or one of its subclasses. Extending Exception (or one of its subclasses, except the subclasses of RuntimeException) is creating a checked exception. Extending RuntimeException(or one of its subclasses) is creating a unchecked exception. public class MyException extends Exception{} public class MyException extends Exception{ public MyException() { super(); } Public MyException(String message) { Super(message); } } Why creating new types? To specialize an exception, or to add new implementation details. Because exceptions are caught selectively using their type (filter). Abstract Data Type (ADT) – QUEUES A queue is a linear abstract data type such that insertions are made at one end, called the rear, and removals are made at the order end, called the front. Queue are sometimes called FIFOs: First-in First-out. The two basic operations are: enqueue: adds an element to the rear of the queue; dequeue: removes and returns the element at the front of the queue. Elements of a queue are processed in the same order as they are inserted into the queue, here “a” was the first element to join the queue and it was the first to leave the queue: first-come, first-serve. Implementations Just like stacks, there are two families of implementations: - Linked elements; - Array-based; public interface Queue { public abstract Boolean isEmpty(); public abstract void enqueue(E o); public abstract E dequeue(); } Using linked elements public class LinkedQueue implements Queue { private static class Elem { private E value; private Elem next; private Elem(E value, Elem next) { this.value=value;; } public boolean isEmpty() {…} public void enqueue(T o) {…} public T dequeue() {…} } public class LinkedQueue implements Queue { private static class Elem { private T value; private Elem next; private Elem( T value, Elem next ) { this.value = value; = next; } } private Elem front; private Elem rear; public E peek() { return front.value; } public void enqueue( E o ) { Elem newElem; newElem = new Elem( o, null ); if ( rear == null ) { front = rear = newElem; } else { = newElem; rear = newElem; } } public E dequeue() { E result = front.value; if ( front != null & == null ) { front = rear = null; } else { front =; } return result; } public boolean isEmpty() { return front == null; } } public class ArrayQueue implements Queue { // Constant private static final int MAX_QUEUE_SIZE = 10000; // Instance variables private E[] elems; // stores the elements of this queue private int front, rear, size; @SuppressWarnings( "unchecked" ) public ArrayQueue() { elems = (E []) new Object[MAX_QUEUE_SIZE]; front = 0; rear = -1; size = 0; } // Instance methods public int size() { return size; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == MAX_QUEUE_SIZE; } public void enqueue( E elem ) { if ( rear == ( MAX_QUEUE_SIZE -1 ) ) { int j=0; for ( int i=front; i<=rear; i++ ) { elems[ j++ ] = elems[ i ]; } front = 0;
More Less

Related notes for ITI1521

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.