队列基础

用可变数组长度实现队列，用链实现队列

 1 import java.util.Iterator;
 2 
 3 
 4 public class ResizingArrayQueue<Item> implements Iterable<Item> {
 5     
 6     private Item[] a = (Item[])new Object[1];
 7     private int N = 0;
 8     
 9     public int size() {
10         return N;
11     }
12     
13     public boolean isEmpty() {
14         return N == 0;
15     }
16     
17     public void resize(int max) {
18         Item[] temp = (Item[]) new Object[max];
19         for(int i=0; i<N; i++) {
20             temp[i] = a[i];
21         }
22         a = temp;
23     }
24     
25     public void enqueue(Item item) {
26         if(N == a.length) {
27             resize(2*a.length);
28         }
29         a[N++] = item;
30     }
31     
32     public Item dequeue() {
33         //拷贝所有的老数组元素到新的数组，并命名为oldItems
34         Item[] oldItems = (Item[]) new Object[N];
35         for(int i=0; i<N; i++) {
36             oldItems[i] = a[i];
37         }
38         
39         //重新设置Queue的大小
40         a[--N] = null;
41         if(N>0 && N == a.length/4 ) {
42             resize(a.length/2);
43         }
44         
45         //获取新数组
46         for(int i=0; i<N-1; i++) {
47             a[i] =oldItems[i+1];
48         }
49         
50         return oldItems[0];
51     }
52     
53     @Override
54     public Iterator<Item> iterator() {
55         return new ArrayIterator();
56     }
57     
58     private class ArrayIterator implements Iterator<Item>{
59         
60         private int i = N;
61 
62         @Override
63         public boolean hasNext() {
64             
65             return i > 0;
66         }
67 
68         @Override
69         public Item next() {
70             Item[] oldItems = (Item[]) new Object[N];
71             for(int i=0; i<N; i++) {
72                 oldItems[i] = a[i];
73             }
74             a[--i] = null;
75             for(int i=0; i<N-1; i++) {
76                 a[i] =oldItems[i+1];
77             }
78             return oldItems[0];
79         }
80         
81     }
82 
83 }

import java.util.Iterator;

public class Queue<Item> implements Iterable<Item> {
    
    private Node first;  //指向最早添加的结点的链接
    private Node last;   //指向最近添加的结点的链接
    private int N;       //队列中的元素数量
    
    private class Node{
        //定义了结点的嵌套类
        Item item;
        Node next;
    }
    
    public boolean isEmpty() {
        return N == 0;//或：first == null;
    }
    
    public int size() {
        return N;
    }
    
    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++;
    }
    
    public Item dequeue() {
        //从表头删除元素
        Item item = first.item;
        first = first.next;
        if(isEmpty()) {
            last = null;
        }
        N--;
        return item;
    }
    
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    
    private class ListIterator implements Iterator<Item>{
        
        private Node current = first;
        
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            if(isEmpty()) {
                last = null;
            }
            return item;
        }
        
    }

}