Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 28-Mar-2007

Logistics:

1. Reading (same as last class):

a. Java by Dissection, Sections 12.5 – 12.6 (Stacks) and 12.7 (Queues)

b. Javanotes, Section 9.3 (all of it, including Queues)

2. Reminder: Study StackByInheritance.java

a. know how to create your own interfaces, exceptions, and parameterized classes.

Topics:

1. Queues

a. Word History (from http://dictionary.reference.com/browse/queue):
“When the British stand in queues (as they have been doing at least since 1837, when this meaning of the word is first recorded in English), they may not realize they form a tail. The French word queue from which the English word is borrowed is a descendant of Latin cōda, meaning "tail." French queue appeared in 1748 in English, referring to a plait of hair hanging down the back of the neck. By 1802 wearing a queue was a regulation in the British army, but by the mid-19th century queues had disappeared along with cocked hats. Latin cōda is also the source of Italian coda, which was adopted into English as a musical term (like so many other English musical terms that come from Italian). A coda is thus literally the "tail end" of a movement or composition.”
Churchill is said to have coined Queuetopia (1950), to describe Britain under Labour or Socialist rule.” My wife, having just heard this quote, said it was “Queuet”.

b. FIFO == “First In First out”

c. Operations:

i. Enqueue (or “push”): Add to the back of the queue

ii. Dequeue (or “pop”): Remove from the front of the stack

iii. Others (Peek, IsEmpty, …)

d. Typical Implementation as Linked List (singly or doubly, perhaps circularly)

i. Q: Why is it reasonable for Java to implement a Stack as a Vector (which it does), but it is unreasonable to implement a Queue that way?

ii. Add to back of singly-linked list and Remove from front (why?)

iii. Circularly-linked list may be a good choice here (why?)

e. Java Queue: java.util.Queue

i. This is an interface, not a class (like java.util.Stack)

ii. The naming is peculiar:

1. “peek” is there, but so is the nearly-identical method “element”

2. “enqueue” à “offer”

3. “dequeue” à “remove”, but there is the nearly-identical method “poll”

iii. The description is peculiar:

1. “Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out).”

2. This is a broader use of the word “queue” than we shall use.

a. Queue == FIFO

b. Stack == LIFO

c. Priority Queue comes later and is neither FIFO nor LIFO

iv. The implementing class is peculiar:

1. java.util.LinkedList implements Queue

a. So name is perhaps misleading

b. Also: this is not synchronized, but java.util.Stack is!

2. You may wish to do this:
@SuppressWarnings(value={"unchecked"})
class Queue extends LinkedList {
public void enqueue(Object obj) { add(obj); }
public Object dequeue() { return remove(); }
public boolean isEmpty() { return (size() == 0); }
}

f. Q: What are the tradeoffs (including Big-Oh runtimes of enqueue and dequeue operations) in backing a Queue with:

i. Singly-Linked List

ii. Doubly-Linked List

iii. Circularly-Linked (singly-linked or doubly-linked) List

iv. ArrayList

v. Two Stacks (think about this!)

2. Queues versus Stacks

a. Typical use in programs

i. Stack: the call stack

ii. Queue: the event queue

b. Typical use in search

i. Stack: depth-first search (DFS)

ii. Queue: breadth-first search (BFS)

3. DFS versus BFS

// DfsBfs.java

// Demonstrates depth-first search and breadth-first search

// using a stack or a queue (respectively).

// Note that DFS is usually implemented recursively, rather

// than using an explicit stack, and further that the recursive

// calls at each level typically occur before fully expanding that level,

// unlike here, so the order in which nodes are "visited" is different here.

// Standard disclaimer: As usual with sample code designed (often in

// class!) to demonstrate specific issues, the style may not be perfect

// (it is especially lacking comments and some top-down design),

// and there may even be a bug or two lurking in the code!

import static java.lang.System.out;

import java.util.*;

@SuppressWarnings(value={"unchecked"})

class Queue extends LinkedList {

public void enqueue(Object obj) { add(obj); }

public Object dequeue() { return remove(); }

public boolean isEmpty() { return (size() == 0); }

}

@SuppressWarnings(value={"unchecked"})

abstract public class DfsBfs {

protected int islands = 20;

protected boolean[][] hasBridge = new boolean[islands][islands];

protected boolean[] visited;

public void addBridge(int island1, int island2) {

hasBridge[island1][island2] = hasBridge[island2][island1] = true;

}

public DfsBfs() {

addBridge(0,1); addBridge(0,2); addBridge(0,3);

addBridge(1,3); addBridge(1,4);

addBridge(2,5);

addBridge(4,6);

}

abstract public void clearList();

abstract public void addToList(Integer i);

abstract public boolean listIsEmpty();

abstract public Integer removeFromList();

abstract public String listToString();

public boolean isConnected(int island1, int island2) {

out.printf("\n%s.isConnected(%d,%d):\n",getClass().getName(),island1,island2);

clearList();

visited = new boolean[islands];

addToList(island1);

out.printf("Starting with %d: %s\n",island1,listToString());

visited[island1] = true;

while (!listIsEmpty()) {

int island = removeFromList();

out.printf("Removing %d: %s\n",island,listToString());

if (island == island2)

return true;

for (int i=0; i<islands; i++)

if (hasBridge[island][i] && (!visited[i])) {

addToList(i);

visited[i] = true;

out.printf("Adding %d->%d: %s\n",
island,i,listToString());

}

}

return false;

}

public static void main(String[] args) {

DfsBfs dfs = new DepthFirstSearch();

DfsBfs bfs = new BreadthFirstSearch();

out.println(dfs.isConnected(0,6));

out.println(bfs.isConnected(0,6));

}

}

@SuppressWarnings(value={"unchecked"})

class DepthFirstSearch extends DfsBfs {

private Stack stack;

public void clearList() { stack = new Stack(); }

public void addToList(Integer i) { stack.push(i); }

public boolean listIsEmpty() { return stack.empty(); }

public Integer removeFromList() { return (Integer)stack.pop(); }

public String listToString() { return stack.toString(); }

}

@SuppressWarnings(value={"unchecked"})

class BreadthFirstSearch extends DfsBfs {

private Queue queue;

public void clearList() { queue = new Queue(); }

public void addToList(Integer i) { queue.enqueue(i); }

public boolean listIsEmpty() { return queue.isEmpty(); }

public Integer removeFromList() { return (Integer)queue.dequeue(); }

public String listToString() { return queue.toString(); }

}