04 Lists Stacks
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 04 Lists Stacks as PDF for free.
More details
- Words: 1,115
- Pages: 19
Lecture Program • Bags • Sets • Lists • Stacks • Queues
1
Making an ADT Import java.util.Iterator; public interface BoxADT{ public boolean add(T item); // Add an item to the box public T remove(); // Remove any item from the box public Iterator iterator(); // Return an iterator for the box public boolean contains(T item); // Does the box contain this item? public boolean isEmpty(); // Is this box empty? public int size(); // How many items in the box? public boolean equals (BoxADT otherBox); // Does this box equal otherBox public String toString(); // Represent this box as a String. } 2
Using our BoxADT … BoxADT <String> toyBox; toyBox = new BoxImp<String>(); toyBox.add(“Car”); toyBox.add(“Plane”); toyBox.add(“Fred”); System.out.println(toyBox.contains(“Barbie”)); System.out.println(toyBox.contains(“Fred”));
What does this print?
while(toyBox.size()) System.out.println(toyBox.remove()); System.out.println(toyBox.contains(“Barbie”)); …
3
Bag ADT • Bag is a collection with • no structure or order maintained • no access constraints (access any item any time) • duplicates allowed
• Minimal Operations: • add(value) • remove(value) → returns true iff value removed • contains(value) → returns true iff value is in bag • findElement(value) → returns matching item iff in bag 4
Bag Applications • When to use a Bag? • When there is no need to order a collection: • A collection of user preferences. • A collection of interchangeable items (worker threads in a web server). •… • Even though a bag is unordered, the implementation may order the data for efficiency. • Such observed ordering must not be relied upon.
5
Set ADT • Set is a collection with: • no structure or order maintained • no access constraints (access any item any time) • Only property is that duplicates are excluded
• Operations: • add(value) → true iff value was added (ie, not duplicate) • remove(value) → returns true iff value removed (was in set) • contains(value) → returns true iff value is in the set • findElement(value) → returns matching item iff in value in the set •…
• When do we use a Set instead of a Bag? What
6
List ADT • Lists are: (Example ToDoList) • Sequence of values • Allows access at any position in the List • Allows items to be inserted and removed Some operations: • add(value) inserts value at the end • add(index, value) inserts value at the specified index • get(index) returns value at the specified index • set(index, value) replaces value at index by new value (and returns old value) • remove(value) removes value (first occurrence only) • remove(index) removes value at index (and returns old value) • size() returns number of values • isEmpty() true iff no values 7
Constructing Lists • Declaring a List: specify the type of the value • List<String> myFriends; • List allPrimes; • List<Shape> drawing;
• Constructing a List: specify implementation and type of value: • myFriends = new LinkedList<String>(); • allPrimes = new Vector(); • drawing = new ArrayList<Shape>(); 8
Example: TodoList • TodoList – collection of jobs, in order they should be done. • Collection type: List of jobs, (jobs represented by a String) public class TodoList implements ActionListener{ : private List<String> myJobs; : public void readJobs(){ try { myJobs = new ArrayList<String>();
}
Scanner sc = new Scanner(new File("myJobs.txt")); while ( sc.hasNext() ){ myJobs.add(sc.next()); } sc.close(); displayJobs(); 9
More TodoList: public void actionPerformed(ActionEvent e){ if (e.getActionCommand().equals("Add") ){ myJobs.add(askJob()); } else if (e.getActionCommand().equals( "AddAt" ) ){ String job = askJob(); myJobs.add(askIndex("add at"), job); } else if (e.getActionCommand().equals("Remove") ){ myJobs.remove(askJob()); } else if (e.getActionCommand().equals("RemoveFrom") ){ myJobs.remove(askIndex("from"));
10
Rest of the example: public void displayJobs(){ textArea.setText("Jobs to be done\n"); int num = 0; for(String job : myJobs){ textArea.append((num++) + " " + job + "\n"); } };
• Note the odd for (EACH) loop (NICE): • For (type variable : Collection object ){ • Means to do the body of the loop for each value in the collection • Applies to all Collection types (except Map)
• Standard (original) Alternative:
for (int i=0; i<myJobs.size(); i++){
11
List vs Array • Lists are nicer than arrays: • No size limit!!! They grow bigger as necessary • but, slower to execute. • Lots of code written for you: • jobList.set(ind, value) • jobList.get(ind) • jobList.size() • jobList.add(value)
jobArray[ind] = value jobArray[ind] ? (Not the length!!!) ? (Where is the last value? What happens if it’s full?) • jobList.add(ind, value) ? (Have to shift everything up!!!) • jobList.remove(ind) ? (Have to shift everything down!!!) • jobList.remove(value) ? (Have to find value, then shift things down!!!) • for (String job : jobList) for(int i = 0; i< ???; i++){ String job = jobArray[ i ];
12
Stack ADT • Stack is a special kind of List: • A sequence of values, • Constrained access → to the top of the stack only.
• Operations: • • • •
push(value): pop() peek(): …
→ Put value on top of stack → Removes and returns top of stack → Returns top of stack, without removing
13
Stacks Example • Reversing the items from a file: • Read and push onto a stack • Pop them off the stack Public void reverseNums(Scanner sc){ Stack myNums = new Stack(); while(sc.hasNext()) myNums.push(sc.nextInt()) while(! myNums.empty()) textArea.append(myNums.pop() + “\n”); } 14
Applications of Stacks • Programs that deal with programs • Eg, program execution: call stack/activation stack, • Eg, expression execution, • (6 + 4) * ((8 * (6 – 2)) – (7 * 3))
• Processing files of structured data. • Eg reading files of with structured markup (HTML, XML,…)
• Undo in editors. • Assignments: • #2: reading and checking XML files • #3: an Undo stack for MiniDraw 15
Evaluating Expressions • (6 + 4) * ((8 * (6 – 2)) – (7 * 3))
16
Queue ADT • Queues are like Stacks • Sequence of values • Constrained access, but: • Add at the back • Remove from the front
• Operations: • offer(value): • poll() • peek(): removing
→ Adds value to end of queue → Removes and returns front of queue → Returns front of queue, without
•… • Enqueue, Dequeue 17
Queue Applications • Used for • Operating Systems, Network Applications: • Handling requests/events/jobs that must be done in order
• Simulation programs • Managing the events that must happen in the future • Representing queues in the real world (traffic, customers, deliveries, ….)
• Search Algorithms • Computer Games • Artificial Intelligence
• Priority Queue 18
Javaism • Could have a Stack interface and different implementations of it (ArrayStack, LinkedStack, etc)) • In Java Collections library: • Stack is a class that implements List • Has extra operations: push(value), pop(), peek() • Also has all List methods • Avoid using them
19
1
Making an ADT Import java.util.Iterator; public interface BoxADT
Using our BoxADT … BoxADT <String> toyBox; toyBox = new BoxImp<String>(); toyBox.add(“Car”); toyBox.add(“Plane”); toyBox.add(“Fred”); System.out.println(toyBox.contains(“Barbie”)); System.out.println(toyBox.contains(“Fred”));
What does this print?
while(toyBox.size()) System.out.println(toyBox.remove()); System.out.println(toyBox.contains(“Barbie”)); …
3
Bag ADT • Bag is a collection with • no structure or order maintained • no access constraints (access any item any time) • duplicates allowed
• Minimal Operations: • add(value) • remove(value) → returns true iff value removed • contains(value) → returns true iff value is in bag • findElement(value) → returns matching item iff in bag 4
Bag Applications • When to use a Bag? • When there is no need to order a collection: • A collection of user preferences. • A collection of interchangeable items (worker threads in a web server). •… • Even though a bag is unordered, the implementation may order the data for efficiency. • Such observed ordering must not be relied upon.
5
Set ADT • Set is a collection with: • no structure or order maintained • no access constraints (access any item any time) • Only property is that duplicates are excluded
• Operations: • add(value) → true iff value was added (ie, not duplicate) • remove(value) → returns true iff value removed (was in set) • contains(value) → returns true iff value is in the set • findElement(value) → returns matching item iff in value in the set •…
• When do we use a Set instead of a Bag? What
6
List ADT • Lists are: (Example ToDoList) • Sequence of values • Allows access at any position in the List • Allows items to be inserted and removed Some operations: • add(value) inserts value at the end • add(index, value) inserts value at the specified index • get(index) returns value at the specified index • set(index, value) replaces value at index by new value (and returns old value) • remove(value) removes value (first occurrence only) • remove(index) removes value at index (and returns old value) • size() returns number of values • isEmpty() true iff no values 7
Constructing Lists • Declaring a List: specify the type of the value • List<String> myFriends; • List
• Constructing a List: specify implementation and type of value: • myFriends = new LinkedList<String>(); • allPrimes = new Vector
Example: TodoList • TodoList – collection of jobs, in order they should be done. • Collection type: List of jobs, (jobs represented by a String) public class TodoList implements ActionListener{ : private List<String> myJobs; : public void readJobs(){ try { myJobs = new ArrayList<String>();
}
Scanner sc = new Scanner(new File("myJobs.txt")); while ( sc.hasNext() ){ myJobs.add(sc.next()); } sc.close(); displayJobs(); 9
More TodoList: public void actionPerformed(ActionEvent e){ if (e.getActionCommand().equals("Add") ){ myJobs.add(askJob()); } else if (e.getActionCommand().equals( "AddAt" ) ){ String job = askJob(); myJobs.add(askIndex("add at"), job); } else if (e.getActionCommand().equals("Remove") ){ myJobs.remove(askJob()); } else if (e.getActionCommand().equals("RemoveFrom") ){ myJobs.remove(askIndex("from"));
10
Rest of the example: public void displayJobs(){ textArea.setText("Jobs to be done\n"); int num = 0; for(String job : myJobs){ textArea.append((num++) + " " + job + "\n"); } };
• Note the odd for (EACH) loop (NICE): • For (type variable : Collection object ){ • Means to do the body of the loop for each value in the collection • Applies to all Collection types (except Map)
• Standard (original) Alternative:
for (int i=0; i<myJobs.size(); i++){
11
List vs Array • Lists are nicer than arrays: • No size limit!!! They grow bigger as necessary • but, slower to execute. • Lots of code written for you: • jobList.set(ind, value) • jobList.get(ind) • jobList.size() • jobList.add(value)
jobArray[ind] = value jobArray[ind] ? (Not the length!!!) ? (Where is the last value? What happens if it’s full?) • jobList.add(ind, value) ? (Have to shift everything up!!!) • jobList.remove(ind) ? (Have to shift everything down!!!) • jobList.remove(value) ? (Have to find value, then shift things down!!!) • for (String job : jobList) for(int i = 0; i< ???; i++){ String job = jobArray[ i ];
12
Stack ADT • Stack is a special kind of List: • A sequence of values, • Constrained access → to the top of the stack only.
• Operations: • • • •
push(value): pop() peek(): …
→ Put value on top of stack → Removes and returns top of stack → Returns top of stack, without removing
13
Stacks Example • Reversing the items from a file: • Read and push onto a stack • Pop them off the stack Public void reverseNums(Scanner sc){ Stack
Applications of Stacks • Programs that deal with programs • Eg, program execution: call stack/activation stack, • Eg, expression execution, • (6 + 4) * ((8 * (6 – 2)) – (7 * 3))
• Processing files of structured data. • Eg reading files of with structured markup (HTML, XML,…)
• Undo in editors. • Assignments: • #2: reading and checking XML files • #3: an Undo stack for MiniDraw 15
Evaluating Expressions • (6 + 4) * ((8 * (6 – 2)) – (7 * 3))
16
Queue ADT • Queues are like Stacks • Sequence of values • Constrained access, but: • Add at the back • Remove from the front
• Operations: • offer(value): • poll() • peek(): removing
→ Adds value to end of queue → Removes and returns front of queue → Returns front of queue, without
•… • Enqueue, Dequeue 17
Queue Applications • Used for • Operating Systems, Network Applications: • Handling requests/events/jobs that must be done in order
• Simulation programs • Managing the events that must happen in the future • Representing queues in the real world (traffic, customers, deliveries, ….)
• Search Algorithms • Computer Games • Artificial Intelligence
• Priority Queue 18
Javaism • Could have a Stack interface and different implementations of it (ArrayStack, LinkedStack, etc)) • In Java Collections library: • Stack is a class that implements List • Has extra operations: push(value), pop(), peek() • Also has all List methods • Avoid using them
19
