CS 245 Lecture 21 – Linked List, Stack, and Queue
Agenda
- what ?s
- why are we here?
- finishing up linked list and Snake
- stacks and queues
- a postfix calculator
- an HTML validator
Program This
Write one of the following for LinkedList:
sizegetFirstgetLastremoveFirstremoveLast
Program This
You’ve got an expression in “postfix” form:
- 1 2 + (which is 1 + 2)
- 3 6 * 5 – (which is 3 * 6 – 5)
- 60 12 / 2 ^ (which is (60 / 12) ^ 2)
Write pseudocode to parse and evaluate such expressions.
Code
HashSet.java
package lecture21;
import java.util.ArrayList;
public class HashSet<T> {
private ArrayList<T>[] items;
public HashSet() {
items = new ArrayList[5];
}
public void add(T item) {
int i = Math.abs(item.hashCode()) % items.length;
if (items[i] == null) {
items[i] = new ArrayList<T>();
}
if (!items[i].contains(item)) {
items[i].add(item);
}
}
public void remove(T item) {
int i = Math.abs(item.hashCode()) % items.length;
if (items[i] != null) {
items[i].remove(item);
}
}
public boolean contains(T item) {
int i = Math.abs(item.hashCode()) % items.length;
return items[i] != null && items[i].contains(item);
}
public Iterator getIterator() {
return new Iterator();
}
public class Iterator {
private int hashIndexOfItemToRetrieve;
private int listIndexOfItemToRetrieve;
public Iterator() {
hashIndexOfItemToRetrieve = 0;
listIndexOfItemToRetrieve = -1;
advanceToNextItemToRetrieve();
}
public boolean hasNext() {
return hashIndexOfItemToRetrieve < items.length;
}
public T next() {
T item = items[hashIndexOfItemToRetrieve].get(listIndexOfItemToRetrieve);
advanceToNextItemToRetrieve();
return item;
}
private void advanceToNextItemToRetrieve() {
++listIndexOfItemToRetrieve;
while (hashIndexOfItemToRetrieve < items.length &&
(items[hashIndexOfItemToRetrieve] == null ||
listIndexOfItemToRetrieve >= items[hashIndexOfItemToRetrieve].size())) {
listIndexOfItemToRetrieve = 0;
++hashIndexOfItemToRetrieve;
}
}
}
public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
set.add("a");
System.out.println(set.contains("a"));
set.remove("a");
System.out.println(set.contains("a"));
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
set.add("f");
set.add("g");
set.add("z");
set.add("z");
set.add("ifrim");
set.add("racecar");
System.out.println(set.contains("racecar"));
System.out.println(set.contains("tacocat"));
HashSet<String>.Iterator i = set.getIterator();
while (i.hasNext()) {
System.out.println(i.next());
}
}
}
LinkedList.java
package lecture21;
import java.util.NoSuchElementException;
public class LinkedList<T> {
private Node<T> head;
private Node<T> tail;
public LinkedList() {
head = new Node<T>(null, null, null);
tail = new Node<T>(null, null, null);
head.next = tail;
tail.prev = head;
}
/**
* Adds the new item at the end of this list.
*
* @param newItem
* The item to add.
*/
public void prepend(T newItem) {
Node<T> newNode = new Node<T>(newItem, head.next, head);
head.next = newNode;
newNode.next.prev = newNode;
}
public void append(T newItem) {
Node<T> newNode = new Node<T>(newItem, tail, tail.prev);
tail.prev = newNode;
newNode.prev.next = newNode;
}
public boolean isEmpty() {
return head.next == tail;
}
public int size() {
int count = 0;
Node<T> thisNode = head;
while (thisNode.next != tail) {
++count;
thisNode = thisNode.next;
}
return count;
}
public T getFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return head.next.value;
}
public T getLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return tail.prev.value;
}
public T removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
T value = head.next.value;
head.next = head.next.next;
head.next.prev = head;
return value;
}
public T removeLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
T value = tail.prev.value;
tail.prev = tail.prev.prev;
tail.prev.next = tail;
return value;
}
public Iterator getIterator() {
return new Iterator();
}
public class Iterator {
private Node<T> current;
public Iterator() {
current = head;
}
public boolean hasNext() {
return current.next != tail;
}
public T next() {
current = current.next;
return current.value;
}
}
public static class Node<T> {
private T value;
private Node<T> next;
private Node<T> prev;
public Node(T value,
Node<T> next,
Node<T> prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
}
}
SnakesOnAFrame.java
package lecture21;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import lecture21.LinkedList.Iterator;
public class SnakesOnAFrame extends JFrame implements KeyListener {
private static final int TILE_WIDTH = 25;
private static final int TILE_HEIGHT = 25;
private int heightInTiles;
private int widthInTiles;
private SnakesPanel panel;
private LinkedList<Point> snake;
private HashSet<Point> eggs;
public SnakesOnAFrame() {
eggs = new HashSet<Point>();
panel = new SnakesPanel();
add(panel);
setFocusable(true);
requestFocusInWindow();
addKeyListener(this);
setSize(1024, 600);
heightInTiles = (int) (getSize().getHeight() / TILE_HEIGHT);
widthInTiles = (int) (getSize().getWidth() / TILE_WIDTH);
generateEggs();
snake = new LinkedList<Point>();
snake.append(new Point(6, 9));
setDefaultCloseOperation(EXIT_ON_CLOSE);
setVisible(true);
}
private void generateEggs() {
Random g = new Random();
for (int i = 0; i < 20; ++i) {
int y = g.nextInt(heightInTiles);
int x = g.nextInt(widthInTiles);
eggs.add(new Point(x, y));
}
}
class SnakesPanel extends JPanel {
public void paintComponent(Graphics g) {
super.paintComponent(g);
// draw eggs
g.setColor(Color.ORANGE);
HashSet<Point>.Iterator i = eggs.getIterator();
while (i.hasNext()) {
Point egg = i.next();
g.fillOval(egg.x * TILE_WIDTH, egg.y * TILE_HEIGHT, TILE_WIDTH, TILE_HEIGHT);
}
g.setColor(Color.GREEN);
LinkedList<Point>.Iterator iSnake = snake.getIterator();
while (iSnake.hasNext()) {
Point segment = iSnake.next();
g.fillRoundRect(segment.x * TILE_WIDTH, segment.y * TILE_HEIGHT, TILE_WIDTH, TILE_HEIGHT, 20, 20);
}
}
}
public static void main(String[] args) {
new SnakesOnAFrame();
}
@Override
public void keyPressed(KeyEvent arg0) {
}
@Override
public void keyReleased(KeyEvent event) {
Point head = new Point(snake.getFirst());
switch (event.getKeyCode()) {
case KeyEvent.VK_UP:
--head.y;
break;
case KeyEvent.VK_DOWN:
++head.y;
break;
case KeyEvent.VK_LEFT:
--head.x;
break;
case KeyEvent.VK_RIGHT:
++head.x;
break;
}
// Insert the new head.
snake.prepend(head);
// Is there an egg under the head?
if (!eggs.contains(head)) {
snake.removeLast();
} else {
eggs.remove(head);
}
panel.repaint();
}
@Override
public void keyTyped(KeyEvent arg0) {
}
}
Stack.java
package lecture21;
public class Stack<T> {
private LinkedList<T> items;
public Stack() {
items = new LinkedList<T>();
}
public boolean isEmpty() {
return items.isEmpty();
}
public void push(T item) {
items.append(item);
}
public T pop() {
return items.removeLast();
}
public T peek() {
return items.getLast();
}
}
Valhalla.java
package lecture21;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Valhalla {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("/Users/johnch/Desktop/foo.html"));
in.useDelimiter("(\\A|>)[^<]*(\\Z|<)");
Stack<String> opens = new Stack<String>();
while (in.hasNext()) {
String element = in.next();
System.out.println(element);
// if it's an opener
// push it
// else
// if there's no top
// stack underflow -- invalid
// elsif it corresponds to the top
// pop -- valid
// else bad correspondence
if (!element.startsWith("/")) {
opens.push(element);
} else if (opens.isEmpty()) {
System.out.println("stack underflow");
return;
} else {
if (opens.peek().startsWith(element.substring(1))) {
opens.pop();
} else {
System.out.println("got a " + element + " but waiting for a " + opens.peek());
return;
}
}
}
if (opens.isEmpty()) {
System.out.println("wee!");
} else {
System.out.println("unclosed " + opens.peek());
}
}
}
Haiku
Jenga is a queue
I map my name to Boardwalk
Discard piles are stacks
I map my name to Boardwalk
Discard piles are stacks