集合介紹：

可以看到集合類的基本介面是Collection介面，而Collection介面繼承了Iterable介面,這個介面內部只有一個方法public abstract Iterator iterator()，而這個迭代器物件用于依次訪問集合中的元素

接下來讓我跟你們介紹一下迭代器Iterator：

1.hasnext()方法：集合中有元素的時候回傳true，否則回傳false；

2.next()方法：首先迭代器指向第一個元素的前面的空白部分，呼叫next后迭代器越過下一個元素，并且回傳這個元素的參考；

3.remove()方法：洗掉上次next回傳的元素，他們互相依賴，所以next（）方法應用在remove（）方法的前面；

接下來介紹Collection集合

Collection

Collection作為基本介面，其中的方法能被所實作了的子類所使用

List集合是線性表，區別于Set，Set不能出現重復的元素

實作List介面的類：

1.Stack

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出的原則

實作Stack：

import java.util.Arrays;
public class MyStack<T> {
    private T[] elem;//陣列
    private int top;//堆疊頂指標

    public MyStack() {
        this.elem = (T[])new Object[10];
    }

    public void push(T item) {
        //1、判斷當前堆疊是否是滿
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.top++] = item;
    }

    public boolean isFull(){
        return this.elem.length == this.top;
    }

    public T pop() {
        if(empty()) {
            throw new UnsupportedOperationException("堆疊為空！");
        }
        T ret = this.elem[this.top-1];
        this.top--;
        return ret;
    }
    public T peek() {
        if(empty()) {
            throw new UnsupportedOperationException("堆疊為空！");
        }
        return this.elem[this.top-1];
    }
    public boolean empty(){
        return this.top == 0;
    }
}
 public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.peek());//3
        System.out.println(myStack.pop());//3
        System.out.println(myStack.pop());//2
        System.out.println(myStack.pop());//1
        System.out.println(myStack.empty());//true
}

影片演示：

2.Queue

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出的特點

進行插入操作的一端稱為隊尾

進行洗掉操作的一端稱為隊頭

實作：

class Node {
    private int val;
    private Node next;
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    private Node first;
    private Node last;
    //入隊
    public void offer(int val) {
        //判斷是不是第一次插入
        Node node = new Node(val);
        if(this.first == null) {
            this.first = node;
            this.last = node;
        }else {
            this.last.setNext(node);//last.next = node;
            this.last = node;
        }
    }
    //出隊
    public int poll() {
        //判斷是否為空的
        if(isEmpty()) {
            throw new UnsupportedOperationException("佇列為空！");
        }
        //this.first = this.first.next;
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;
    }
    //得到隊頭元素
    public int peek() {
        if(isEmpty()) {
            throw new UnsupportedOperationException("佇列為空！");
        }
        return this.first.getVal();
    }
    //佇列是否為空
    public boolean isEmpty() {
        return this.first == null;
    }
public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);

        System.out.println(myQueue.peek());//1
        System.out.println(myQueue.poll());//1
        System.out.println(myQueue.poll());//2
        System.out.println(myQueue.poll());//3
		while(myQueue!=null){
			System.out.println(myQueue.poll());
		}
        System.out.println(myQueue.isEmpty());//true
    }
}

回圈佇列

回圈佇列由front隊頭指標和rear隊尾指標分別來洗掉元素和添加元素

回圈佇列的特點：
1.在rear等于front的時候佇列空
2.rear+1==front的時候隊滿
3.大小為size的佇列實際用到的只有size-1個空間

回圈佇列的一個好處是我們可以利用這個佇列之前用過的空間

代碼實作：

class MyCircularQueue {
    public int front;
    public int rear;
    public int length;
    public int []elem;
    public MyCircularQueue(int k) {
        elem=new int[k+1];
        rear=0;
        front=rear;
        length=k+1;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[rear]=value;
        rear=(rear+1)%length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front=(front+1)%length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return elem[((rear-1)+length)%length];
    }
    
    
    public boolean isEmpty() {
        if(rear==front)
        return true;
        else{
            return false;
        }
    }
    
    public boolean isFull() {
        if((rear+1)%length==front){
          return true;  
        }else{
            return false;
        }
    }
}

3.ArrayList

底層是陣列：
缺點：
①陣列長度固定,超過陣列大小需要擴容并且元素拷貝，回傳一個新的陣列，效率低下

②插入(洗掉)元素慢：往陣列的中插入(洗掉)一個元素，要把陣列中那個新增元素后面的元素往后面（前面）挪動一位，消耗時間多，效率低

優點：
①隨機訪問，查找修改快，時間復雜度為O(1)

// 默認容量

private static final int DEFAULT_CAPACITY = 10;

//空陣列，容量為0呼叫
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空陣列，傳入容量時使用，添加第一個元素的時候會擴展為默認容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存盤元素的陣列
transient Object[] elementData; // non-private to simplify nested class access

// 集合中元素的個數

private int size;

(1).add:

添加元素到隊尾位置，平均時間復雜度為O(1)

public boolean add(E e) {
       // 檢查是否擴容
       ensureCapacityInternal(size + 1);  
       elementData[size++] = e;
       return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是為才創建的是空陣列
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//回傳10與所需大小較大的一個
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //否則回傳所需大小
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果所需大小比陣列大小更大就擴容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//擴容
}
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
       	//1.5倍擴容
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果擴容量后發現比需要的容量還小，則回傳需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 創建新容量的陣列并把老陣列拷貝到新陣列
        elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

(2).void add(int index, E element):

public void add(int index, E element) {
        rangeCheckForAdd(index);//檢查index位置是否合理
		//是否需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 把插入索引位置后的元素都往后挪一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在插入索引位置放置插入的元素
        elementData[index] = element;
        size++;
}
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

(3).addAll()：

public boolean addAll(Collection<? extends E> c) {
	//將集合轉化為陣列
    Object[] a = c.toArray();
    int numNew = a.length;
	//是否擴容
    ensureCapacityInternal(size + numNew);  // Increments modCount
	//拷貝到表尾
    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

}

(4.)get():

//獲取指定索引位置的元素：
public E get(int index) {

    rangeCheck(index);
    return elementData(index);

}
E elementData(int index) {

    return (E) elementData[index];

}

(5).E remove(int index):

public E remove(int index) {

    rangeCheck(index);
    modCount++;

    E oldValue = elementData(index);
	//移動元素次數
    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    // 將最后一個元素洗掉，幫助GC
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;

}

(6).boolean remove(Object o)：

//找到第一個等于指定元素值的元素；
public boolean remove(Object o) {

    if (o == null) {

        for (int index = 0; index < size; index++)

            if (elementData[index] == null) {

                fastRemove(index);
                return true;
            }

    } else {

        for (int index = 0; index < size; index++)

            if (o.equals(elementData[index])) {

                fastRemove(index);
                return true;
            }

    }
    return false;

}

private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // clear to let GC do its work

}

4.LinkedList

底層是雙向鏈表，由于既實作了List有實作了Queue，所以可以作為佇列或者堆疊來使用

優點：
不用擴容，增刪元素方便

.缺點：
查改元素消耗時間多

慎用get(int index)這個方法，需要遍歷鏈表，雖然get方法優化在前size/2在從頭開始遍歷，否則從尾開始遍歷，但是當元素非常多的時候，遍歷的所花的時間是非常多的