CS 245 Lecture 20 – More Stack
Agenda
- what ?s
- is-a vs. has-a
- program this
- solve this
- postfix calculator
- searching the filesystem
TODO
- Write a static method reverseString that accepts a String parameter and returns the reversed version. Use a stack instead of the more straightforward algorithm. 1/4 sheet.
Program This
Write a Stack class, with methods size(), push(), pop(), and peek().
Solve This
Solve these postfix expressions. Think about your method:
- 5 6 *
- 8 9 10 + +
- 1 1 – 1 1 + *
Code
Stack.java
package lecture20;
import java.util.LinkedList;
public class Stack<T> {
private LinkedList<T> items;
public Stack() {
items = new LinkedList<T>();
}
public boolean isEmpty() {
return items.isEmpty();
}
public int size() {
return items.size();
}
public void push(T itemToAdd) {
items.add(itemToAdd);
}
public T pop() {
return items.removeLast();
}
public T peek() {
return items.getLast();
}
// public void push(T itemToAdd) {
// super.pu
// }
public static void main(String[] args) {
Stack<Integer> numbers = new Stack<Integer>();
numbers.push(10);
// process(numbers);
// numbers.add(0, 20);
System.out.println(numbers.peek());
System.out.println(numbers.pop());
}
// public static void process(LinkedList<Integer> l) {
// l.add(0, 56);
// }
}
Postfix.java
package lecture20;
import java.util.Scanner;
public class Postfix {
public static void main(String[] args) {
System.out.println("Enter your maths: ");
Scanner in = new Scanner(System.in);
Stack<Integer> operands = new Stack<Integer>();
while (in.hasNext()) {
if (in.hasNextInt()) {
int number = in.nextInt();
operands.push(number);
} else {
String operator = in.next();
int b = operands.pop();
int a = operands.pop();
if (operator.equals("+")) {
operands.push(a + b);
} else if (operator.equals("-")) {
operands.push(a - b);
} else if (operator.equals("*")) {
operands.push(a * b);
} else if (operator.equals("/")) {
operands.push(a / b);
} else {
throw new RuntimeException("Bad math, you foobag!");
}
}
}
int result = operands.pop();
System.out.println("Your answer is: " + result);
}
}
DiskSearcher.java
package lecture20;
import java.io.File;
public class DiskSearcher {
public static void main(String[] args) {
Stack<File> directoriesToSearch = new Stack<File>();
directoriesToSearch.push(new File("/Users/johnch/Desktop"));
while (!directoriesToSearch.isEmpty()) {
// pull off a directory
// look at its files
// if there's a match, we're done
// or if there's a directory, add it to the stack
File dirToSearch = directoriesToSearch.pop();
File[] contents = dirToSearch.listFiles();
for (File entry : contents) {
if (entry.getName().endsWith(".png")) {
System.out.println(entry);
} else if (entry.isDirectory()) {
directoriesToSearch.push(entry);
}
}
}
}
}
Haiku
We crave being first
But what if life is a stack?
Where the first is last?
But what if life is a stack?
Where the first is last?