Implement a FIFO (first in first out) queue. The methods need to support are add(E e), poll(), size(), isEmpty(), iterator() (the same method names in java's Queue implementation java.util.LinkedList).
Solution:
The time complexity of add(E e), poll(), size(), isEmpty() are O(1), the time complexity of iterator() is O(N). The space complexity is O(N).
import java.util.Iterator;
public class MyLinkedListQueue<Item> implements Iterable<Item> {
private int N;
private class Node {
private Item item;
private Node next;
}
private Node first;
private Node last;
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void add(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty()) first = last;
else oldlast.next = last;
N++;
}
public Item poll() {
if(isEmpty()) return null;
Item item = first.item;
first = first.next;
if(isEmpty()) last = null;
N--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<Item> {
Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
MyLinkedListQueue<Integer> queue = new MyLinkedListQueue<>();
queue.add(3);
queue.add(4);
queue.add(0);
System.out.println(queue.size());
System.out.println(queue.poll());
Iterator<Integer> it = queue.iterator();
System.out.println();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.isEmpty());
queue.add(5);
System.out.println(queue.size());
}
}
