# teaching machines

## CS 245 Lecture 21 – Linked List, Stack, and Queue

April 15, 2014 by . Filed under cs245, lectures, spring 2014.

### 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:

• size
• getFirst
• getLast
• removeFirst
• removeLast

### 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];
}

int i = Math.abs(item.hashCode()) % items.length;
if (items[i] == null) {
items[i] = new ArrayList<T>();
}
if (!items[i].contains(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;
}

public boolean hasNext() {
return hashIndexOfItemToRetrieve < items.length;
}

public T next() {
T item = items[hashIndexOfItemToRetrieve].get(listIndexOfItemToRetrieve);
return item;
}

++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>();
System.out.println(set.contains("a"));
set.remove("a");
System.out.println(set.contains("a"));

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());
}
}
}

package lecture21;

import java.util.NoSuchElementException;

private Node<T> tail;

head = new Node<T>(null, null, null);
tail = new Node<T>(null, null, null);
}

/**
* Adds the new item at the end of this list.
*
* @param newItem
*/
public void prepend(T newItem) {
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() {
}

public int size() {
int count = 0;
while (thisNode.next != tail) {
++count;
thisNode = thisNode.next;
}
return count;
}

public T getFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
}

public T getLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return tail.prev.value;
}

public T removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
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() {
}

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;

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 HashSet<Point> eggs;

public SnakesOnAFrame() {
eggs = new HashSet<Point>();

panel = new SnakesPanel();

setFocusable(true);
requestFocusInWindow();

setSize(1024, 600);

heightInTiles = (int) (getSize().getHeight() / TILE_HEIGHT);
widthInTiles = (int) (getSize().getWidth() / TILE_WIDTH);

generateEggs();
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);
}
}

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);
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) {

switch (event.getKeyCode()) {
case KeyEvent.VK_UP:
break;
case KeyEvent.VK_DOWN:
break;
case KeyEvent.VK_LEFT:
break;
case KeyEvent.VK_RIGHT:
break;
}

// Is there an egg under the head?
snake.removeLast();
} else {
}

panel.repaint();
}

@Override
public void keyTyped(KeyEvent arg0) {
}
}

#### Stack.java

package lecture21;

public class Stack<T> {

public Stack() {
}

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

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