In JAVA

Implement the Queue ADT using a circular linked list

The LinkedQueue.java Implements QueueInterface using a linked list.

1. QueueInterface.java

package ch04.queues;

public interface QueueInterface {

void remove(int count) throws QueueUnderflowException;

boolean swapStart();

boolean swapEnds();

}

2. LLNode.java

package support;

public class LLNode {

private T element; private LLNode next;

public LLNode(T element) { this.element = element; }

public void setNext(LLNode node) { this.next = node;

}

public T getElement() { return element; }

/** * @param element the element to set */ public void setElement(T element) { this.element = element; }

public LLNode getNext() { return next; }

}

3. LinkedQueue.java

package ch04.queues;

import support.LLNode;

public class LinkedQueue implements QueueInterface {

protected LLNode front; // reference to the front of this queue protected LLNode rear; // reference to the rear of this queue protected int numElements = 0; // number of elements in this queue

public LinkedQueue() { front = null; rear = null; }

public void enqueue(T element) { LLNode node = new LLNode(element);

if (isEmpty()) front = node; else rear.setNext(node); rear = node; numElements++; }

/** * The remove method removes the front count elements from the queue * * @param count * @throws QueueUnderflowException */ @Override public void remove(int count) throws QueueUnderflowException { for (int i = 1; i <= count; i++) { dequeue(); } }

/** * The swapStart method returns false if less than two elements are in the * queue, otherwise reverses the order of the front two elements in the * queue and returns true. * * @return * @throws QueueUnderflowException */ public boolean swapStart() { if (numElements < 2) return false; else { // swap T firstElement = front.getElement(); T lastElement = front.getNext().getElement(); front.setElement(lastElement); front.getNext().setElement(firstElement); return true; }

}

/** * The swapEnds method returns false if there are less than two elements in * the queue, otherwise swaps the first and last elements of the queue and * returns true * * @return */ public boolean swapEnds() { if (numElements < 2) return false; else { T firstElement = front.getElement(); T lastElement = rear.getElement(); front.setElement(lastElement); rear.setElement(firstElement); return true;

} }

public T dequeue() throws QueueUnderflowException { if (isEmpty()) throw new QueueUnderflowException("Queue Underflow!");

T result = front.getElement(); front = front.getNext(); numElements--;

if (isEmpty()) rear = null; return result; }

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

public String toString() { String result = ""; LLNode current = front;

while (current != null) { result = result + (current.getElement()).toString() + " "; current = current.getNext(); }

return result; } }

4. QueueUnderflowException.java

package ch04.queues;

@SuppressWarnings("serial") public class QueueUnderflowException extends Exception { private String message; public QueueUnderflowException(String message) { this.message=message; System.out.println(this.message); } }

5. LinkedQueueDriver.java

package ch04.queues;

public class LinkedQueueDriver {

public static void main(String[] args) { try { LinkedQueue linkedQueue = new LinkedQueue(); linkedQueue.enqueue(10); linkedQueue.enqueue(20); linkedQueue.enqueue(30); linkedQueue.enqueue(40); linkedQueue.enqueue(50); System.out.println("Queue"); System.out.println(linkedQueue);

System.out.println("after swapStart"); linkedQueue.swapStart(); System.out.println(linkedQueue); System.out.println("after swapEnds"); linkedQueue.swapEnds(); System.out.println(linkedQueue); System.out.println("after remove 2 count"); linkedQueue.remove(2); System.out.println(linkedQueue); linkedQueue.remove(3); System.out.println("after remove 3 count"); System.out.println(linkedQueue); linkedQueue.remove(1); } catch (QueueUnderflowException e) { e.printStackTrace(); }

}

}