Java程序辅导

Monday 11/1
Announcements:
 Lab 6 is due Today 
 Quiz 4 Friday
 Stack: Client and Programmer View
 Queue: Client and Programmer View
 Homework 7 is posted
For Next Time
 Do Lab 7 Before Lab (Queues and Mazes)
 Review Section 4.7 – Queue Implementation
Today
 Queue ADT – Client View of a Queue
 Queue Implementation 
 In-class Exercise 11-QueuePractice.java (20 minutes)
 Lab 7 Before Lab (10 minutes)
Queue Practice
 There is Queue interface but no Queue class.
 How does Java implement a Queue?
 LinkedList implements the interface Queue
Queue myQueue = new LinkedList<>();  //ArrayDeque<>()
 Method count(myQueue, target): Using size() to examine all elements 
in the Queue and leaving the Queue unchanged.
A B C myQueue
loop size() times
remove/poll
process current
add/offer
B C A myQueue
C A B myQueue
A B C myQueue
Queue HAS-A List : Implementation
 How should we implement the Queue?
 Could use “has-a” with 
ArrayList class
 LinkedList class
Which would be better and why?
public  class QueueHasA implements Queue{
private LinkedList   theQueue;   //field
public E poll (){
if(theQueue.isEmpty())
return null;
return theQueue.removeFirst();
}
Queue From Scratch Using SLL
 SingleLinked List Implementation
What fields do we need?
Node front, rear
int size       //the Queue interface includes size()
What does it look like?
 Which side of the single linked list is front and       
which is rear?
front    rear      size 3
A  B  C  
Single-Linked List Implementation
 Fields
Node front, rear
int size
 Of course we have private inner class Node
Single-Linked List Implementation
public class LinkedQueue implements Queue{
//fields
private Node front, rear;
private int size;
public  boolean offer(E item){
if (size == 0) {
rear   = new Node(item);
front =  rear;
}
else {
rear.next = new Node(item)
rear = rear.next;
}
size++;
return true;
}//offer
special case – what is it?
Single-Linked List Implementation
Continued
public class LinkedQueue implements Queue{
….
public  E poll ( ){
if (size == 0)
return null;
E item = front.data;
front = front.next;
size - - ; //what if we remove the last element
return item;
}//poll
….
}
Queue From Scratch Using an Array
 Circular Array Implementation From Scratch
What fields do we need?
 E [ ] theData
 int size, front, rear
int capacity
final int DEFAULT_CAPACITY=10;
Implementing ArrayQueue
Suppose the ArrayQueue is full
Now remove one element
Now suppose we add an element  A
Implementing ArrayQueue
size     = 0front = 0
rear  = 4
public ArrayQueue(int initCapacity) {
capacity = initCapacity;
theData = (E[])new Object[capacity];
front = 0;
rear = capacity – 1;
size = 0;
}
ArrayQueue q = new ArrayQueue(5);  //client code
capacity = 5
Implementing a Queue Using a Circular Array 
Implementing a Queue Using a Circular Array 
size     = 0front = 0
rear  = 4
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('*');
capacity = 5
1
rear  = 0
*
size     = 1front = 0
rear  = 1
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('+');
capacity = 5
2
rear  = 0
*
+
Implementing a Queue Using a Circular Array 
size     = 2front = 0
rear  = 1
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('/');
capacity = 5
3*
+
rear  = 2 /
Implementing a Queue Using a Circular Array 
size     = 3front = 0
rear  = 3
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('-');
capacity = 5
4*
+
rear  = 2 /
-
Implementing a Queue Using a Circular Array 
size     = 4front = 0
rear  = 4
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('A');
capacity = 5
5*
+
rear  = 3
/
A
-
Implementing a Queue Using a Circular Array 
size     = 5front = 0
public E poll() {
if (size == 0) {
return null
}
E result = theData[front];
front = (front + 1) % capacity;
size--;
return result;
}
next = q.poll();
capacity = 5
4*
+
/
-
result = '*'
front = 1
Arear  = 4
Implementing a Queue Using a Circular Array 
size     = 4
front = 1
public E poll() {
if (size == 0) {
return null
}
E result = theData[front];
front = (front + 1) % capacity;
size--;
return result;
}
next = q.poll();
capacity = 5
3*
+
/
-
result = '+'
front = 2
Arear  = 4
Implementing a Queue Using a Circular Array 
size     = 3
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('B');
capacity = 5
4*
+
/
-
front = 2
Arear  = 4
rear  = 0 B
Implementing a Queue Using a Circular Array 
size     = 4
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('C');
capacity = 5
5B
+
/
-
front = 2
A
rear  = 0
rear  = 1 C
Implementing a Queue Using a Circular Array 
size     = 5
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
Implementing a Queue Using a Circular Array 
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
theData
Implementing a Queue Using a Circular Array 
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 2
i  = 0
newData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 2
i  = 0 /
j = 3
i  = 1
newData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 3
i  = 1 -
j = 4
i  = 2
/
newData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 0
i  = 2 A
j = 4i  = 3
/
-
newData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 1
i  = 3 B
j = 0
i  = 4
/
-
A
newData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
B
+
/
-
front = 2
A
rear  = 1 C
newCapacity = 10
j = 2
i  = 4 C
j = 1
i  = 5
/
-
A
B
newData
theData
theData
Implementing a Queue Using a Circular Array
size     = 5
private void reallocate() {
int newCapacity = 2 * capacity;
E[] newData = (E[])new Object[newCapacity];
int j = front;
for (int i = 0; i < size; i++) {
newData[i] = theData[j];
j = (j + 1) % capacity;
}
front = 0;
rear = size – 1;
capacity = newCapacity;
theData = newData;
}
q.offer('D');
capacity = 5
front = 2
rear  = 1
newCapacity = 10
C
i  = 5
/
-
A
B
B
+
/
-
A
C
j = 2
theData
front = 0
rear  = 4
10
Implementing a Queue Using a Circular Array
size     = 5
q.offer('D');
capacity = 5
C
/
-
A
B
theData
front = 0
rear  = 4
10
public boolean offer(E item) {
if (size == capacity) {
reallocate();
}
size++;
rear = (rear + 1) % capacity;
theData[rear] = item;
return true;
}
6
rear  = 5 D
In-class Exercise
1. You can work together but each student must write 
and submit their own code
2. Start eclipse and create JavaProject PracticeQueue
3. Add QueuePractice.java to your JavaProject
4. At the end of class upload QueuePractice.java to the 
Submission System In-class 8-QueuePractice