Site Search:

Queue/LinkedList

Queue is a FIFO (first in first out) data structure. JDK's Queue implementation is java.util.LinkedList. The add(E e) and offer(E e) add to the queue, the remove() and poll() retrieves and removes the head of the queue. Offer and poll don't throw exception, while add and remove throws exception. The implementation is based on linked list, the time complexity are O(1), the space complexity is O(N).

The following is a simplified class for queue:

Code:

import java.util.Iterator;
public class MyLinkedListQueue<Item> implements Iterable<Item> {
    private int N;
    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());
    }

}


Examples: