A queue that can be allowed to get the front entry without removing it.

Please, twogetSecond methods, one forArrayQueueand one forLinkedQueue.

• If the queue has two entries or more, getSecond returns the second entry (the entry after the front) without altering the queue.
• If the queue has fewer than two entries, getSecond should throw an exception (to be consistent with the 5th edition versions of the queues).

Here is the method header for both classes:

public T getSecond() 

-----------------------------------------------------------------------------------------------------------------------------------------------

/**

* A class that implements the ADT queue by using an expandable circular array

* with one unused location after the back of the queue.

*

* @author Frank M. Carrano

* @author Timothy M. Henry

* @version 5.0

*/

public final class ArrayQueue implements QueueInterface {

private T[] queue; // Circular array of queue entries and one unused location

private int frontIndex; // Index of front entry

private int backIndex; // Index of back entry

private boolean integrityOK;// true if data structure is correct, false if corrupted

private static final int DEFAULT_CAPACITY = 3;

private static final int MAX_CAPACITY = 10000;

public ArrayQueue() {

this(DEFAULT_CAPACITY);

} // end default constructor

public ArrayQueue(int initialCapacity) {

integrityOK = false;

checkCapacity(initialCapacity);

// The cast is safe because the new array contains null entries

@SuppressWarnings("unchecked")

T[] tempQueue = (T[]) new Object[initialCapacity + 1];

queue = tempQueue;

frontIndex = 0;

backIndex = initialCapacity;

integrityOK = true;

} // end constructor

public void enqueue(T newEntry) {

checkIntegrity();

ensureCapacity();

backIndex = (backIndex + 1) % queue.length;

queue[backIndex] = newEntry;

} // end enqueue

public T getFront() {

checkIntegrity();

if (isEmpty())

throw new EmptyQueueException();

else

return queue[frontIndex];

} // end getFront

public T dequeue() {

checkIntegrity();

if (isEmpty())

throw new EmptyQueueException();

else {

T front = queue[frontIndex];

queue[frontIndex] = null;

frontIndex = (frontIndex + 1) % queue.length;

return front;

} // end if

} // end dequeue

public boolean isEmpty() {

checkIntegrity();

return frontIndex == ((backIndex + 1) % queue.length);

} // end isEmpty

// Question 4, Chapter 8

public void clear() {

checkIntegrity();

if (!isEmpty()) { // Deallocates only the used portion

for (int index = frontIndex; index != backIndex; index = (index + 1) % queue.length) {

queue[index] = null;

} // end for

queue[backIndex] = null;

} // end if

frontIndex = 0;

backIndex = queue.length - 1;

} // end clear

public void display() {

for(int i=frontIndex; i!=(backIndex+1)%queue.length; i=(i+1)%queue.length) {

T data = queue[i];

System.out.print(data + " ");

}

System.out.println();

}

public void splice(ArrayQueue anotherQueue) {

//

}

private void checkIntegrity() {

if (!integrityOK)

throw new SecurityException("ArrayQueue object is corrupt.");

} // end checkIntegrity

// Throws an exception if the client requests a capacity that is too large.

private void checkCapacity(int capacity) {

if (capacity > MAX_CAPACITY)

throw new IllegalStateException(

"Attempt to have a queue " + "whose capacity exceeds " + "allowed maximum.");

} // end checkCapacity

// Doubles the size of the array queue if it is full.

// Precondition: checkIntegrity has been called.

private void ensureCapacity() {

if (frontIndex == ((backIndex + 2) % queue.length)) // If array is full,

{ // double size of array

T[] oldQueue = queue;

int oldSize = oldQueue.length;

int newSize = 2 * oldSize;

checkCapacity(newSize);

integrityOK = false;

// The cast is safe because the new array contains null entries

@SuppressWarnings("unchecked")

T[] tempQueue = (T[]) new Object[newSize];

queue = tempQueue;

for (int index = 0; index < oldSize - 1; index++) {

queue[index] = oldQueue[frontIndex];

frontIndex = (frontIndex + 1) % oldSize;

} // end for

frontIndex = 0;

backIndex = oldSize - 2;

integrityOK = true;

} // end if

} // end ensureCapacity

} // end ArrayQueue

---------------------------------------------------------------------------------------------------------------------------------------------

/**

* A class that implements a queue of objects by using a chain of linked nodes

* that has both head and tail references.

*

* @author Frank M. Carrano

* @author Timothy M. Henry

* @version 5.0

*/

public final class LinkedQueue implements QueueInterface {

public Node firstNode; // References node at front of queue

public Node lastNode; // References node at back of queue

public LinkedQueue() {

firstNode = null;

lastNode = null;

} // end default constructor

public void enqueue(T newEntry) {

Node newNode = new Node(newEntry, null);

if (isEmpty())

firstNode = newNode;

else

lastNode.setNextNode(newNode);

lastNode = newNode;

} // end enqueue

public T getFront() {

if (isEmpty())

throw new EmptyQueueException();

else

return firstNode.getData();

} // end getFront

public T dequeue() {

T front = getFront(); // Might throw EmptyQueueException

// Assertion: firstNode != null

firstNode.setData(null);

firstNode = firstNode.getNextNode();

if (firstNode == null)

lastNode = null;

return front;

} // end dequeue

public boolean isEmpty() {

return (firstNode == null) && (lastNode == null);

} // end isEmpty

public void clear() {

firstNode = null;

lastNode = null;

} // end clear

public void display() {

Node current = firstNode;

while(current!=null) {

System.out.print(current.data + " ");

current = current.next;

}

System.out.println();

}

public void splice(LinkedQueue anotherQueue) {

//

}

public class Node {

public T data; // Entry in queue

public Node next; // Link to next node

private Node(T dataPortion) {

data = dataPortion;

next = null;

} // end constructor

private Node(T dataPortion, Node linkPortion) {

data = dataPortion;

next = linkPortion;

} // end constructor

private T getData() {

return data;

} // end getData

private void setData(T newData) {

data = newData;

} // end setData

private Node getNextNode() {

return next;

} // end getNextNode

private void setNextNode(Node nextNode) {

next = nextNode;

} // end setNextNode

} // end Node

} // end Linkedqueue

---------------------------------------------------------------------------------------------------------

/**

An interface for the ADT deque.

@author Frank M. Carrano

@author Timothy M. Henry

@version 5.0

*/

public interface DequeInterface

{

/** Adds a new entry to the front/back of this deque.

@param newEntryAn object to be added. */

public void addToFront(T newEntry);

public void addToBack(T newEntry);

/** Removes and returns the front/back entry of this deque.

@returnThe object at the front/back of the deque.

@throwsEmptyQueueException if the deque is empty before the

operation. */

public T removeFront();

public T removeBack();

/** Retrieves the front/back entry of this deque.

@returnThe object at the front/back of the deque.

@throwsEmptyQueueException if the deque is empty. */

public T getFront();

public T getBack();

/** Detects whether this deque is empty.

@returnTrue if the deque is empty, or false otherwise. */

public boolean isEmpty();

/*Removes all entries from this deque. */

public void clear();

} // end DequeInterface