April 9th 2014 public class Lecture5 MaxSum to find maximum sum n n 3 2 n 2 n 3 n 3 8 3 n 3 n 3 n 3 27 2nd try we ve eliminated a whole inner for loop GOOD n n 2 2 n 2 n 2 n 2 4 3 n 3 n 2 n 2 9 public static int maxSum1 int a int max 0 for int start 0 start a length start int sum 0 put this here instead for int stop start stop a length stop int sum 0 elements from a start to a stop sum a stop for int i start i stop i sum a i if sum max max sum return max 1 Stacks and queues some collcetions ar constrained so clients can only use optimized operations stack retreives elements in reverse order as added vertical can only touch the top Two operations add or remove at the top queue retreives elements in same order as added horizontal has front and back allowed two operations adding to the back and removing from the front 2 Abstract Data Types ADTs abstract data type ADT A specification of a collection of data and the operations that can be performed on it Describes what a collection does how it does it 3 Stacks collection based on the principle of adding elements and retrieving them in the opposite order last in first out LIFO elements are stored in order of insertion we do not think of them as having indexes client can only add remove examine the last element added the top basic stack operations push add an element to the top pop remove the top element peek examine the top element 4 Stacks in comp sci Programming languages and compilers method calls are placed onto a stack call push return pop compilers use stacks to evaluate expressions matching up related pairs of things find out whether a string is a palindrome examine a file to see if its braces match convert infix expressions to pre postfix Sophisticated algorithms searching through a maze with backtracking many programs use an undo stack of previous operations 5 Class Stack Stack E constructs a new stack with elements of type E push value places given value at top of stack pop removes top value from stack and returns it throws EmptyStackException if stack is empty peek returns top value from stack without removing throws EmptyStackException if stack is empty size number of elements in stack isEmpty sees if the stack is empty 6 Class Queue retrieves elements in the order they were added first in first out FIFO elements are stored in order of insertion but don t have indexes client can only add to the end of the queue and can only examine remove the front of the queue 7 Queues in comp sci operating systems queue of print jobs to send to the printer queue of programs processes to run queue of network data packets to send programming modeling a line of customers or clients storing a queue of computations to be performed in order 8 Queue methods add value palces given value at back of queue remove removes value from front of queue and returns it throws a NoSuchElementException if empty peek returns value of the first in line without removing size number of elements in queue isEmpty sees if queue is empty Queue Integer q new LinkedList Integer HAVE TO DO new LinkedList public class StackQueueDemo public static void main String args Stack String tas new Stack String tas push Max bottom tas push Andrew tas push Molly top System out println tas Max Andrew Molly System out println tas pop pops Molly System out println tas Max Andrew Stack traversal while loops while tas isEmpty System out println tas pop pop returns the value it popped removes it as well Queue String tas2 new LinkedList String tas2 add Max front tas2 add Andrew tas2 add Molly back System out println tas2 Max Andrew Molly System out println tas2 remove Max System out println tas2 Andrew Molly 9 Wrapper classes primitive type int double char boolean wrapper type Integer Double Character Boolean Wrapper objects have a single field of a primitive type Collection can be used with familiar primitives Post stack is UNCHANGED Save values into a new stack then bring it back public static int max Stack Integer nums int max 0 while nums isEmpty int value nums pop can store int in an Integer if value max max value return max