a. queue = f z b ch1 = a ch2 = b b. queue = 12 32 10 a = 2 b = 8
a. 8 b. 7 c. 5 d. 5 6 10
5 0 7 5 6 7
7 6 2 5 6 -1
6 5 5 5 6 11
6 5 5 6 30
a. queue = B C D E F b. queue = D E A c. queue = E A B C D
front = 1 front = 3 front = 4
back = 0 back = 0 back = 3
numElements = 5 numElements = 3 numElements = 5
array = F B C D E array = A B C D E array = A B C D E
value = C error; already full
d. queue = empty e. queue = D E A H f. queue = C D
front = 2 front = 3 front = 2
back = 1 back = 1 back = 3
numElements = 0 numElements = 4 numElements = 2
array = A B C D E ar ray = A H C D E array = A B C D E
value = ?? value = B
error; already empty
// use a temp queue so that oldqq is unchanged at the end of the method
public static void copy(ArrayUnboundedQueue<T> oldqq, ArrayUnboundedQueue<T> newqq) {
ArrayUnboundedQueue<T> tempqq = new ArrayUnboundedQueue<T>();
T qval;
while (!newqq.isEmpty())
qval = newqq.dequeue();
while (!oldqq.isEmpty()) {
qval = oldqq.dequeue();
newqq.enqueue(qval);
tempqq.enqueue(qval);
}
while (!tempqq.isEmpty()) {
qval = tempqq.dequeue();
oldqq.enqueue(qval);
}
}
public LinkedQueue<T> copy() {
LinkedQueue<T> newq = new LinkedQueue<T>();
LLNode<T> temp, next;
if (this.front == null)
return newq;
temp = new LLNode<T>(this.front.getInfo());
newq.front = newq.rear = temp;
next = this.front.getLink();
while (next != null) {
temp = new LLNode<T>(next.getInfo());
newq.rear.setLink(temp);
newq.rear = temp;
next = next.getLink();
}
return newq;
}
public ArrayUnboundedQueue<T> copy() {
ArrayUnboundedQueue<T> newq = new ArrayUnboundedQueue<T>(this.elements.length);
if (this.numElements == 0)
return newq;
newq.numElements = this.numElements;
// copy elements into the new queue starting at loc 0
// newq.front has been initialized to 0 in the construction
int newloc = 0;
int thisloc = this.front;
while (newloc < this.numElements) {
newq.elements[newloc] = this.elements[thisloc];
newloc++;
thisloc = (thisloc+1) % this.elements.length;
}
newq.rear = newq.numElements - 1;
return newq;
}
// use a temp queue so that qq is unchanged at the end of the method
public static void countneg(ArrayUnboundedQueue<Integer> qq) {
ArrayUnboundedQueue<Integer> tempqq = new ArrayUnboundedQueue<Integer>();
int value;
int numneg = 0;
while (!qq.isEmpty()) {
value = qq.dequeue();
tempqq.enqueue(value);
if (value < 0)
numneg = numneg + 1;
}
while (!tempqq.isEmpty()) {
value = tempqq.dequeue();
qq.enqueue(value);
}
return numneg;
}
// the match function will empty the queues; copy the queues and
// use the copies so that at the end of the function the queues will not
// be changed
public static int match(ArrayUnboundedQueue<T> qq1, ArrayUnboundedQueue<T> qq2) {
T qitem1;
T qitem2;
ArrayUnboundedQueue<T> tempqq1 = new ArrayUnboundedQueue<T>();
ArrayUnboundedQueue<T> tempqq2 = new ArrayUnboundedQueue<T>();
int ok;
int matchnum = 0;
copy(qq1,tempqq1); // from problem 4
copy(qq2,tempqq2);
while (!tempqq1.isEmpty() && !tempqq2.isEmpty()) {
qitem1 = tempqq1.dequeue();
qitem2 = tempqq2.dequeue();
if (qitem1.equals(qitem2))
matchnum = matchnum + 1;
}
return matchnum;
}
public void removeAll() {
if (count == 0)
throw new QueueUnderflowException("queue is already empty");
numElements = 0;
front = 0;
rear = queue.length - 1;
}
public void removeAll() {
if (front == null)
throw new QueueUnderflowException("queue is already empty");
front = null;
rear = null;
}
public void removeItem(T remitem) {
int loc = front;
boolean found = false;
if (numElements == 0)
throw new NoSuchElementException(remitem + " not found");
while (loc != rear && !found) {
if (queue[loc].equals(remitem))
found = true;
else
loc = (loc+1)%queue.length;
}
if (queue[rear].equals(remitem))
found = true;
if (!found)
throw new NoSuchElementException(remitem + " not found");
if (loc != rear) {
while (loc != rear) {
queue[loc] = queue[(loc+1)%queue.length];
loc = (loc+1)%queue.length;
}
}
if (rear == 0)
rear = queue.length - 1;
else
rear--;
numElements--;
}
public void removeItem(T remitem) {
LLNode<T> prev = null;
LLNode<T> curr = front;
boolean found = false;
if (front == null)
throw new NoSuchElementException(remitem + " not found");
while (curr != rear && !found) {
if (curr.getInfo().equals(remitem))
found = true;
else {
prev = curr;
curr = curr.getLink();
}
}
if (curr.getInfo().equals(remitem))
found = true;
if (!found)
throw new NoSuchElementException(remitem + " not found");
if (curr == front)
front = front.getLink();
else {
prev.setLink(curr.getLink());
if (curr == rear)
rear = prev;
}
numElements--;
}
Email Me |
Office Hours |
My Home Page |
Department Home |
MCC Home Page
© Copyright Emmi Schatz 2009