Java程序辅导

Lab 9 Queue Implementations in Circular Array and 
Linked List
Student Name: ______________________________________________________
TA Initial and Checkout time: ___________________________________________
TA Comments: ______________________________________________________
Prelab: Answer the following questions before working on the lab computers.
CSci112 Fall 2011 Closed Lab Handout! Lab 9, Friday, November 4, 2011
http://www.cs.olemiss.edu/~jxue/teaching/csci112_F11/notes/lab9
Prepared by Jianxia Xue, Last Update Wednesday, October 19, 2011! 1 of 2
1. What are the two critical operations 
in a Queue ADT?
     __________________________
     __________________________
2. What is the main difference 
between a Stack and a Queue 
ADT? 
     __________________________
     __________________________
     __________________________
     __________________________
     __________________________
     __________________________
3. Suppose that you can use only one 
node reference inside a linked queue, 
and let the reference points to the last 
enqueued item. Describe the nature of 
the linked queue given the following 
code:
      public void enqueue(T item) {
           Node n = new Node(item);
           if (last ~= null) {
!     n.setLink(last.getNext());
               last.setLink(n);
! } else {
               n.setLink(n);
           }
! last = n;
      }
     __________________________
 
     __________________________
     __________________________
     __________________________
Coding Tasks
1. Debug BuggyLinkedQueue.java
The given code of BuggyLinkedQueue.java has one syntax error in the main 
method and two logical errors in the enqueue and dequeue methods. By fixing the 
errors, the driver method should produce correct answer to a Josephus problem.
2. Deriving PoppableQueue.java from CircularArrayQueue.java
In this task, you will create a variation from the standard queue ADT, namely 
poppable queue. Such a queue supports the standard enqueue and dequeue 
operations. In addition, it also supports a pop operation, which removes the last 
enqueued item, and returns its value. 
The PoppableQueue class must be extended from CircularArrayQueue, with only 
one method of pop. The pop method should have the same interface as that in 
stack. Verify your implementation with a driver method. Here is a demo run for your 
reference.
3. (Extra Credit) 
Implement the PoppableQueue using the debugged LinkedQueue from task 1. Verify 
your implementation with a driver method.
CSci112 Fall 2011 Closed Lab Handout! Lab 9, Friday, November 4, 2011
http://www.cs.olemiss.edu/~jxue/teaching/csci112_F11/notes/lab9
Prepared by Jianxia Xue, Last Update Wednesday, October 19, 2011! 2 of 2
Exit, enqueue, dequeue, or pop?
enqueue a
Current queue is: 
Queue with 1 items:
	 a
Exit, enqueue, dequeue, or pop?
enqueue b
Current queue is: 
Queue with 2 items:
	 a
	 b
Exit, enqueue, dequeue, or pop?
enqueue c
Current queue is: 
Queue with 3 items:
	 a
	 b
	 c
Exit, enqueue, dequeue, or pop?
pop
Popped value is c
Current queue is: 
Queue with 2 items:
	 a
	 b
Exit, enqueue, dequeue, or pop?
dequeue
Dequeued value is a
Current queue is: 
Queue with 1 items:
	 b
Exit, enqueue, dequeue, or pop?
exit
Bye~