Write two minimal, O(1) implementations of the QueueADT: CircularArrayQueue, and
ID: 656131 • Letter: W
Question
Write two minimal, O(1) implementations of the QueueADT: CircularArrayQueue, and LinkedQueue.
In this assignment, you are going to write two classes that implement the QueueADT interface so that you can run JosephusQueues and pass all tests.
You need to provide both the circular-array-based queue and the linked nodes-based queue with the names exactly as specified.
All QueueADT operations (other than toString()) should be O(1).
You must implement all methods in the queue classes. Do not simply wrap a list, another queue implementation, or any other data structure class.
Most of the necessary Queue code, obviously, is provided in Chapter 14. The purpose of the exercise, then, is for you to think through how it works and what is going on
Explanation / Answer
you have to use the import file package has
import java.io.File;
import java.util.Scanner;
import java.util.*;
import java.util.*;
/**
* Execute a Josephus death circle on the names in a given file (one name per line) by
* skipping given number of people between executions. The lucky martyrs are collected
* in either a circular array-based queue or a linked node-based queue.
*
* @author mvail
*/
interface QueueADT<T>
{
/**
* Adds one element to the rear of this queue.
* @param element the element to be added to the rear of the queue
*/
public void enqueue(T element);
/**
* Removes and returns the element at the front of this queue.
* @return the element at the front of the queue
* @throws EmptyCollectionException if stack is empty
*/
public T dequeue();
/**
* Returns without removing the element at the front of this queue.
* @return the first element in the queue
* @throws EmptyCollectionException if stack is empty
*/
public T first();
/**
* Returns true if this queue contains no elements.
* @return true if this queue is empty
*/
public boolean isEmpty();
/**
* Returns the number of elements in this queue.
* @return the integer representation of the size of the queue
*/
public int size();
/**
* Returns a string representation of this queue.
* @return the string representation of the queue
*/
public String toString();
}
public class CircularQueue {
int[] queue;
int front;
int rear;
int currentSize;
int size;
public CircularQueue(int size) {
this.queue = new int[size];
this.front = 0;
this.rear = 0;
this.size = size;
this.currentSize = 0;
}
public synchronized boolean add(int x) {
if (currentSize == size) {
throw new IllegalStateException("The queue is full: front size: " + rear);
}
queue[rear++] = x;
rear = (rear + 1) % size;
currentSize++;
return true;
}
public synchronized int peek() {
if (front == rear) {
throw new IllegalStateException("The queue is empty");
}
return queue[front];
}
public synchronized int poll() {
if (front > rear) {
throw new IllegalStateException("The queue is empty");
}
currentSize--;
return queue[front++];
}
}
public class LinkedQueue<T>
implements Queue<T> {
private Node<T> head ;
private Node<T> tail ;
private int length;
public LinkedQueue(){
head = null;
tail = null;
length = 0;
}
public int size() {
return length;
}
public boolean isEmpty() {
return (length == 0);
}
public void enqueue (T data) {
Node<T> newNode = new Node<T>(data);
if (isEmpty())
head = tail = newNode;
else {
tail.setNext(newNode);
tail = newNode;
}
length++;
}
public T front()
throws QueueEmptyException{
if (isEmpty())
throw new QueueEmptyException(
"FRONT from empty queue");
return head.getData();
}
public T dequeue()
throws QueueEmptyException {
if (isEmpty())
throw new QueueEmptyException(
"DEQUEUE from empty queue");
T data = head.getData();
head = head.getNext();
length--;
return data;
}
public void flush() {
while (!isEmpty())
dequeue();
}
public void print() {
Node p = head;
while (p!=null) {
if (p !=head)
System.out.print(", ");
System.out.print(p.getData());
p = p.getNext();
}
System.out.println();
}
public void concatenate(LinkedQueue<T> q) {
if (isEmpty()) {
head = q.head;
tail = q.tail;
length = q.length;
}
else if (!q.isEmpty()) {
tail.setNext(q.head);
tail = q.tail;
length += q.length;
}
}
String sentence = "Shooby doo wop she bop" ;
Scanner words
=new Scanner(sentence);
LinkedStack<String> stack=
new LinkedStack<String>();
Queue<String> queue=
new LinkedQueue<String>();
while(words.hasNext()){
String word=words.next();
stack.push(word);
queue.enqueue(word);
}
while (!stack.isEmpty()){
System.out.println(stack.pop()+
" "+queue.dequeue());
}
}
public class JosephusQueues implements QueueADT<String> {
//private QueueADT<String>;
/**
* @param args [-c|-l] [skip count] [namesFile]
*/
public static void main(String[] args) {
if (args.length != 3) {
System.out.println("Usage: java JosephusQueues [-c|-l] [int i] [namesFile]");
System.out.println(" where -c indicates that a circular array-based queue should be used");
System.out.println(" and -l indicates that a linked node-based queue should be used.");
System.out.println(" Integer i is the number of people to skip between swings of the sword.");
System.exit(1);
}
QueueADT<String> herd = null;
switch (args[0]) {
case "-c":
herd = new CircularArrayQueue<String>();
break;
case "-l":
herd = new LinkedQueue<String>();
break;
default:
System.out.println("Invalid queue type argument. Must be -c or -l.");
System.exit(1);
break;
}
int ith = 1;
try {
ith = Integer.parseInt(args[1]);
if (ith < 1) {
System.out.println("Invalid second argument. Must have a positive integer for number of people to skip.");
System.exit(1);
}
} catch (Exception e) {
System.out.println("Invalid second argument. Must have a positive integer for number of people to skip.");
System.exit(1);
}
try {
Scanner scan = new Scanner(new File(args[2]));
while (scan.hasNextLine()) {
String name = scan.nextLine().trim();
if (name.length() > 0) {
herd.enqueue(name);
}
}
scan.close();
} catch (Exception e) {
System.out.println("Invalid third argument. Cannot open or read " + args[2]);
System.exit(1);
}
if (herd.isEmpty()) {
System.out.println("Failure! You can't have a death circle without at least 2 people!");
} else {
//who's present?
System.out.println("The " + herd.size() + " not-so-lucky soldiers facing death or capture:");
System.out.println(herd);
//cull the herd
cull(herd, ith);
//who's left?
if (herd.isEmpty()) {
System.out.println("These people are incompetant. No one survived.");
} else if (herd.size() > 1) {
System.out.println("Cowards! There are " + herd.size() + " survivors!");
} else {
System.out.println("The lucky survivor who faces capture rather than death: " + herd.dequeue());
}
}
}
/**
* Skip ith-1 people and kill the ith until only one person remains.
* @param herd collection of potential martyrs
* @param ith will kill the ith person in each round of culling
*/
private static void cull(QueueADT<String> herd, int ith) {
int victimNumber = 1;
while (herd.size() > 1) {
for (int i = 0; i < ith - 1; i++) {
herd.enqueue(herd.dequeue());
}
System.out.printf("Victim %2d: %s ", victimNumber, herd.dequeue());
victimNumber++;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.