1. Linked list queue. Modify the LinkedQueue data structure (LinkedQueue.java) b
ID: 670268 • Letter: 1
Question
1. Linked list queue. Modify the LinkedQueue data structure (LinkedQueue.java) by adding the following methods. • void reverse() - This method reverses the order of the linked list (first becomes last and last becomes first). It should not create a new list, it should only reverse the order of the nodes. • int remove(Item item) - This method scans the queue for occurrences of item and removes them from the queue. It returns the number of items deleted from the queue. Modify the main function of LinkedQueue to do the following. (a) Create a queue of Strings, by inserting (enqueuing) the following strings: “a”, “b”, “c”, “a”, “d”, “b”, “abba”, “a”, “z”, “a”. (b) Output the queue. (c) Reverse the queue. (d) Output the queue. (e) Remove the string “a” from the queue. (f) Remove the string “f” from the queue (not in the queue). (g) Remove the string “c” from the queue.
Explanation / Answer
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class LinkedQueue<Item> implements Iterable<Item> {
private int N; // number of elements on queue
private Node first; // beginning of queue
private Node last; // end of queue
// helper linked list class
private class Node {
private Item item;
private Node next;
}
/**
* Initializes an empty queue.
*/
public LinkedQueue() {
first = null;
last = null;
N = 0;
assert check();
}
/**
* Is this queue empty?
* @return true if this queue is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
public int size() {
return N;
}
/**
* Returns the item least recently added to this queue.
* @return the item least recently added to this queue
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* Adds the item to this queue.
* @param item the item to add
*/
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
assert check();
}
public void reverse(){
if(first != last){
reverse(first);
last.next = null;
}
}
public void reverse(Node next){
if(next.next == null){
Node temp = first;
first = last;
last = temp;
}
else{
reverse(next.next);
next.next.next = next;
}
}
public int remove(Item item){
Node temp = first;
int count = 0;
while(temp != null && temp == first){
if(temp.item.equals(item)){
temp = temp.next;
first = temp;
count++;
}
else{
temp = temp.next;
}
}
temp = first;
while(temp.next != null){
if(temp.next.item.equals(item)){
temp.next = temp.next.next;
count++;
}
else{
temp = temp.next;
}
}
return count;
}
/**
* Removes and returns the item on this queue that was least recently added.
* @return the item on this queue that was least recently added
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null; // to avoid loitering
assert check();
return item;
}
/**
* Returns a string representation of this queue.
* @return the sequence of items in FIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
// check internal invariants
private boolean check() {
if (N < 0) {
return false;
}
else if (N == 0) {
if (first != null) return false;
if (last != null) return false;
}
else if (N == 1) {
if (first == null || last == null) return false;
if (first != last) return false;
if (first.next != null) return false;
}
else {
if (first == null || last == null) return false;
if (first == last) return false;
if (first.next == null) return false;
if (last.next != null) return false;
// check internal consistency of instance variable N
int numberOfNodes = 0;
for (Node x = first; x != null && numberOfNodes <= N; x = x.next) {
numberOfNodes++;
}
if (numberOfNodes != N) return false;
// check internal consistency of instance variable last
Node lastNode = first;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
if (last != lastNode) return false;
}
return true;
}
/**
* Returns an iterator that iterates over the items in this queue in FIFO order.
* @return an iterator that iterates over the items in this queue in FIFO order
*/
public Iterator<Item> iterator() {
return new ListIterator();
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
/**
* Unit tests the <tt>LinkedQueue</tt> data type.
*/
public static void main(String[] args) {
LinkedQueue<String> q = new LinkedQueue<String>();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
q.enqueue("a");
q.enqueue("d");
q.enqueue("b");
q.enqueue("abba");
q.enqueue("a");
q.enqueue("z");
q.enqueue("a");
System.out.println(q);
q.reverse();
System.out.println(q);
System.out.println(q.remove("a"));
System.out.println(q);
System.out.println(q.remove("f"));
System.out.println(q);
System.out.println(q.remove("c"));
System.out.println(q);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.